撰写今天在使用C++中的unordered_map的时候遇到一个小问题。我试图将std::pair<int, int>作为键放到unordered_map中，结果编译器无情地报错。众所周知，一旦模板类编译出错，错误信息一般都要几十行甚至数百行，在其中“徜徉”了许久之后，我发现下面的错误信息可能对我会有帮助：
error: no match for call to '(const std::hash<std::pair<int, int> >) (const std::
pair<int, int>&)'
原来，标准库中并未为std::pair 提供哈希函数，之前我一直以为标准库的所有组件都提供了相应的std::hash<T>。
找到问题所在之后就可以着手解决了，本文以std::unordered_set<std::pair<int, int>>为例，讲述如何为类型自定义哈希函数。
首先，需要查看std::unordered_set 类的声明
template < class Key, // unordered_set::key_type/value_type >
class Hash = hash<Key>, // unordered_set::hasher
class Pred = equal_to<Key>, // unordered_set::key_equal
class Alloc = allocator<Key> // unordered_set::allocator_type
> class unordered_set;
注意到第二个模板参数就是与哈希函数相关的内容，不过它并不是接收一个函数，而是一个函数对象，因此我们可以实现一个计算std::pair<int, int>的函数对象，例如：
#include<iostream>
#include<unordered_set>
using namespace std;
class myhash {
public:
std::size_t operator()(const std::pair<int, int> &p) const {
return std::hash<int>()(p.first) ^ std::hash<int>()(p.second);
}
};
int main()
{
unordered_set<pair<int,int>, myhash> us;
us.insert({0, 0});
return 0;
}
上述例子中使用std::pair 中两个元素的哈希值的异或作为std::pair的哈希值，你可以采用任何你可以想到的方法构造哈希值，只要返回结果为std::size_t 即可。 需要特别注意myhash::operator() 中的两个const，丢掉任何一个都可能会使你的代码编译错误。
除了上述写法，还可以采用下面的方法添加默认的哈希函数
#include<iostream>
#include<unordered_set>
using namespace std;
namespace std {
template<>
class hash<pair<int, int>> {
public:
size_t operator()(const pair<int, int> &p) const {
return std::hash<int>()(p.first) ^ std::hash<int>()(p.second);
}
};
} // namespace std
int main()
{
unordered_set<pair<int,int>> us;
us.insert({0, 0});
return 0;
}
这样写可以使用unordered_set 的第二个模板参数的默认参数，也就不需要在定义unordered_set 的时候显式地给出了。
到这里，我们的问题已经解决了，但我们只为std::pair<int, int> 定义了哈希函数，如果我们需要std::pair<double, char> 等等，还需要再次做很多相似的工作，这里使用C++强大的模板给出这个问题的一种解决方法：
#include<iostream>
#include<unordered_set>
using namespace std;
namespace std {
template<>
template<typename T, typename U>
class hash<pair<T, U>> {
public:
size_t operator()(const pair<T, U> &p) const {
return std::hash<T>()(p.first) ^ std::hash<U>()(p.second);
}
};
} // namespace std
int main()
{
unordered_set<pair<int,int>> us1;
us1.insert({0, 0});
unordered_set<pair<double, char>> us2;
us2.insert({3.14, 'p'});
unordered_set<pair<pair<int, float>, pair<double, long>>> us3;
us3.insert({{1, 2.3f}, {4.5, 678}});
return 0;
}
只要类型T和类型U定义了哈希函数，则上述代码就可以为std::pair<T, U> 定义一个哈希函数。
本文由kedixa发表于个人博客，
转载请注明作者及出处。
本文链接：https://blog.kedixa.top/2017/cpp-user-defined-hash/