Generischer Hash für Tupel in unordered_map / unordered_set

Dies funktioniert auf gcc 4.5, dass alle c++0x-Tupel mit standard-hashable Typen, die Mitglieder
unordered_map und unordered_set ohne weiteres.
(Ich habe den code in eine header-Datei und fügen Sie einfach.)

Die Funktion hat, zu Leben im std-namespace, so dass es abgeholt wird von
argument-dependent name lookup (ADL).

Gibt es eine einfachere Lösung?

#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-Konformen code

Yakk weist darauf hin, dass die Spezialisierung Dinge im std-namespace ist tatsächlich ein Undefiniertes Verhalten. Wenn Sie möchten, haben eine Standard-konforme Lösung, dann müssen Sie zu bewegen, alle dieser code in Ihrem eigenen namespace, und geben eine Vorstellung von ADL die Suche nach den richtigen hash-Implementierung automatisch. Statt :

unordered_set<tuple<double, int> > test_set;

Benötigen Sie:

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

wo hash_tuple ist in Ihrem eigenen Namensraum, anstatt std::.

Um dies zu tun, müssen Sie zunächst erklären, eine hash-Implementierung innerhalb der hash_tuple namespace. Dies wird uns alle nicht Tupel-Typen auf den std::hash:

namespace hash_tuple{

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

Stellen Sie sicher, dass hash_combine Anrufe hash_tuple::hash und nicht 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);
    }
}

Dann sind alle anderen vorherigen code, sondern legte es in namespace hash_tuple und nicht 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;                                 
        }                                              
    };

}

InformationsquelleAutor der Antwort Leo Goodstadt

In meinem C++0x draft 20.8.15 sagt hash ist spezialisiert für built-in Typen (auch Zeiger, aber scheint nicht zu bedeuten, dereferenzieren Sie). Es scheint auch so zu sein, spezialisiert für error_codebitset<N>unique_ptr<T, D>shared_ptr<T>typeindexstringu16stringu32stringwstringvector<bool, Allocator>und thread::id. (herrlichen Liste!)

Habe ich nicht verwendet C++0x variadics, so dass meine Formatierung ist wohl Weg, aber etwas in diese Richtung funktionieren könnte, für alle Tupel.

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

Diese version tatsächlich kompiliert und ausgeführt wird

Yakk hat beobachtet, dass sich spezialisiert std::hash direkt technisch nicht erlaubt, da wir sind spezialisiert eine standard-library-Vorlage einer Erklärung, dass nicht nicht abhängig von einem benutzerdefinierten Typ.

InformationsquelleAutor der Antwort Mooing Duck