在unordered_set或者unordered_map中，经常需要自定义哈希函数，用于将某些没有默认哈希函数的元素放入容器中，比如说pair或者vector。总结（踩坑）了一下，记录一些比较常用的方法，以及一个很重要的细节点，const。
- 注： 以下的代码均基于
unordered_set<vector<int>>进行编写，我们的目的就是要为这个容器编写正确的hash function（假定vector<int>只包含两个元素）
使用函数类型
使用函数类型进行编写会相对麻烦一些。先引用一段关于unordered_set的模板声明和其中一个构造函数[1]，该构造函数基于容器的迭代器进行构造。重点来了，因为我们使用的是函数类型作为模板参数的入参，所以在构造函数的hash参数中还要引入具体的函数指针(为了抹去默认入参Hash())，且由于bucket_count参数在hash参数的前面，所以我们还需要指定bucket_count参数的入参，这样写起来就很麻烦了。
template<
class Key,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator<Key>
> class unordered_set;
template< class InputIt >
unordered_set( InputIt first, InputIt last,
size_type bucket_count = /*implementation-defined*/,
const Hash& hash = Hash(),
const key_equal& equal = key_equal(),
const Allocator& alloc = Allocator() );
OK，了解了原理，接下来就是具体的实现。下述代码只放出哈希函数的定义和哈希集合的构造。可以看出，为了写入函数指针，我们不得不临时指定一个bucket_count，这就显得很随意，说实话，代码比较复杂，也不太好看。
size_t hash_vec(const vector<int> &v){
return hash<int>()(v[0]^v[1]); // 假定vector只有两个元素
}
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
unordered_set<vector<int>, decltype(hash_vec) *> S(obstacles.begin(), obstacles.end(), 10000, &hash_vec);
/* ... process ... */
}
使用类类型
我们观察上面的哈希集合的构造函数的声明，可以发现，构造函数的hash参数的默认值是根据模板参数Hash来指定的，具体来说，也就是模板参数指定的类类型的实例化对象Hash()（这也就是俗称的可调用对象），所以，实际上，在指定模板参数的时候，使用类类型入参是更简洁的。下面是具体的实现。怎么样，看起来是不是简洁多了？^_^
struct hash_myself{
size_t operator()(const vector<int> &v) const {
return hash<int>()(v[0]&v[1]);
}
};
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
unordered_set<vector<int>, hash_myself> S(obstacles.begin(), obstacles.end());
/* ... process ... */
}
关于const
注意！如果没有加上必要的const，可能连编译都通不过。我们一个一个来看。
- 函数类型：
hash_vec函数的入参必须是const引用类型； - 类类型：
hash_myself类中的operator()函数的入参必须是const引用类型，其本身必须是const成员函数。
不用知道为什么，这存粹是编程素养的问题，对于不会发生改变的变量，以及不会改变类中成员的成员函数，都设置为const，是又安全，又有涵养的做法。
网友评论