webentwicklung-frage-antwort-db.com.de

Wie spezialisiere ich std :: hash <Key> :: operator () für einen benutzerdefinierten Typ in ungeordneten Containern?

Um benutzerdefinierte Schlüsseltypen in std::unordered_set<Key> Und std::unordered_map<Key, Value> Zu unterstützen, müssen Sie operator==(Key, Key) und einen Hash-Funktor bereitstellen:

struct X { int id; /* ... */ };
bool operator==(X a, X b) { return a.id == b.id; }

struct MyHash {
  size_t operator()(const X& x) const { return std::hash<int>()(x.id); }
};

std::unordered_set<X, MyHash> s;

Es wäre bequemer, nur std::unordered_set<X> Mit einem Standard-Hash für den Typ X zu schreiben, wie es für die Typen der Fall ist, die mitkommen mit dem Compiler und der Bibliothek. Nach Rücksprache mit

  • C++ Standard Entwurf N3242 §20.8.12 [unord.hash] und §17.6.3.4 [hash.requirements],
  • Boost.Unordered
  • g ++ include\c++\4.7.0\bits\functional_hash.h
  • VC10 include\xfunctional
  • verschiedene verwandte Frage s in Stack Overflow

es scheint möglich zu sein, std::hash<X>::operator() zu spezialisieren:

namespace std { // argh!
  template <>
  inline size_t 
  hash<X>::operator()(const X& x) const { return hash<int>()(x.id); } // works for MS VC10, but not for g++
  // or
  // hash<X>::operator()(X x) const { return hash<int>()(x.id); }     // works for g++ 4.7, but not for VC10 
}

Die gegebene Compiler-Unterstützung für C++ 11 ist noch experimentell. Ich habe Clang nicht ausprobiert. Dies sind meine Fragen:

  1. Ist es zulässig, dem Namespace std eine solche Spezialisierung hinzuzufügen? Ich habe gemischte Gefühle.

  2. Welche der std::hash<X>::operator() -Versionen entspricht, falls vorhanden, dem C++ 11-Standard?

  3. Gibt es eine tragbare Möglichkeit, dies zu tun?

c++hashc++11unordered-mapunordered-set
95
René Richter

Es ist Ihnen ausdrücklich gestattet und empfohlen, Spezialisierungen zum Namespace std * hinzuzufügen. Die korrekte (und grundsätzlich einzige) Möglichkeit, eine Hash-Funktion hinzuzufügen, ist folgende:

namespace std {
  template <> struct hash<Foo>
  {
    size_t operator()(const Foo & x) const
    {
      /* your code here, e.g. "return hash<int>()(x.value);" */
    }
  };
}

(Andere beliebte Spezialisierungen, die Sie unterstützen könnten, sind std::less, std::equal_to und std::swap.)

*) Ich nehme an, solange einer der beteiligten Typen benutzerdefiniert ist.

119
Kerrek SB

Meine Wette wäre auf das Hash-Template-Argument für die Klassen unordered_map/unorder_set/...:

#include <unordered_set>
#include <functional>

struct X 
{
    int x, y;
    std::size_t gethash() const { return (x*39)^y; }
};

typedef std::unordered_set<X, std::size_t(*)(const X&)> Xunset;
typedef std::unordered_set<X, std::function<std::size_t(const X&)> > Xunset2;

int main()
{
    auto hashX = [](const X&x) { return x.gethash(); };

    Xunset  my_set (0, hashX);
    Xunset2 my_set2(0, hashX); // if you prefer a more flexible set typedef
}

Na sicher

  • hashX könnte genauso gut eine globale statische Funktion sein
  • im zweiten Fall könnten Sie das
    • das altmodische functor Objekt (struct Xhasher { size_t operator(const X&) const; };)
    • std::hash<X>()
    • jeder Bindungsausdruck, der die Signatur erfüllt -
6
sehe

@Kerrek SB hat 1) und 3) abgedeckt.

2) Obwohl g ++ und VC10 std::hash<T>::operator() mit unterschiedlichen Signaturen deklarieren, sind beide Bibliotheksimplementierungen Standard-kompatibel.

Der Standard spezifiziert nicht die Mitglieder von std::hash<T>. Es heißt nur, dass jede solche Spezialisierung die gleichen "Hash" -Anforderungen erfüllen muss, die für das zweite Template-Argument von std::unordered_set Usw. benötigt werden. Nämlich:

  • Hash-Typ H ist ein Funktionsobjekt mit mindestens einem Argumenttyp Key.
  • H ist kopierfähig.
  • H ist zerstörbar.
  • Wenn h ein Ausdruck vom Typ H oder const H Ist und k ein Ausdruck eines Typs ist, der konvertierbar ist in (möglicherweise const) Key, dann h(k) ist ein gültiger Ausdruck mit dem Typ size_t.
  • Wenn h ein Ausdruck vom Typ H oder const H Ist und u ein Wert vom Typ Key ist, dann h(u) ist ein gültiger Ausdruck vom Typ size_t, der u nicht ändert.
4
aschepler