Wie kann ich Tupel als Schlüssel in ungeordneten Karten verwenden, ohne eine benutzerdefinierte Hash-Funktion zu schreiben?

Verwenden von Tupeln in ungeordneten Karten ohne benutzerdefinierte Hash-Funktion

Sie können erwarten, dass std::unordered_map mühelos mit Tupelschlüsseln funktioniert. Es erfordert jedoch die Definition einer Hash-Funktion für Tupel, wie unten gezeigt:

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

Dieser Prozess kann mühsam werden, was zu der Frage führt, ihn für C 0x-Tupel zu automatisieren, ohne auf verschiedene Vorlagen zurückzugreifen.

Mit dem folgenden Ansatz können alle C 0x-Tupel, die Standard-Hashable-Typen enthalten, ohne zusätzlichen Aufwand Teil von unordered_map und unordered_set werden:

#include <tuple>
namespace std {
    namespace {
        template <class T>
        inline void hash_combine(std::size_t& seed, T const& v) {
            // Modified from Boost
            seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        }

        // Recursive template for hashing tuples
        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;
        }
    };
}

Durch Platzieren der Funktion im std-Namespace ist sie über das Argument zugänglich. Abhängige Namenssuche (ADL).

Standardkonformer Code

Das Spezialisieren von Objekten im std-Namespace ist undefiniertes Verhalten. Verschieben Sie daher für eine standardkonforme Lösung den Code in einen separaten Namespace und verzichten Sie auf die Bequemlichkeit von ADL:

namespace hash_tuple {

// Forward non-tuple types to std::hash
template <class TT>
struct hash {
    size_t
    operator()(TT const& tt) const {
        return std::hash<TT>()(tt);
    }
};

// Hash function combining values in a tuple
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));
    }
};

// Hash function for tuples
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;
    }
};
} // namespace hash_tuple

Deklarieren Sie eine Hash-Implementierung innerhalb des hash_tuple-Namespace, um alle Nicht-Tupel-Typen an std weiterzuleiten: :hash und ändern Sie hash_combine, um hash_tuple::hash anstelle von std::hash zu verwenden. Platzieren Sie den verbleibenden Code im Namespace hash_tuple.

Um diese Lösung zu verwenden, müssen Sie den folgenden Code einschließen, der auf die Bequemlichkeit von ADL verzichtet:

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

Das obige ist der detaillierte Inhalt vonWie kann ich Tupel als Schlüssel in ungeordneten Karten verwenden, ohne eine benutzerdefinierte Hash-Funktion zu schreiben?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!