如何使用unordered_set与自定义类型？ [英] How to use unordered_set with custom types?

问题描述

是否需要为自定义类型创建自己的哈希函数？

Is it required that I create my own hash function for custom types? Is there no defaults I can use with unordered_set?

推荐答案

标准库包含 std ::对于基本类型，对于指针和对于 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.)

这篇关于如何使用unordered_set与自定义类型？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！