C++ 自定義比較函數(map和multimap)詳解

2020-07-16 10:04:30
對於為什麼要改變 map 或 multimap 的比較函數,可能想用降序排列的元素來代替預設升序排列的元素;或者鍵需要使用的比較函數和直接的小於或大於運算子不同。例如,如果鍵是指標的話,就需要使用這種函數。在看一個演示如何替代比較函數的範例之前,先強調比較鍵的函數物件所需要的一個非常重要的條件。

需要注意的是,map 容器的比較函數在相等時不能返回 true,換句話說,不能使用<=或>=來比較。這是為什麼? map或multimap容器用等價來判 斷鍵是否相等。如果表示式 key1<key2 和 key2<key1 的結果都是 false,那麼 key1 和 key2 是等價的,所以它們被認為是相等的。換一種方式,等價意味著 !(key1<key2)&&!(key2<key1) 的運算值為 true。

如果我們的函數物件實現了 <=,思考一下會發生什麼。當 key1 和 key2 相等時,key1<=key2 和 key2<=key1 都為 true,因而表示式 !(key1<=key2)&&!(key2<=key1) 為 false,這意味著來自於容器的這兩個鍵竟然不相等。

事實上,不會出現用相等來判斷鍵的情況。這意味著這個容器將無法進行正常操作。讓我們來看一下如何替換比較函數,從而使容器可以正常操作。

greater<T>物件的用法

假設我們已經為先前章節中使用的 Name 類實現了 operator>()。在這個類的定義中,成員函數 operator>() 的定義如下:
bool operator>(const Name& name) const
{
    return second > name.second ||(second == name.second && first > name.first);
}
當然,可以將成員函數的定義放在類的外面:
inline Name::bool operator> (const Name& name) const
{
    return second > name.second || (second == name.second && first > name.first);
}
現在可以用 Name 物件作為 map 的鍵,將容器中的 pair 物件按降序排列:
std::map<Name,size_t, std::greater<Name>>people{{Name{"Al", "Bedo"}, 53}, {Name{"Woody","Leave"},33},{Name{"Noah", "Lot"}, 43}};
這裡第三個模板型別引數指定了用來比較鍵的函數物件的型別。greater<Name> 物件使用 > 運算子來比較 Name 物件,因為 Name 類實現了 operator>(),所以可以這樣做。這三個元素會按照降序排列。如果列出這些元素,它們的排列方式是很明顯的,可以像下面這樣列出元素:
for ( const auto& p : people)
    std:: cout << p.first << " " << p.second << " n";
基於範圍的 for 迴圈遍歷了 people 容器中的所有元素,然後將它們輸出:

Noah Lot 43
Woody Leave 33
Al Bedo 53

用自定義的函數物件來比較元素

如果 map 或 multimap 中的鍵是指標的話,那麼需要定義一個函數來比較它們所指向的物件,否則會比較指標所表示的地址,這並不是我們想要的。如果鍵是不支援直接進行 < 或 > 比較的型別,為了可以在 map 或 multimap 中使用它們,必須為它們定義一個適當的函數物件。處理這兩種情況的方式在本質上相同。

假設我們想用堆上生成的物件的指標作為 map 容器的鍵。下面用指向 string 物件的智慧指標來說明這種情況。這個容器的鍵可以是 unique_ptr<string> 型別,在這個範例中我們需要含兩個 unique_ptr<string> 引數的比較函數,這個函數可以比較它的引數所指向的 string 物件。可以用偽函數,即函數物件來定義它,這裡假設使用了 using_std::string:
// Compares keys that are unique_ptr<string> objects
class Key_compare
{
public:
    bool operator () (const std::unique_ptr<string>& p1, const std::unique_ptr <string>& p2) const
    {
        return *p1 < *p2;
    }
};
可以用 Key_compare 型別作為 map 容器來比較鍵的函數物件的型別:
std::map<std::unique_ptr<string>,std::string,Key_compare> phonebook;
第三個 map 模板引數指定了用來比較元素的函數物件的物件,因為這個型別引數指定了預設的值 less<T>,所以我們需要指定我們自己定義的函數物件。map 中的元素是 pair 物件,它封裝了一個指向 string 物件的智慧指標,string 物件用來儲存人名和電話。對於這個 map,我們不能使用初始化列表,因為初始化列表包含了副本,而 unique_ptr 物件是不能被複製的。我們至少有兩種向容器中新增元素的方式:
Phonebook.emplace(std::make_unique<string>("Fred"), "914 626 7897");
Phonebook.insert(std::make_pair(std::make_unique<string>("Lily"), "212 896 4337"));
第一條語句在容器的適當位置直接生成了一個 pair 物件。這個 pair 物件的建構函式可以移動這裡指定的引數,所以可以無條件地複製它們。第二條語句呼叫了容器的成員函數 insert(),它會將引數元素移到容器中。

可以按如下所示列出 phonebook 容器中的元素:
for (const auto& p: phonebook)
    std:: cout << *p.first << " " << p.second << std::endl;
基於範圍的 for 迴圈遍歷了 map 中的所有元素,map 中的元素都是 pair 物件。每一個 pair 物件的成員變數 first 都是 unique 指標,所以不得不通過解除參照來存取它們所指向的 string 物件。如果使用疊代器來存取元素,語法略有不同:
for (auto iter = std::begin (phonebook) ;iter != std:: end (phonebook) ; ++iter)
    std:: cout << *iter->first << " " << iter->second << std::endl;
它和之前的迴圈有相同的輸出,但使用的是疊代器。可以用 -> 運算子來存取 pair 物件的成員。因為這樣定義了偽函數 Key_compare,所以容器中的元素會被升序排列。