Wie können Sie eine generische Hash-Funktion für Tupel in ungeordneten Sammlungen in C implementieren?

Generisches Hashing für Tupel in ungeordneten Sammlungen

Im Bereich der C-Standardbibliotheken das Konzept von Tupeln und ihre Verwendung als Schlüssel in ungeordneten Sammlungen wie std::unordered_map und std::unordered_set können eine Herausforderung darstellen. Standardmäßig ist für Tupel keine generische Hash-Funktion definiert, sodass Entwickler die mühsame Aufgabe haben, eine solche manuell zu definieren.

Die Notwendigkeit einer generischen Lösung

Das Definieren einer benutzerdefinierten Hash-Funktion für Tupel kann umständlich und fehleranfällig sein. Um dieses Problem anzugehen, suchen Entwickler häufig nach einer allgemeineren Lösung, die den Prozess automatisiert.

Ein standardkonformer Ansatz

Während der Standard nicht explizit eine generische Hash-Funktion für Tupel bereitstellt, ist dies ein Standard -konformer Ansatz ist verfügbar. Durch das Verschieben des Codes in einen benutzerdefinierten Namespace ist es möglich, undefiniertes Verhalten zu vermeiden, das mit der Spezialisierung auf den std-Namespace verbunden ist.

Bei diesem Ansatz wird ein benutzerdefinierter Namespace, hash_tuple, mit seiner eigenen Implementierung der Hash-Funktion erstellt . Diese Implementierung sendet Nicht-Tupel-Typen an die Funktion std::hash.

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

Der rekursive Vorlagencode wird geändert, um hash_tuple::hash anstelle von std::hash:

namespace hash_tuple{
    namespace
    {
        template <class T>
        inline void hash_combine(std::size_t&amp; seed, T const&amp; v)
        {
            seed ^= hash_tuple::hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }
    }
}

Schließlich wird die Standard-Vorlagenspezialisierung im hash_tuple platziert Namespace:

namespace hash_tuple{
    template <typename ... TT>
    struct hash<std::tuple<TT...>> 
    {
        size_t
        operator()(std::tuple<TT...> const&amp; tt) const
        {                                              
            size_t seed = 0;                             
            HashValueImpl<std::tuple<TT...> >::apply(seed, tt);    
            return seed;                                 
        }                                              
    };
}

Um diesen Ansatz zu verwenden, müssen Benutzer den Namensraum hash_tuple in ihren ungeordneten Sammlungsdeklarationen angeben:

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

Obwohl diese Lösung standardkonform ist, erfordert sie die Angabe des Namensraums für jede ungeordnete Sammelerklärung.

Ein nicht standardmäßiger Ansatz

Ein alternativer Ansatz, nämlich Nicht mit dem C-Standard kompatibel, besteht darin, den generischen Hash-Funktionscode im std-Namespace zu platzieren. Dies ermöglicht die argumentabhängige Suche (ADL), um automatisch die richtige Hash-Implementierung zu finden.

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&amp; seed, T const&amp; 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&amp; seed, Tuple const&amp; 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&amp; seed, Tuple const&amp; tuple)
          {
            hash_combine(seed, std::get<0>(tuple));
          }
        };
    }

    template <typename ... TT>
    struct hash<std::tuple<TT...>> 
    {
        size_t
        operator()(std::tuple<TT...> const&amp; tt) const
        {                                              
            size_t seed = 0;                             
            HashValueImpl<std::tuple<TT...> >::apply(seed, tt);    
            return seed;                                 
        }                                              

    };
}

Mit diesem Ansatz bleibt die Syntax ungeordneter Sammlungen einfacher:

unordered_set<tuple<double, int> > test_set;

Diese Technik trägt jedoch das Risiko undefinierten Verhaltens aufgrund der Spezialisierung im std-Namespace.

Fazit

Das Generikum Das Hashing von Tupeln in ungeordneten Sammlungen ist ein nicht triviales Problem, das eine benutzerdefinierte Implementierung erfordern kann. Sowohl die in diesem Artikel beschriebenen standardkonformen als auch nicht standardisierten Ansätze bieten praktikable Lösungen. Letztendlich hängt die Wahl zwischen diesen Ansätzen von den Anforderungen des Entwicklers und seiner Toleranz gegenüber potenziell undefiniertem Verhalten ab.

Das obige ist der detaillierte Inhalt vonWie können Sie eine generische Hash-Funktion für Tupel in ungeordneten Sammlungen in C implementieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!