unordered_map / unordered_set中元组的通用哈希

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.

为什么std :: unordered_map ,string>只是开箱即用?为tuple 定义一个哈希函数是很繁琐的,例如, ,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.) shows how to automate this for boost::tuple. Is there anyway of doing this for c++0x tuples without using variadic templates?

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

Surely this should be in the standard :(

当然这应该在标准:(

3 个解决方案

#1

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

这适用于gcc 4.5,允许包含标准hashable类型的所有c ++ 0x元组成为unordered_map和unordered_set的成员,而不会更加轻松。 (我把代码放在头文件中,只是包含它。)

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

该函数必须存在于std命名空间中,以便通过参数依赖的名称查找(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://*.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 :

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

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

其中hash_tuple是你自己的命名空间而不是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:

为此,首先必须在hash_tuple命名空间内声明一个哈希实现。这会将所有非元组类型转发给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

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

Then include all the other previous code but put it inside namespace hash_tuple and not std::

然后包括所有其他以前的代码,但把它放在命名空间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;                                 
        }                                              
    };

}

#2

#include <boost/functional/hash.hpp>
#include <tuple>

namespace std
{

template<typename... T>
struct hash<tuple<T...>>
{
    size_t operator()(tuple<T...> const& arg) const noexcept
    {
        return boost::hash_value(arg);
    }
};

}

#3

In my C++0x draft, 20.8.15 says hash is specialized for built-in types (including pointers, but doesn't seem to imply dereferencing them). It also appears to be specialized for error_code, bitset<N>, unique_ptr<T, D>, shared_ptr<T>, typeindex, string, u16string, u32string, wstring, vector<bool, Allocator>, and thread::id. (facinating list!)

在我的C ++ 0x草案中,20.8.15表示hash专门用于内置类型(包括指针,但似乎并不意味着取消引用它们)。它似乎也专门用于error_code,bitset ,unique_ptr ,shared_ptr ,typeindex,string,u16string,u32string,wstring,vector 和thread :: id。 (表示清单!) ,allocator> ,d>

I've not used C++0x variadics, so my formatting is probably way off, but something along these lines might work for all tuples.

我没有使用过C ++ 0x variadics,所以我的格式化可能已经过时了,但这些行中的某些内容可能适用于所有元组。

size_t hash_combiner(size_t left, size_t right) //replacable
{ return left + 0x9e3779b9 + (right<<6) + (right>>2);}

template<int index, class...types>
struct hash_impl {
    size_t operator()(size_t a, const std::tuple<types...>& t) const {
        typedef typename std::tuple_element<index, std::tuple<types...>>::type nexttype;
        hash_impl<index-1, types...> next;
        size_t b = std::hash<nexttype>()(std::get<index>(t));
        return next(hash_combiner(a, b), t); 
    }
};
template<class...types>
struct hash_impl<0, types...> {
    size_t operator()(size_t a, const std::tuple<types...>& t) const {
        typedef typename std::tuple_element<0, std::tuple<types...>>::type nexttype;
        size_t b = std::hash<nexttype>()(std::get<0>(t));
        return hash_combiner(a, b); 
    }
};

template<class...types>
struct tuple_hash<std::tuple<types...>> {
    size_t operator()(const std::tuple<types...>& t) {
        const size_t begin = std::tuple_size<std::tuple<types...>>::value-1;
        return hash_impl<begin, types...>()(0, t);
    }
}

This version actually compiles and runs

这个版本实际上编译并运行

Yakk has observed that specializing std::hash directly is technically not allowed, since we're specializing a standard library template with a declaration that does not depend on a user-defined type.

Yakk已经观察到,在技术上不允许直接专门化std :: hash,因为我们专门化了一个标准库模板,其声明不依赖于用户定义的类型。