unordered_map / unordered_set中的元组的通用哈希 [英] Generic hash for tuples in unordered_map / unordered_set

问题描述

为什么 std :: unordered_map< tuple< int，int>，string>
为 tuple 定义一个散列函数是很繁琐的，例如

 模板<> struct do_hash< tuple< int，int>> 
 {size_t operator（）（std :: tuple< int，int> const& tt）const {...}}; 
  

（Matthieu M.）展示了如何
自动化为 boost :: tuple 。有没有使用c ++ 0x元组而不使用可变参数模板？

当然这应该在标准中：（

< gcc 4.5允许包含标准hashable类型的所有c ++ 0x元组都是
unordered_map 的成员

c $ c>和 unordered_set 不用多说了。
（我把代码放在头文件中，只是包含它。）

函数必须存在于std命名空间中，以便它可以通过
参数依赖的名称查找（ADL）来获取。

有更简单的解决方案吗？

  #include< tuple> 
 namespace std {
 namespace 
 {
 
 //来自boost的代码
 //黄金比例的交互有助于传播熵
 //并处理重复
 //查看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 + < 6）+（种子> 2）; 
} 
 
 //从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& ，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& 
} 
}; 
} 
 
 template< typename ... TT> 
 struct hash< std :: tuple< TT ...>> 
 {
 size_t 
 operator（）（std :: tuple< TT ...> const& tt）const 
 {
 size_t seed = 
 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

 命名空间hash_tuple {
 
命名空间
 {
 template< class T& 
 inline void hash_combine（std :: size_t& seed，T const& v）
 {
 seed ^ = hash_tuple :: hash T（v）+ 0x9e3779b9 + < 6）+（种子> 2）; 
} 
} 
  

然后包括所有其他以前的代码， 命名空间hash_tuple 而不是 std ::

  namespace hash_tuple {
 
 namespace 
 {
 //递归模板代码派生自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& ，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& 
} 
}; 
} 
 
 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; 
} 
}; 
 
} 
  

Why doesn't std::unordered_map<tuple<int, int>, string> just work out of the box? It is tedious to have to define a hash function for tuple<int, int>, e.g.

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.) shows how to automate this for boost::tuple. Is there anyway of doing this for c++0x tuples without using variadic templates?

Surely this should be in the standard :(

解决方案

This works on gcc 4.5 allowing all c++0x tuples containing standard hashable types to be members of unordered_map and unordered_set without further ado. (I put the code in a header file and just include it.)

The function has to live in the std namespace so that it is picked up by argument-dependent name lookup (ADL).

Is there a simpler solution?

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

    };
}

Standard Conformant code

Yakk points out that specialising things in the std namespace is actually undefined behaviour. If you wish to have a standards conforming solution, then you need to move all of this code into your own namespace and give up any idea of ADL finding the right hash implementation automatically. Instead of :

unordered_set<tuple<double, int> > test_set;

You need:

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

where hash_tuple is your own namespace rather than std::.

To do this, you first have to declare a hash implementation inside the hash_tuple namespace. This will forward all non tuple types to the std::hash:

namespace hash_tuple{

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

Make sure that hash_combine calls hash_tuple::hash and not 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);
    }
}

Then include all the other previous code but put it inside namespace hash_tuple and not 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;                                 
        }                                              
    };

}

这篇关于unordered_map / unordered_set中的元组的通用哈希的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！