Общ хеш за кортежи в unordered_map / unordered_set

Това работи на 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;                                 
        }                                              
    };

}

В моя чернова на C++0x 20.8.15 казва, че хешът е специализиран за вградени типове (включително указатели, но изглежда не предполага тяхното дерефериране). Изглежда също, че е специализиран за error_code, bitset<N>, unique_ptr<T, D>, shared_ptr<T>, typeindex, string, u16string, u32string, wstring, vector<bool, Allocator> и thread::id. (удивителен списък!)

Не съм използвал 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);
    }
}

Тази версия всъщност се компилира и работи

Yakk забеляза, че специализирането на std::hash директно е технически неразрешено, тъй като ние специализираме стандартен библиотечен шаблон с декларация, която не зависи от дефиниран от потребителя тип.

С C++20 е възможно да се използват сгъваеми изрази и генерични ламбда за изчисляване на хеш на кортеж без рекурсия. Предпочитам да разчитам на std::hash<uintmax_t> вместо ръчно комбиниране на хешове:

#include <cinttypes>
#include <cstddef>
#include <functional>
#include <tuple>

class hash_tuple {
    template<class T>
    struct component {
        const T& value;
        component(const T& value) : value(value) {}
        uintmax_t operator,(uintmax_t n) const {
            n ^= std::hash<T>()(value);
            n ^= n << (sizeof(uintmax_t) * 4 - 1);
            return n ^ std::hash<uintmax_t>()(n);
        }
    };

public:
    template<class Tuple>
    size_t operator()(const Tuple& tuple) const {
        return std::hash<uintmax_t>()(
            std::apply([](const auto& ... xs) { return (component(xs), ..., 0); }, tuple));
    }
};

- 1 в sizeof(uintmax_t) * 4 - 1 не е задължително, но изглежда леко подобрява разпределението на хеша. Този клас може да се използва както с std::tuple, така и с std::pair.