Wie spezialisiere ich std :: hash & lt; Key & gt; :: operator () für einen benutzerdefinierten Typ in ungeordneten Containern?

Unterstützt user-defined key types in std::unordered_set<Key> und std::unordered_map<Key, Value>
man hat operator==(Key, Key) - und ein hash-Funktor:

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;

Wäre es bequemer zu schreiben, nur std::unordered_set<X>
mit einem Standard-hash - für Typ X,
wie für die Arten kommen zusammen mit dem compiler und Bibliothek.
Nach Anhörung

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

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 
}

Gegeben compiler-Unterstützung für C++11 ist noch experimentellen---ich habe nicht versucht Clang---, dies sind meine Fragen:

  1. Ist es legal solch eine Spezialisierung namespace std? Ich habe gemischte Gefühle darüber.
  2. Welche der std::hash<X>::operator() Versionen, wenn überhaupt, ist kompatibel mit standard C++11?
  3. Gibt es eine portable Möglichkeit, es zu tun?

InformationsquelleAutor der Frage René Richter | 2011-11-16

  1. 106

    Sie sind ausdrücklich erlaubt und erwünscht hinzufügen Spezialisierungen namespace std*. Die richtige (und im Grunde einzige) Weg, um einen hash-Funktion ist diese:

    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 möglicherweise in Betracht zu unterstützen sind std::lessstd::equal_to und std::swap.)

    *) solange eine der beteiligten Arten ist Benutzer-definiert, nehme ich an.

    InformationsquelleAutor der Antwort Kerrek SB

  2. 6

    Meine Wette wäre auf die Hash-template-argument für die unordered_map/unorder_set/... Klassen:

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

    Natürlich

    • hashX könnte genauso gut eine Globale statische Funktion
    • im zweiten Fall, könnte passieren, dass
      • die altmodische functor-Objekt (struct Xhasher { size_t operator(const X&) const; };)
      • std::hash<X>()
      • die bind-Ausdruck der Befriedigung der Signatur
        -

    InformationsquelleAutor der Antwort sehe

  3. 4

    @Kerrek SB hat unter 1) und 3).

    2), obwohl g++ und VC10 erklären std::hash<T>::operator() mit unterschiedlichen Signaturen, beide Bibliothek Implementierungen sind Standard-konform.

    Die der Standard nicht spezifiziert, die Mitglieder der std::hash<T>. Es sagt nur, dass jeder solche Spezialisierung erfüllen müssen, die gleichen "Hash" Anforderungen, die für die zweite Vorlage-argument von std::unordered_set und so weiter. Nämlich:

    • Hash-Typ H ist ein function-Objekt, mit mindestens einem argument type Key.
    • H kopieren bebaubar.
    • H zerstörbar ist.
    • Wenn h ist ein Ausdruck vom Typ H oder const Hund k ist ein Ausdruck für eine Art Cabrio zu (eventuell const) Keydann h(k) ist ein Gültiger Ausdruck mit Typ -size_t.
    • Wenn h ist ein Ausdruck vom Typ H oder const Hund u ist ein lvalue des Typs Keydann h(u) ist ein Gültiger Ausdruck mit Typ - size_t die nicht ändern u.

    InformationsquelleAutor der Antwort aschepler

Schreibe einen Kommentar