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

问题描述

为什么std::unordered_map<tuple<int, int>, string> 只是开箱即用?必须为 tuple 定义散列函数很繁琐，例如

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

构建以元组为键的无序映射 (Matthieu M.) 展示了如何boost::tuple 自动执行此操作.有没有在不使用可变参数模板的情况下对 c++0x 元组执行此操作?

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 :(

推荐答案

这适用于 gcc 4.5，允许所有包含标准哈希类型的 c++0x 元组成为unordered_map 和 unordered_set 不用多说.(我将代码放在头文件中并包含它.)

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.)

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

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

    };
}

标准符合代码

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

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;

你需要:

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

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

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

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

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

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

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

然后包含所有其他以前的代码，但将其放入 namespace hash_tuple 而不是 std::

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屋！