如何将unordered_set与自定义类型一起使用？

Question

是否需要为自定义类型创建自己的哈希函数？我可以使用unordered_set没有默认值吗？

Answer 1

标准库包含std::hash<T>基本类型,指针和std::string(或者更确切地说,对于所有特化std::basic_string)的特化.

不幸的是,图书馆里没有包含以下重要的新的历史的组合功能,但是这是加速的一部分,你应该复制到你的代码:

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源代码,了解许多示例和有用的实现.显然,您可以使用此函数为您自己的类型创建哈希函数.例如,这里是一对哈希:

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;
    }
};

但请注意,哈希组合不会产生良好的哈希值.结果具有非常差的统计质量(例如,很容易创建哈希冲突).好的散列需要能够看到所有原始输入位,并且不能通过部分散列来计算.(这就是为什么目前的标准库没有更好的解决方案;没有人能够提出令人满意的设计.)

Answer 2

是的,您需要编写自己的哈希函数.这听起来并不像听起来那么糟糕:如果你的类有任何你知道的可清除成员是合理的唯一,你可以只返回该成员的哈希值.

您可以通过专门化std::hash或通过显式传递散列类作为模板参数来提供此散列.