Wie implementiert man eine generische Hash-Funktion für Tupel in ungeordneten Sammlungen?

Generische Hash-Funktion für Tupel in ungeordneten Sammlungen

Die Container std::unordered_map und std::unordered_set ermöglichen ein effizientes Suchen und Einfügen von Elementen basierend auf ihren gehashten Werten. Allerdings kann die Verwendung von Tupeln als Schlüssel in diesen Sammlungen ohne Definition einer benutzerdefinierten Hash-Funktion zu unerwartetem Verhalten führen.

Um dies zu beheben, besteht ein Ansatz darin, manuell eine Hash-Funktion für den spezifischen Tupeltyp zu definieren, wie zum Beispiel:

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

Obwohl dieser Ansatz funktioniert, kann es mühsam sein, Hash-Funktionen für jeden verwendeten Tupeltyp zu definieren. Um dies zu automatisieren, kann eine generische Hash-Funktion wie folgt implementiert werden:

#include <tuple>

namespace std {
  namespace {

    // Code derived from Boost
    template<class T>
    inline void hash_combine(std::size_t& seed, T const& v) { ... }

    // Recursive template code from Matthieu M.
    template<class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
    struct HashValueImpl { ... };

  }

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

Diese Funktion nutzt die argumentabhängige Namenssuche (ADL), um dem Compiler zu ermöglichen, automatisch die richtige Hash-Implementierung basierend auf dem Tupeltyp auszuwählen .

Standardkonforme Lösung

Es ist erwähnenswert, dass die Definition nicht standardmäßiger Funktionen in der std-Namespace ist undefiniertes Verhalten. Für eine standardkonforme Lösung kann ein benutzerdefinierter Namespace erstellt und zum Definieren der Hash-Funktion verwendet werden:

namespace my_hash {

  // Forward non-tuple types to the std::hash
  template<typename TT>
  struct hash { ... };

  // Provide the optimized hash for tuples
  template<typename... TT>
  struct hash<std::tuple<TT...>> { ... };

}

Bei Verwendung dieser Lösung muss die ungeordnete Sammlung explizit auf die benutzerdefinierte Hash-Implementierung wie folgt verweisen:

unordered_set<
  std::tuple<double, int>,
  std::hash<std::tuple<double, int>>,
  std::equal_to<std::tuple<double, int>>
> test;  

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