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

Posted on by

前面在講解如何創建 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://jb51.net.net/stl/",
        "http://jb51.net.net/python/",
        "http://jb51.net.net/java/"};
 //輸出容器中存儲的元素
 for (auto iter = myset.begin(); iter != myset.end(); ++iter) {
   cout << *iter << endl;
 }
 return 0;
}

程序執行結果為：
http://jb51.net.net/stl/
http://jb51.net.net/java/
http://jb51.net.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://jb51.net.net/stl/");
 myset.emplace("http://jb51.net.net/c/");
 myset.emplace("http://jb51.net.net/python/");
 //
 for (auto iter = myset.begin(); iter != myset.end(); ++iter) {
  myString mystr = *iter;
  cout << mystr.getStr() << endl;
 }
 return 0;
}

程序執行結果為：
http://jb51.net.net/c/
http://jb51.net.net/stl/
http://jb51.net.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）也同樣適用，有興趣的讀者可自行編寫代碼驗證。

到此這篇關於C++ STL關聯式容器自定義排序規則的2種方法的文章就介紹到這瞭,更多相關C++ STL關聯式容器自定義排序內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：