在C++ STL中使用unordered_set hash_function()

unordered_set是C++ STL中的一个容器，它通过哈希表实现快速查找、插入、删除元素的操作。而哈希表的实现离不开哈希函数，它是将数据映射到哈希表中的关键步骤。在C++11中，我们可以通过重载哈希函数的方式来定义我们自己的哈希函数，以适应不同类型的数据。

unordered_set简介

unordered_set是一个关联容器，它用哈希表实现存储和查找元素。无序容器的优点是查询效率高，而缺点是元素没有顺序性。对于unordered_set，可以用下面的方式定义：

#include<unordered_set>
unordered_set<int> mySet;

这样就定义了一个名为mySet的unordered_set容器，它存储的元素类型为int型。

哈希函数

由于unordered_set的实现是通过哈希表来存储元素的，所以哈希函数是我们需要自定义的关键部分。在C++11之前，我们必须手动实现哈希函数并将其作为unordered_set容器类的模板参数之一。在C++11中，我们可以通过对类std::hash进行特化实现自己的哈希函数。

下面的示例演示如何为一个自定义的类型Person实现哈希函数：

#include<iostream>
#include<unordered_set>

using namespace std;

class Person {
public:
    string name;
    int age;
    int id;
};

namespace std {
    template<>
    struct hash<Person> {
        size_t operator()(const Person& p) const {
            return hash<string>()(p.name) ^ hash<int>()(p.age) ^ hash<int>()(p.id);
        }
    };
}

int main() {
    unordered_set<Person> personSet;
    Person p1 = { "Lucy", 25, 123 };
    Person p2 = { "Tom", 30, 456 };
    Person p3 = { "Lucy", 25, 789 };
    personSet.insert(p1);
    personSet.insert(p2);
    personSet.insert(p3);
    cout << personSet.size() << endl; //输出2，p1和p3被认为是同一个元素
    system("pause");
    return 0;
}

在这个例子中，我们重载了std::hash<>，该结构体有一个用于计算哈希值的模板函数operator()。Person是我们自定义的结构体类型，它有三个成员变量：name、age和id。具体来说，它通过三个哈希函数将string类型的name、int类型的age和id顺序地组合起来，产生一个哈希值。这就是哈希函数的工作原理。

注意，我们必须将重载过的哈希函数置于标准命名空间std中，以便unordered_set容器能够正确找到它。

自定义类型

我们可以使用C++ STL中已有的类型，比如string、int、double等等。但是如果我们定义的类型并不是这些基本类型，我们需要通过对std::hash<>进行特化的方式来实现我们自己的哈希函数。

下面的示例演示了如何为自定义类Student实现哈希函数：

#include<iostream>
#include<unordered_set>

using namespace std;

class Student {
public:
    string name;
    int age;
    int id;
    bool operator==(const Student& s) const {
        return name == s.name && age == s.age && id == s.id;
    }
};

namespace std {
    template<>
    struct hash<Student> {
        size_t operator()(const Student& s) const {
            return hash<string>()(s.name) ^ hash<int>()(s.age) ^ hash<int>()(s.id);
        }
    };
}

int main() {
    unordered_set<Student> studentSet;
    Student s1 = { "Lucy", 25, 123 };
    Student s2 = { "Tom", 30, 456 };
    Student s3 = { "Lucy", 25, 789 };
    studentSet.insert(s1);
    studentSet.insert(s2);
    studentSet.insert(s3);
    cout << studentSet.size() << endl; //输出2，s1和s3被认为是同一个元素
    system("pause");
    return 0;
}

在这个例子中，我们定义了一个自定义的类Student，它有三个成员变量：name、age和id。为了判断两个Student对象是否相等，我们还重载了运算符。接下来，我们为这个类实现了一个哈希函数，它和前面我们为Person类实现的哈希函数非常类似。

结论

C++ STL的unordered_set容器采用哈希表来实现存储和查找元素。为了实现哈希表，我们需要自定义哈希函数。在C++11中，你可以通过对std::hash进行特化实现哈希函数。为了实现哈希函数，你需要选择一些关键的哈希函数，比如std::hash<std::string>、std::hash<int>等等，对每个成员变量分别计算哈希值并将其组合。这使得你可以使用unordered_set来存储自定义的类型，比如Person、Student等。