C++ sort(STL sort)排序演算法詳解

2020-07-16 10:04:29
在很多應用中,排序都是至關重要的,而且很多 STL 演算法也只適用於有序物件序列。定義在 algorithm 標頭檔案中的函數模板 sort<Iter>() 預設會將元素段排成升序,這也就意味著排序的物件的型別需要支援 < 運算子。 

物件也必須是可交換的,這說明可以用定義在 utility 標頭檔案中的函數模板 swap() 來對兩個物件進行交換。這進一步表明這種物件的型別需要實現移動建構函式和移動賦值運算子。

函數模板 sort<Iter>() 的型別引數 Iter 是元素段元素對應的迭代器型別,而且它們必須支援隨機存取疊代器。這表明 sort() 演算法只能對提供隨機存取疊代器的容器中的元素進行排序,也說明 sort() 只能接受 array、vector、deque 或標準陣列中的元素。可以回顧前面章節,list 和 forward_list 容器都有成員函數 sort(); 這些用來排序的特殊成員函數是必要的,因為 list 只提供雙向疊代器,且 forward_list 只提供正向疊代器。

可以從函數呼叫的引數中推匯出 sort() 的模板型別引數,它們是定義被排序物件範圍的疊代器。當然,疊代器型別隱式定義了這個元素段中物件的型別。下面是一個使用 sort() 演算法的範例:
std::vector<int> numbers {99, 77, 33, 66, 22, 11, 44, 88};
std::sort(std::begin(numbers), std::end(numbers));
std::copy(std::begin(numbers), std::end(numbers),std:: ostream_iterator<int> {std::cout," "}) ;
// Output: 11 22 33 44 66 77 88 99
sort() 呼叫將 number 容器的全部元素排成升序,然後用 copy() 演算法輸出結果。可以不必對容器的全部內容進行排序。下面這條語句對 numbers 中除了第一個和最後一個元素之外的元素進行了排序:
std::sort(++std::begin(numbers),--std::end(numbers));
為了將元素排成降序,需要提供一個用來比較元素的函數物件,作為 sort() 的第三個引數:
std::sort(std::begin(numbers), std::end(numbers), std::greater<>());
這個比較函數必須返回布林值,而且有兩個引數,它們要麼是疊代器解除參照後得到的型別,要麼是疊代器解除參照後可以隱式轉換成的型別。引數可以是不同型別的。只要比較函數滿足這些條件,它就可以是你喜歡的任何樣子,也包括 lambda 表示式。例如:
std::deque<string> words { "one", "two", "nine", "nine", "one", "three", "four", "five", "six" };
std::sort(std::begin(words), std::end(words),[](const string& s1, const string& s2) { return s1.back()> s2.back();});
std::copy(std::begin(words), std::end(words),
std::ostream_iterator<string> {std::cout," "}); // six four two one nine nine one three five
這段程式碼對 deque 容器 words 中的 string 元素進行了排序,並且輸出了排序後的結果。這裡的比較函數是一個 lambda 表示式,它們用每個單詞的最後一個字母來比較排序的順序。結果元素以它們最後一個字母的降序來排序。

下面在一個簡單的範例中介紹 sort() 的用法。這裡會先從鍵盤讀取 Name 物件,然後將它們按升序排列,再輸出結果。Name 類定義在 Name.h 標頭檔案中,它包含下面這些程式碼:
#ifndef NAME_H
#define NAME_H
#include <string>                                // For string class

class Name
{
private:
    std::string first {};
    std::string second {};

public:
    Name(const std::string& name1, const std::string& name2) : first(name1), second(name2){}
    Name()=default;
    std::string get_first() const { return first; }
    std::string get_second() const { return second; }

    friend std::istream& operator>>(std::istream& in, Name& name);
    friend std::ostream& operator<<(std::ostream& out, const Name& name);
};

// Stream input for Name objects
inline std::istream& operator>>(std::istream& in, Name& name)
{
    return in >> name.first >> name.second;
}

// Stream output for Name objects
inline std::ostream& operator<<(std::ostream& out, const Name& name)
{
    return out << name.first << " " << name.second;
}
#endif
這個流插入和提取運算子被定義為 Name 物件的友元函數。可以將 operator<() 定義為類的成員函數,但為了展示如何為 sort() 演算法指定比較函數引數,這裡沒有定義它。下面是程式程式碼:
// Sorting class objects
#include <iostream>                              // For standard streams
#include <string>                                // For string class
#include <vector>                                // For vector container
#include <iterator>                              // For stream and back insert iterators
#include <algorithm>                             // For sort() algorithm
#include "Name.h"

int main()
{
    std::vector<Name> names;
    std::cout << "Enter names as first name followed by second name. Enter Ctrl+Z to end:";
    std::copy(std::istream_iterator<Name>(std::cin), std::istream_iterator<Name>(),std::back_insert_iterator<std::vector<Name>>(names));

    std::cout << names.size() << " names read. Sorting in ascending sequence...n";
    std::sort(std::begin(names), std::end(names), [](const Name& name1, const Name& name2) {return name1.get_second() < name2.get_second(); });

    std::cout << "nThe names in ascending sequence are:n";
    std::copy(std::begin(names), std::end(names), std::ostream_iterator<Name>(std::cout, "n"));
}
main() 中的一切幾乎都是使用 STL 模板完成的。names 容器用來儲存從 cin 讀入的姓名。輸入由 copy() 演算法執行,它使用一個 istream_iterator<Name> 範例讀入 Name 物件。 istream_iterator<Name> 預設的建構函式會建立流的結束疊代器。copy() 函數用 back_insert_iterator<Name>() 建立的 back_inserter<Name> 疊代器將輸入的每個物件複製到 names 中。為 Name 類過載的流運算子允許使用流疊代器來輸入和輸出 Name 物件。

Name 物件的比較函數是用 lambda 表示式定義的,它是 sort() 演算法的第三個引數。如果想將 operator<() 定義為 Name 類的成員函數,可以省略這個引數。然後用 copy() 演算法將排序後的 names 寫入標準輸出流,它會將前兩個引數指定範圍內的元素複製到作為第三個引數的 ostream_iterator<Name> 物件中。

下面是範例輸出:

Enter names as first name followed by second name. Enter Ctrl+Z to end:
Jim Jones
Bill Jones
Jane Smith
John Doe
Janet Jones
Willy Schaferknaker
^Z
6 names read. Sorting in ascending sequence...

The names in ascending sequence are:
John Doe
Jim Jones
Bill Jones
Janet Jones
Willy Schaferknaker
Jane Smith

對 names 的排序只考慮了姓。當姓相同時,可以將 lambda 表示式擴充套件為可以比較名。你可能會好奇在這個範例中為什麼不用 pair<string,string> 來表示姓名,這比定義一個新的類要簡單多了。顯然我們可以這麼做,但卻沒有定義類這麼清楚明瞭。