unordered_set/map自定义哈希函数

今天在使用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> 定义一个哈希函数。

发表评论

电子邮件地址不会被公开。 必填项已用*标注