C++ STL無序容器自定義雜湊函數和比較規則（超級詳細）

前面在講解 unordered_map、unordered_multimap、unordered_set 以及 unordered_multiset 這 4 種無序關聯式容器（雜湊容器）時，遺留過一個共性問題，即如何給無序容器自定義一個雜湊函數和比較規則？

注意，雖然每種無序容器都指定了預設的 hash<key> 雜湊函數和 equal_to<key> 比較規則，但它們僅適用於儲存基本型別（比如 int、double、float、string 等）資料的無序容器。換句話說，如果無序容器儲存的資料型別為自定義的結構體或類，則 STL 標準庫提供的 hash<key> 和 equal_to<key> 將不再適用。

C++無序容器自定義雜湊函數

我們知道，無序容器以鍵值對的方式儲存資料（unordered_set 和 unordered_multiset 容器可以看做儲存的是鍵和值相等的鍵值對），且底層採用雜湊表結構儲存各個鍵值對。在此儲存結構中，雜湊函數的功能是根據各個鍵值對中鍵的值，計算出一個雜湊值（本質就是一個整數），雜湊表可以根據該值判斷出該鍵值對具體的儲存位置。

簡單地理解雜湊函數，它可以接收一個元素，並通過內部對該元素做再加工，最終會得出一個整形值並反饋回來。需要注意的是，雜湊函數只是一個稱謂，其本體並不是普通的函數形式，而是一個函數物件類。因此，如果我們想自定義個雜湊函數，就需要自定義一個函數物件類。

關於什麼函數物件類，可閱讀《C++函數物件詳解》一節做詳細了解，由於不是本節重點，這裡不再贅述。

舉個例子，假設有如下一個 Person 類：

class Person {
public:
    Person(string name, int age) :name(name), age(age) {};
    string getName() const;
    int getAge() const;
private:
    string name;
    int age;
};
string Person::getName() const {
    return this->name;
}
int Person::getAge() const {
    return this->age;
}

在此基礎上，假設我們想建立一個可儲存 Person 類物件的 unordered_set 容器，考慮到 Person 為自定義的型別，因此預設的 hash<key> 雜湊函數不再適用，這時就需要以函數物件類的方式自定義一個雜湊函數。比如：

class hash_fun {
public:
    int operator()(const Person &A) const {
        return A.getAge();
    }
};

注意，過載 ( ) 運算子時，其引數必須為 const 型別，且該方法也必須用 const 修飾。

可以看到，我們利用 hash_fun 函數物件類的 ( ) 運算子過載方法，自定義了適用於 Person 類物件的雜湊函數。該雜湊函數每接收一個 Person 類物件，都會返回該物件的 age 成員變數的值。

事實上，預設的 hash<key> 雜湊函數，其底層也是以函數物件類的形式實現的。

由此，在建立儲存 Person 類物件的 unordered_set 容器時，可以將 hash_fun 作為引數傳遞給該容器模板類中的 Pred 引數：

std::unordered_set<Person, hash_fun> myset；

但是，此時建立的 myset 容器還無法使用，因為該容器使用的是預設的 std::equal_to<key> 比較規則，但此規則並不適用於該容器。

C++無序容器自定義比較規則

和雜湊函數一樣，無論建立哪種無序容器，都需要為其指定一種可比較容器中各個元素是否相等的規則。

值得一提的是，預設情況下無序容器使用的 std::equal_to<key> 比較規則，其本質也是一個函數物件類，底層實現如下：

template<class T>
class equal_to
{
public:   
    bool operator()(const T& _Left, const T& _Right) const{
        return (_Left == _Right);
    }   
};

可以看到，該規則在底層實現過程中，直接用 == 運算子比較容器中任意 2 個元素是否相等，這意味著，如果容器中儲存的元素型別，支援直接用 == 運算子比較是否相等，則該容器可以使用預設的 std::equal_to<key> 比較規則；反之，就不可以使用。

顯然，對於我們上面建立的 myset 容器，其內部儲存的是 Person 類物件，不支援直接使用 == 運算子做比較。這種情況下，有以下 2 種方式可以解決此問題：

1. 在 Person 類中過載 == 運算子，這會使得 std::equal_to<key> 比較規則中使用的 == 運算子變得合法，myset 容器就可以繼續使用 std::equal_to<key> 比較規則；
2. 以函數物件類的方式，自定義一個適用於 myset 容器的比較規則。

1) 過載==運算子

如果選用第一種解決方式，需要注意的是，C++ 中只能以成員函數的形式過載 == 運算子。仍以 Python 類為例，在此類的外部新增如下語句：

bool operator==(const Person &A, const Person &B) {
    return (A.getAge() == B.getAge());
}

注意，這裡在過載 == 運算子時，2 個引數必須用 const 修飾。

可以看到，通過此方式過載的運算子，當 std::equal_to<key> 函數物件類中直接比較 2 個 Person 類物件時，實際上是在比較這 2 個物件的 age 成員變數是否相等。換句話說，此時的 std::equal_to<key> 規則的含義為：只要 2 個 Person物件的 age 成員變數相等，就認為這 2 個 Person 物件是相等的。

過載 == 運算子之後，就能以如下方式建立 myset 容器：

std::unordered_set<Person, hash_fun> myset{ {"zhangsan", 40},{"zhangsan", 40},{"lisi", 40},{"lisi", 30} };

注意，雖然這裡給 myset 容器初始化了 4 個 Person 物件，但由於比較規則以各個類物件的 age 值為準，myset 容器會認為前 3 個 Person 物件是相等的，因此最終 myset 容器只會儲存 {"zhangsan", 40} 和 {"lisi", 30}。

2) 以函數物件類的方式自定義比較規則

除此之外，還可以完全捨棄 std::equal_to<key>，以函數物件類的方式自定義一個比較規則。比如：

class mycmp {
public:
    bool operator()(const Person &A, const Person &B) const {
        return (A.getName() == B.getName()) && (A.getAge() == B.getAge());
    }
};

在 mycmp 規則的基礎上，我們可以像如下這樣建立 myset 容器：

std::unordered_set<Person, hash_fun, mycmp> myset{ {"zhangsan", 40},{"zhangsan", 40},{"lisi", 40},{"lisi", 30} };

由此建立的 myset 容器，雖然初始化了 4 個 Person 物件，但 myset 容器根據 mycmp 比較規則，可以識別出前 2 個是相等的，因此最終該容器內部存有  {"zhangsan", 40}、{"lisi", 40} 和 {"lisi", 30} 這 3 個 Person 物件。

總結

總的來說，當無序容器中儲存的是基本型別（int、double、float、string）資料時，自定義雜湊函數和比較規則，都只能以函數物件類的方式實現。

而當無序容器中儲存的是用結構體或類自定義型別的資料時，自定義雜湊函數的方式仍只有一種，即使用函數物件類的形式；而自定義比較規則的方式有兩種，要麼也以函數物件類的方式，要麼仍使用預設的 std::equal_to<key> 規則，但前提是必須過載 == 運算子。

如下是本節的完整程式碼，讀者可直接拷貝下來，加深對本節知識的理解：

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
class Person {
public:
    Person(string name, int age) :name(name), age(age) {};
    string getName() const;
    int getAge() const;
private:
    string name;
    int age;
};
string Person::getName() const {
    return this->name;
}
int Person::getAge() const {
    return this->age;
}
//自定義雜湊函數
class hash_fun {
public:
    int operator()(const Person &A) const {
        return A.getAge();
    }
};

//過載 == 運算子，myset 可以繼續使用預設的 equal_to<key> 規則
bool operator==(const Person &A, const Person &B) {

    return (A.getAge() == B.getAge());
}
//完全自定義比較規則，棄用 equal_to<key>
class mycmp {
public:
    bool operator()(const Person &A, const Person &B) const {
        return (A.getName() == B.getName()) && (A.getAge() == B.getAge());
    }
};
int main()
{
    //使用自定義的 hash_fun 雜湊函數，比較規則仍選擇預設的 equal_to<key>,前提是必須過載 == 運算子
    std::unordered_set<Person, hash_fun> myset1{ {"zhangsan", 40},{"zhangsan", 40},{"lisi", 40},{"lisi", 30} };
    //使用自定義的 hash_fun 雜湊函數，以及自定義的 mycmp 比較規則
    std::unordered_set<Person, hash_fun, mycmp> myset2{ {"zhangsan", 40},{"zhangsan", 40},{"lisi", 40},{"lisi", 30} };
   
    cout << "myset1:" << endl;
    for (auto iter = myset1.begin(); iter != myset1.end(); ++iter) {
        cout << iter->getName() << " " << iter->getAge() << endl;
    }

    cout << "myset2:" << endl;
    for (auto iter = myset2.begin(); iter != myset2.end(); ++iter) {
        cout << iter->getName() << " " << iter->getAge() << endl;
    }
    return 0;
}

程式執行結果為：

myset1:
zhangsan 40
lisi 30
myset2:
lisi 40
zhangsan 40
lisi 30