C++ STL關聯式容器自定義排序規則（2種方法）

前面在講解如何建立 map、multimap、set 以及 multiset 容器時，遺留了一個問題，即如何自定義關聯式容器中的排序規則？

實際上，為關聯式容器自定義排序規則的方法，已經在《STL priority_queue自定義排序方法》一節中做了詳細的講解。換句話說，為 Priority_queue 容器介面卡自定義排序規則的方法，同樣適用於所有關聯式容器。

總的來說，為關聯式容器自定義排序規則，有以下 2 種方法。

1) 使用函數物件自定義排序規則

在掌握此方法之前，讀者必須對函數物件有基本的了解，可閱讀《C++函數物件》一節。

無論關聯式容器中儲存的是基礎型別（如 int、double、float 等）資料，還是自定義的結構體變數或類物件（包括 string 類），都可以使用函數物件的方式為該容器自定義排序規則。

下面樣例以 set 容器為例，演示了如何用函數物件的方式自定義排序規則：

#include <iostream>
#include <set>      // set
#include <string>       // string
using namespace std;
//定義函數物件類
class cmp {
public:
    //過載 () 運算子
    bool operator ()(const string &a,const string &b) {
        //按照字串的長度，做升序排序(即儲存的字串從短到長)
        return  (a.length() < b.length());
    }
};

int main() {
    //建立 set 容器，並使用自定義的 cmp 排序規則
    std::set<string, cmp>myset{"http://c.biancheng.net/stl/",
                               "http://c.biancheng.net/python/",
                               "http://c.biancheng.net/java/"};
    //輸出容器中儲存的元素
    for (auto iter = myset.begin(); iter != myset.end(); ++iter) {
            cout << *iter << endl;
    }
    return 0;
}

程式執行結果為：

http://c.biancheng.net/stl/
http://c.biancheng.net/java/
http://c.biancheng.net/python/

重點分析一下 6~13 行程式碼，其定義了一個函數物件類，並在其過載 () 運算子的方法中自定義了新的排序規則，即按照字串的長度做升序排序。在此基礎上，程式第 17 行程式碼中，通過將函數物件類的類名 cmp 通過 set 類別範本的第 2 個引數傳遞給 myset 容器，該容器內部排序資料的規則，就改為了以字串的長度為標準做升序排序。

需要注意的是，此程式中建立的 myset 容器，由於是以字串的長度為準進行排序，因此其無法儲存相同長度的多個字串。

另外，C++ 中的 struct 和 class 非常類似（有關兩者區別，可閱讀《C++ struct和class到底有什麼區別》一文），前者也可以包含成員變數和成員函數。因此上面程式中，函數物件類 cmp 也可以使用 struct 關鍵字建立：

//定義函數物件類
struct cmp {
    //過載 () 運算子
    bool operator ()(const string &a, const string &b) {
        //按照字串的長度，做升序排序(即儲存的字串從短到長)
        return  (a.length() < b.length());
    }
};

值得一提的是，在定義函數物件類時，也可以將其定義為模板類。比如：

//定義函數物件模板類
template <typename T>
class cmp {
public:
    //過載 () 運算子
    bool operator ()(const T &a, const T &b) {
        //按照值的大小，做升序排序
        return  a < b;
    }
};

注意，此方式必須保證 T 型別元素可以直接使用關係運算子（比如這裡的 < 運算子）做比較。

2) 過載關係運算子實現自定義排序

其實在 STL 標準庫中，本就包含幾個可供關聯式容器使用的排序規則，如表 1 表示。

表 1 C++ STL標準庫適用於關聯式容器的排序規則
排序規則	功能
std::less<T>	底層採用 < 運算子實現升序排序，各關聯式容器預設採用的排序規則。
std::greater<T>	底層採用 > 運算子實現降序排序，同樣適用於各個關聯式容器。
std::less_equal<T>	底層採用 <= 運算子實現升序排序，多用於 multimap 和 multiset 容器。
std::greater_equal<T>	底層採用 >= 運算子實現降序排序，多用於 multimap 和 multiset 容器。

值得一提的是，表 1 中的這些排序規則，其底層也是採用函數物件的方式實現的。以 std::less<T> 為例，其底層實現為：

template <typename T>
struct less {
    //定義新的排序規則
    bool operator()(const T &_lhs, const T &_rhs) const {
        return _lhs < _rhs;
    }
}

在此基礎上，當關聯式容器中儲存的資料型別為自定義的結構體變數或者類物件時，通過對現有排序規則中所用的關係運算子進行過載，也能實現自定義排序規則的目的。

注意，當關聯式容器中儲存的元素型別為結構體指標變數或者類的指標物件時，只能使用函數物件的方式自定義排序規則，此方法不再適用。

舉個例子：

#include <iostream>
#include <set>      // set
#include <string>       // string
using namespace std;
//自定義類
class myString {
public:
    //定義建構函式，向 myset 容器中新增元素時會用到
    myString(string tempStr) :str(tempStr) {};
    //獲取 str 私有物件，由於會被私有物件呼叫，因此該成員方法也必須為 const 型別
    string getStr() const;
private:
    string str;
};
string myString::getStr() const{
    return this->str;
}
//過載 < 運算子，引數必須都為 const 型別
bool operator <(const myString &stra, const myString & strb) {
    //以字串的長度為標準比較大小
    return stra.getStr().length() < strb.getStr().length();
}

int main() {
    //建立空 set 容器，仍使用預設的 less<T> 排序規則
    std::set<myString>myset;
    //向 set 容器新增元素，這裡會呼叫 myString 類別建構函式
    myset.emplace("http://c.biancheng.net/stl/");
    myset.emplace("http://c.biancheng.net/c/");
    myset.emplace("http://c.biancheng.net/python/");
    //
    for (auto iter = myset.begin(); iter != myset.end(); ++iter) {
        myString mystr = *iter;
        cout << mystr.getStr() << endl;
    }
    return 0;
}

程式執行結果為：

http://c.biancheng.net/c/
http://c.biancheng.net/stl/
http://c.biancheng.net/python/

在這個程式中，雖然 myset 容器表面仍採用預設的 std::less<T> 排序規則，但由於我們對其所用的 < 運算子進行了過載，使得 myset 容器內部實則是以字串的長度為基準，對各個 mystring 類物件進行排序。

另外，上面程式以全域性函數的形式實現對 < 運算子的過載，還可以使用成員函數或者友元函數的形式實現。其中，當以成員函數的方式過載 < 運算子時，該成員函數必須宣告為 const 型別，且引數也必須為 const 型別：

bool operator <(const myString & tempStr) const {
    //以字串的長度為標準比較大小
    return this->str.length() < tempStr.str.length();
}

至於引數的傳值方式是採用按參照傳遞還是按值傳遞，都可以（建議採用按參照傳遞，效率更高）。

同樣，如果以友元函數的方式過載 < 運算子時，要求引數必須使用 const 修飾：

//類中友元函數的定義
friend bool operator <(const myString &a, const myString &b);

//類外部友元函數的具體實現
bool operator <(const myString &stra, const myString &strb) {
    //以字串的長度為標準比較大小
    return stra.str.length() < strb.str.length();
}

當然，本節所講自定義排序規則的方法並不僅僅適用於 set 容器，其它關聯式容器（map、multimap、multiset）也同樣適用，有興趣的讀者可自行編寫程式碼驗證。