c++ - unordered_map/unordered_set 中元组的通用哈希

Question

为什么不 std::unordered_map<tuple<int, int>, string>只是 开箱即用？ 必须为 tuple<int, int> 定义哈希函数是很乏味的，例如

template<> struct do_hash<tuple<int, int>>                               
{   size_t operator()(std::tuple<int, int> const& tt) const {...}  }; 

Building an unordered map with tuples as keys (Matthieu M.)展示了如何 为 boost::tuple 自动执行此操作.是否可以在不使用可变参数模板的情况下对 c++0x 元组执行此操作？

当然这应该在标准中:(

Answer 1

这适用于 gcc 4.5，允许所有包含标准可哈希类型的 c++0x 元组成为 unordered_map 和 unordered_set 事不宜迟。 (我把代码放在一个头文件中，然后直接包含它。)

该函数必须存在于 std 命名空间中，以便由 参数相关的名称查找 (ADL)。

有没有更简单的解决方案？

#include <tuple>
namespace std{
    namespace
    {

        // Code from boost
        // Reciprocal of the golden ratio helps spread entropy
        //     and handles duplicates.
        // See Mike Seymour in magic-numbers-in-boosthash-combine:
        //     http://stackoverflow.com/questions/4948780

        template <class T>
        inline void hash_combine(std::size_t& seed, T const& v)
        {
            seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }

        // Recursive template code derived from Matthieu M.
        template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
        struct HashValueImpl
        {
          static void apply(size_t& seed, Tuple const& tuple)
          {
            HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
            hash_combine(seed, std::get<Index>(tuple));
          }
        };

        template <class Tuple>
        struct HashValueImpl<Tuple,0>
        {
          static void apply(size_t& seed, Tuple const& tuple)
          {
            hash_combine(seed, std::get<0>(tuple));
          }
        };
    }

    template <typename ... TT>
    struct hash<std::tuple<TT...>> 
    {
        size_t
        operator()(std::tuple<TT...> const& tt) const
        {                                              
            size_t seed = 0;                             
            HashValueImpl<std::tuple<TT...> >::apply(seed, tt);    
            return seed;                                 
        }                                              

    };
}

标准合规代码

Yakk 指出在 std 命名空间中特化事物实际上是未定义的行为。如果你希望有一个符合标准的解决方案，那么你需要将所有这些代码移动到你自己的命名空间中，并放弃任何让 ADL 自动找到正确的哈希实现的想法。而不是:

unordered_set<tuple<double, int> > test_set;

你需要:

unordered_set<tuple<double, int>, hash_tuple::hash<tuple<double, int>>> test2;

其中 hash_tuple 是您自己的命名空间而不是 std::。

为此，您首先必须在 hash_tuple 命名空间内声明一个哈希实现。这会将所有非元组类型转发到 std::hash:

namespace hash_tuple{

template <typename TT>
struct hash
{
    size_t
    operator()(TT const& tt) const
    {                                              
        return std::hash<TT>()(tt);                                 
    }                                              
};
}

确保 hash_combine 调用 hash_tuple::hash 而不是 std::hash

namespace hash_tuple{

namespace
    {
    template <class T>
    inline void hash_combine(std::size_t& seed, T const& v)
    {
        seed ^= hash_tuple::hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
}

然后包括所有其他先前的代码，但将其放在 namespace hash_tuple 而不是 std::

中

namespace hash_tuple{

    namespace
    {
        // Recursive template code derived from Matthieu M.
        template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
        struct HashValueImpl
        {
          static void apply(size_t& seed, Tuple const& tuple)
          {
            HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
            hash_combine(seed, std::get<Index>(tuple));
          }
        };

        template <class Tuple>
        struct HashValueImpl<Tuple,0>
        {
          static void apply(size_t& seed, Tuple const& tuple)
          {
            hash_combine(seed, std::get<0>(tuple));
          }
        };
    }

    template <typename ... TT>
    struct hash<std::tuple<TT...>> 
    {
        size_t
        operator()(std::tuple<TT...> const& tt) const
        {                                              
            size_t seed = 0;                             
            HashValueImpl<std::tuple<TT...> >::apply(seed, tt);    
            return seed;                                 
        }                                              
    };

}