C ++ unordered_map mit einem benutzerdefinierten Klassentyp als Schlüssel

285

Ich versuche, eine benutzerdefinierte Klasse als Schlüssel für eine zu verwenden unordered_map, wie die folgende:

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

class node;
class Solution;

class Node {
public:
    int a;
    int b; 
    int c;
    Node(){}
    Node(vector<int> v) {
        sort(v.begin(), v.end());
        a = v[0];       
        b = v[1];       
        c = v[2];       
    }

    bool operator==(Node i) {
        if ( i.a==this->a && i.b==this->b &&i.c==this->c ) {
            return true;
        } else {
            return false;
        }
    }
};

int main() {
    unordered_map<Node, int> m;    

    vector<int> v;
    v.push_back(3);
    v.push_back(8);
    v.push_back(9);
    Node n(v);

    m[n] = 0;

    return 0;
}

G ++ gibt mir jedoch den folgenden Fehler:

In file included from /usr/include/c++/4.6/string:50:0,
                 from /usr/include/c++/4.6/bits/locale_classes.h:42,
                 from /usr/include/c++/4.6/bits/ios_base.h:43,
                 from /usr/include/c++/4.6/ios:43,
                 from /usr/include/c++/4.6/ostream:40,
                 from /usr/include/c++/4.6/iostream:40,
                 from 3sum.cpp:4:
/usr/include/c++/4.6/bits/stl_function.h: In member function bool std::equal_to<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = Node]’:
/usr/include/c++/4.6/bits/hashtable_policy.h:768:48:   instantiated from bool std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_M_compare(const _Key&, std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_Hash_code_type, std::__detail::_Hash_node<_Value, false>*) const [with _Key = Node, _Value = std::pair<const Node, int>, _ExtractKey = std::_Select1st<std::pair<const Node, int> >, _Equal = std::equal_to<Node>, _H1 = std::hash<Node>, _H2 = std::__detail::_Mod_range_hashing, std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_Hash_code_type = long unsigned int]’
/usr/include/c++/4.6/bits/hashtable.h:897:2:   instantiated from std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node* std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_M_find_node(std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node*, const key_type&, typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hash_code_type) const [with _Key = Node, _Value = std::pair<const Node, int>, _Allocator = std::allocator<std::pair<const Node, int> >, _ExtractKey = std::_Select1st<std::pair<const Node, int> >, _Equal = std::equal_to<Node>, _H1 = std::hash<Node>, _H2 = std::__detail::_Mod_range_hashing, _Hash = std::__detail::_Default_ranged_hash, _RehashPolicy = std::__detail::_Prime_rehash_policy, bool __cache_hash_code = false, bool __constant_iterators = false, bool __unique_keys = true, std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node = std::__detail::_Hash_node<std::pair<const Node, int>, false>, std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::key_type = Node, typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hash_code_type = long unsigned int]’
/usr/include/c++/4.6/bits/hashtable_policy.h:546:53:   instantiated from std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::mapped_type& std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::operator[](const _Key&) [with _Key = Node, _Pair = std::pair<const Node, int>, _Hashtable = std::_Hashtable<Node, std::pair<const Node, int>, std::allocator<std::pair<const Node, int> >, std::_Select1st<std::pair<const Node, int> >, std::equal_to<Node>, std::hash<Node>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, false, false, true>, std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::mapped_type = int]’
3sum.cpp:149:5:   instantiated from here
/usr/include/c++/4.6/bits/stl_function.h:209:23: error: passing const Node as this argument of bool Node::operator==(Node)’ discards qualifiers [-fpermissive]
make: *** [threeSum] Error 1

Ich denke, ich muss C ++ sagen, wie man eine Hash-Klasse erstellt Node, aber ich bin mir nicht ganz sicher, wie ich das machen soll. Wie kann ich diese Aufgaben ausführen?

Alfred Zhong
quelle
2
Das dritte Vorlagenargument ist die Hash-Funktion, die Sie angeben müssen.
Chrisaycock
3
cppreference hat ein einfaches und praktisches Beispiel dafür: en.cppreference.com/w/cpp/container/unordered_map/unordered_map
jogojapan

Antworten:

485

Um std::unordered_map(oder einen der anderen ungeordneten assoziativen Container) mit einem benutzerdefinierten Schlüsseltyp verwenden zu können, müssen Sie zwei Dinge definieren:

  1. Eine Hash-Funktion ; Dies muss eine Klasse sein, die operator()den Hashwert für ein Objekt vom Schlüsseltyp überschreibt und berechnet. Eine besonders einfache Möglichkeit besteht darin, die std::hashVorlage für Ihren Schlüsseltyp zu spezialisieren .

  2. Eine Vergleichsfunktion für Gleichheit ; Dies ist erforderlich, da sich der Hash nicht auf die Tatsache verlassen kann, dass die Hash-Funktion immer einen eindeutigen Hash-Wert für jeden einzelnen Schlüssel bereitstellt (dh, er muss in der Lage sein, mit Kollisionen umzugehen), sodass zwei gegebene Schlüssel verglichen werden können für eine genaue Übereinstimmung. Sie können dies entweder als überschreibende Klasse operator()oder als Spezialisierung von std::equaloder - am einfachsten von allen - durch Überladen implementierenoperator==() Ihres Schlüsseltyps (wie Sie es bereits getan haben).

Die Schwierigkeit bei der Hash-Funktion besteht darin, dass, wenn Ihr Schlüsseltyp aus mehreren Elementen besteht, die Hash-Funktion normalerweise Hash-Werte für die einzelnen Elemente berechnet und diese dann irgendwie zu einem Hash-Wert für das gesamte Objekt kombiniert. Für eine gute Leistung (dh wenige Kollisionen) sollten Sie sorgfältig überlegen, wie Sie die einzelnen Hashwerte kombinieren, um sicherzustellen, dass Sie nicht zu oft dieselbe Ausgabe für verschiedene Objekte erhalten.

Ein ziemlich guter Ausgangspunkt für eine Hash-Funktion ist einer, der Bitverschiebung und bitweises XOR verwendet, um die einzelnen Hash-Werte zu kombinieren. Nehmen wir zum Beispiel einen Schlüsseltyp wie diesen an:

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

Hier ist eine einfache Hash-Funktion (angepasst an die im cppreference-Beispiel für benutzerdefinierte Hash-Funktionen verwendete ):

namespace std {

  template <>
  struct hash<Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::size_t;
      using std::hash;
      using std::string;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
    }
  };

}

Mit dieser Option können Sie a std::unordered_mapfür den Schlüsseltyp instanziieren :

int main()
{
  std::unordered_map<Key,std::string> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}

Es wird automatisch std::hash<Key>wie oben für die Hashwertberechnungen definiert und die operator==als Member definierte Funktion Keyfür Gleichheitsprüfungen verwendet.

Wenn Sie die Vorlage nicht auf den stdNamespace spezialisieren möchten (obwohl dies in diesem Fall völlig legal ist), können Sie die Hash-Funktion als separate Klasse definieren und zur Liste der Vorlagenargumente für die Map hinzufügen:

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
    using std::size_t;
    using std::hash;
    using std::string;

    return ((hash<string>()(k.first)
             ^ (hash<string>()(k.second) << 1)) >> 1)
             ^ (hash<int>()(k.third) << 1);
  }
};

int main()
{
  std::unordered_map<Key,std::string,KeyHasher> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}

Wie definiere ich eine bessere Hash-Funktion? Wie oben erwähnt, ist es wichtig, eine gute Hash-Funktion zu definieren, um Kollisionen zu vermeiden und eine gute Leistung zu erzielen. Für ein wirklich gutes müssen Sie die Verteilung möglicher Werte aller Felder berücksichtigen und eine Hash-Funktion definieren, die diese Verteilung auf einen Raum möglicher Ergebnisse projiziert, der so breit und gleichmäßig wie möglich verteilt ist.

Das kann schwierig sein; Die obige XOR / Bit-Shifting-Methode ist wahrscheinlich kein schlechter Start. Für einen etwas besseren Start können Sie die Vorlage hash_valueund hash_combinefunction aus der Boost-Bibliothek verwenden. Ersteres verhält sich ähnlich wie std::hashbei Standardtypen (in letzter Zeit auch Tupel und andere nützliche Standardtypen); Letzteres hilft Ihnen, einzelne Hash-Werte zu einem zu kombinieren. Hier ist eine Neufassung der Hash-Funktion, die die Boost-Hilfsfunktionen verwendet:

#include <boost/functional/hash.hpp>

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
      using boost::hash_value;
      using boost::hash_combine;

      // Start with a hash value of 0    .
      std::size_t seed = 0;

      // Modify 'seed' by XORing and bit-shifting in
      // one member of 'Key' after the other:
      hash_combine(seed,hash_value(k.first));
      hash_combine(seed,hash_value(k.second));
      hash_combine(seed,hash_value(k.third));

      // Return the result.
      return seed;
  }
};

Und hier ist eine Umschreibung, die keinen Boost verwendet, aber eine gute Methode zum Kombinieren der Hashes verwendet:

namespace std
{
    template <>
    struct hash<Key>
    {
        size_t operator()( const Key& k ) const
        {
            // Compute individual hash values for first, second and third
            // http://stackoverflow.com/a/1646913/126995
            size_t res = 17;
            res = res * 31 + hash<string>()( k.first );
            res = res * 31 + hash<string>()( k.second );
            res = res * 31 + hash<int>()( k.third );
            return res;
        }
    };
}
jogojapan
quelle
11
Können Sie bitte erklären, warum es notwendig ist, die Bits zu verschieben KeyHasher?
Chani
45
Wenn Sie die Bits nicht verschoben hätten und zwei Zeichenfolgen gleich wären, würde das xor dazu führen, dass sie sich gegenseitig aufheben. Hash ("a", "a", 1) wäre also dasselbe wie Hash ("b", "b", 1). Auch die Reihenfolge spielt keine Rolle, daher ist Hash ("a", "b", 1) dasselbe wie Hash ("b", "a", 1).
Buge
1
Ich lerne gerade C ++ und eine Sache, mit der ich immer zu kämpfen habe, ist: Wo soll ich den Code ablegen? Ich habe std::hashwie Sie eine Spezialisierungsmethode für meinen Schlüssel geschrieben . Ich habe dies am Ende meiner Key.cpp-Datei eingefügt, erhalte jedoch die folgende Fehlermeldung : Error 57 error C2440: 'type cast' : cannot convert from 'const Key' to 'size_t' c:\program files (x86)\microsoft visual studio 10.0\vc\include\xfunctional. Ich vermute, dass der Compiler meine Hash-Methode nicht findet? Sollte ich meiner Key.h-Datei etwas hinzufügen?
Ben
4
@Ben Das Einfügen in die .h-Datei ist korrekt. std::hashist eigentlich keine Struktur, sondern eine Vorlage (Spezialisierung) für eine Struktur . Es ist also keine Implementierung - es wird in eine Implementierung umgewandelt, wenn der Compiler sie benötigt. Vorlagen sollten immer in Header-Dateien gespeichert werden. Siehe auch stackoverflow.com/questions/495021/…
jogojapan
3
@nightfury find()gibt einen Iterator zurück und dieser Iterator zeigt auf einen "Eintrag" der Karte. Ein Eintrag besteht std::pairaus Schlüssel und Wert. Wenn Sie dies tun auto iter = m6.find({"John","Doe",12});, erhalten Sie den Schlüssel iter->firstund den Wert (dh die Zeichenfolge "example") iter->second. Wenn Sie die Zeichenfolge direkt möchten, können Sie entweder m6.at({"John","Doe",12})(das löst eine Ausnahme aus, wenn der Schlüssel nicht beendet wird) oder m6[{"John","Doe",12}](das einen leeren Wert erzeugt, wenn der Schlüssel nicht vorhanden ist) verwenden.
Jogojapan
16

Ich denke, Jogojapan gab eine sehr gute und erschöpfende Antwort . Sie sollten es sich unbedingt ansehen, bevor Sie meinen Beitrag lesen. Ich möchte jedoch Folgendes hinzufügen:

  1. Sie können eine Vergleichsfunktion für eine unordered_mapseparat definieren, anstatt den Gleichheitsvergleichsoperator ( operator==) zu verwenden. Dies kann beispielsweise hilfreich sein, wenn Sie letzteres verwenden möchten, um alle Elemente zweier NodeObjekte miteinander zu vergleichen, jedoch nur einige bestimmte Elemente als Schlüssel eines unordered_map.
  2. Sie können auch Lambda-Ausdrücke verwenden, anstatt die Hash- und Vergleichsfunktionen zu definieren.

Alles in allem Nodekönnte der Code für Ihre Klasse wie folgt geschrieben werden:

using h = std::hash<int>;
auto hash = [](const Node& n){return ((17 * 31 + h()(n.a)) * 31 + h()(n.b)) * 31 + h()(n.c);};
auto equal = [](const Node& l, const Node& r){return l.a == r.a && l.b == r.b && l.c == r.c;};
std::unordered_map<Node, int, decltype(hash), decltype(equal)> m(8, hash, equal);

Anmerkungen:

  • Ich habe gerade die Hashing-Methode am Ende von Jogojapans Antwort wiederverwendet, aber Sie können die Idee für eine allgemeinere Lösung hier finden (wenn Sie Boost nicht verwenden möchten).
  • Mein Code ist vielleicht etwas zu klein. Eine etwas besser lesbare Version finden Sie in diesem Code auf Ideone .
hupen
quelle
Woher kamen die 8 und was bedeutet das?
AndiChin
@WhalalalalalalaCHen: Bitte schauen Sie sich die Dokumentation des unordered_mapKonstruktors an . Das 8repräsentiert die sogenannte "Bucket Count". Ein Bucket ist ein Slot in der internen Hash-Tabelle des Containers. unordered_map::bucket_countWeitere Informationen finden Sie z .
Hupen Sie
@ WalalalalalalaCHen: Ich habe 8zufällig ausgewählt. Abhängig von dem Inhalt, den Sie in Ihrem speichern möchten, unordered_mapkann die Anzahl der Buckets die Leistung des Containers beeinträchtigen.
Hupen Sie