如何将 unordered_set 与自定义类型一起使用?
是否需要我为自定义类型创建自己的哈希函数?unordered_set 没有可以使用的默认值吗?
Is it required that I create my own hash function for custom types? Is there no defaults I can use with unordered_set?
推荐答案
标准库包含 std::hash<T> 的特殊化，用于基本类型、指针和 std::string(或者更确切地说，对于 std::basic_string 的所有特化).
The standard library contains specialisations of std::hash<T> for the fundamental types, for pointers and for std::string (or rather, for all specializations of std::basic_string).
不幸的是，该库不包含以下重要的新旧组合函数，但它是 Boost 的一部分，您应该将其复制到您的代码中:
Unfortunately the library does not contain the following vital new-from-old combination function, which is however part of Boost, and which you should copy into your code:
template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
std::hash<T> hasher;
seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
使用此函数，您可以散列对、元组、数组和任何类型的范围本身可散列的元素.浏览 Boost 源以获得许多示例和有用的实现.显然你可以使用这个函数为你自己的类型创建一个散列函数.例如，这里是散列一对:
With this function, you can hash pairs, tuples, arrays, and any sort of range of elements that are themselves hashable. Browse the Boost sources for many examples and useful implementations. And obviously you can use this function to create a hash function for your own types. For example, here's hashing a pair:
template<typename S, typename T> struct pair_hash<std::pair<S, T>>
{
inline std::size_t operator()(const std::pair<S, T> & v) const
{
std::size_t seed = 0;
hash_combine(seed, v.first);
hash_combine(seed, v.second);
return seed;
}
};
但是请注意，散列组合不会产生好的散列值.结果的统计质量非常差(例如，很容易产生哈希冲突).好的散列需要能够看到所有原始输入位，并且不能通过部分散列进行分解.(这就是为什么当前标准库中没有更好的解决方案；没有人能够提出令人满意的设计.)
Please be aware, though, that hash-combining does not produce good hash values. The results have very poor statistic qualities (e.g. it is very easy to create hash collisions). Good hashing needs to be able to see all the raw input bits, and cannot be factored through partial hashes. (That's why there isn't a better solution in the current standard library; nobody has been able to come up with a satisfactory design.)
相关文章