Generische hash für Tupel in unordered_map / unordered_set

Warum nicht std::unordered_map<tuple<int, int>, string> nur
die Arbeit out of the box?
Es ist mühsam, Sie zu haben, um zu definieren, eine hash-Funktion für tuple<int, int> z.B.

template<> struct do_hash<tuple<int, int>>                               
{   size_t operator()(std::tuple<int, int> const& tt) const {...}  };

Gebäude eine ungeordnete Karte mit Tupel als Schlüssel (Matthieu M.) zeigt, wie
automatisieren Sie diese für boost::tuple. Gibt es trotzdem, dies zu tun für c++0x-Tupel ohne mithilfe von variadic templates?

Sicherlich sollte dies in den standard 🙁

Wenn Sie C++0x-warum nicht variadic templates? (oder gibt es eine Implementierung mit Tupeln, aber keine varidic Vorlagen?)
VC++ 2010 entspricht, dass die Beschreibung (und es scheint, dass die nächste version von VC++ ist wahrscheinlich auch).
Wenn std::tuple wird implementiert, indem manuell schreiben aus Vorlagen von 1 bis N-stelligkeit (wie boost::tuple), dann denke ich, dass die std::hash Spezialisierung notwendig, um die hash-Tupel wird auch manuell geschrieben (mit zu klug, Vorverarbeitung?) auf die gleiche Weise. Aaargh!

InformationsquelleAutor Leo Goodstadt | 2011-08-18

c++c++11 tuples 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 nur Sie gehören.)

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

}

Ist es ein std::hash_combine?
Ihre Vorlage kompiliert mit std::hash_combine mit gcc-4.6.3. Ich habe den Schalter zu vermeiden, mit boost
Lu: ich Frage mich, was du redest, da ich auch die hash_combine explizit zu vermeiden boost Abhängigkeiten. Dann bemerkte ich, dass ich vergessen habe zu entfernen die boost-namespace-qualifier aus meinem code... Hoffe, es funktioniert immer noch.
Nicht Wert, das zu undefiniertem Verhalten: nicht spezialisieren Dinge in std:: mit Dingen, die Sie nicht besitzen, und Sie nicht selbst std::tuple<TT...>. Als ein konkretes Beispiel, wie dies könnte schrecklich break code, was passiert, wenn eine neue iteration der standard bringt seine eigene hash-Spezialisierung? Was passiert, wenn jemand anderes hat Ihre glänzende Idee führt eine schmale hash<tuple<int>> Spezialisierung, die sichtbar von einigen, aber nicht allen stellen, wo hash<tuple<int>> verwendet wird? Das sind konkrete Beispiele, aber die UB ist nicht beschränkt durch Sie. Ihr Programm ist schlecht gebildet.
Das ist alt, aber hinzufügen von Spezialisierungen zu den std-namespace ist wirklich zu empfehlen. Hinzufügen von Klassen, Funktionen, oder andere Definitionen explizit verboten. en.cppreference.com/w/cpp/language/extending_std

InformationsquelleAutor Leo Goodstadt

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

}

InformationsquelleAutor Вова

7

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_code, bitset<N>, unique_ptr<T, D>, shared_ptr<T>, typeindex, string, u16string, u32string, wstring, vector<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.

Verwenden left() ^ right() wenn Sie nicht wissen, was zu tun ist. Siehe stackoverflow.com/questions/5889238/... . Aber beachten Sie, dass die XOR-Operation ist nicht immer die richtige Wahl. Mit klarem hinaus kann sich besser, wenn Sie erwarten, dass die Tupel enthalten doppelte Mitglieder. Dies ist wahrscheinlich der Grund, warum es keine standard-hash für Tupel.
Es muss ein versehen, dass Tupel nicht hashable. Zu spät für die standard-obwohl 🙁
seltsam genug, keine container, außer für vector<bool>, und basic_string ist hashable. (bitset ist technisch eine container?)
oh, mir ist gerade jetzt aufgefallen ist: without using variadic templates? whoops. Die Antwort ist Nein, kann nicht getan werden für alle Tupel, da ein Tupel ist eine variadic template-Typ.
und + sind sowohl kommutativ ist, und somit zu einer schlechten Wahl für die Kombination von hashes. Überlegen Sie, wie std::unordered_set<std::tuple<int, int, …>> behandeln würde, Permutationen {1, 2, ..., 10}. Verwenden Sie stattdessen eine nicht-Kommutative combiner wie m * left + right, wo m ist eine große ungerade Zahl.

InformationsquelleAutor Mooing Duck

Mit C++20, ist es möglich, Fach-Ausdrücke und generische lambdas zu berechnen hash eines Tupel ohne Rekursion. Ich verlassen sich lieber auf std::hash<uintmax_t> anstatt manuell die Kombination von hashes:

#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 im sizeof(uintmax_t) * 4 - 1 ist optional, aber erscheint etwas zu verbessern hash-Verteilung. Diese Klasse kann verwendet werden, sowohl mit std::tuple und std::pair.

InformationsquelleAutor Vladimir Reshetnikov

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.