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?
Antworten:
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: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, diestd::hash
Vorlage für Ihren Schlüsseltyp zu spezialisieren .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 vonstd::equal
oder - 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:
Hier ist eine einfache Hash-Funktion (angepasst an die im cppreference-Beispiel für benutzerdefinierte Hash-Funktionen verwendete ):
Mit dieser Option können Sie a
std::unordered_map
für den Schlüsseltyp instanziieren :Es wird automatisch
std::hash<Key>
wie oben für die Hashwertberechnungen definiert und dieoperator==
als Member definierte FunktionKey
für Gleichheitsprüfungen verwendet.Wenn Sie die Vorlage nicht auf den
std
Namespace 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: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_value
undhash_combine
function aus der Boost-Bibliothek verwenden. Ersteres verhält sich ähnlich wiestd::hash
bei 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:Und hier ist eine Umschreibung, die keinen Boost verwendet, aber eine gute Methode zum Kombinieren der Hashes verwendet:
quelle
KeyHasher
?std::hash
wie 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?std::hash
ist 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/…find()
gibt einen Iterator zurück und dieser Iterator zeigt auf einen "Eintrag" der Karte. Ein Eintrag bestehtstd::pair
aus Schlüssel und Wert. Wenn Sie dies tunauto iter = m6.find({"John","Doe",12});
, erhalten Sie den Schlüsseliter->first
und den Wert (dh die Zeichenfolge"example"
)iter->second
. Wenn Sie die Zeichenfolge direkt möchten, können Sie entwederm6.at({"John","Doe",12})
(das löst eine Ausnahme aus, wenn der Schlüssel nicht beendet wird) oderm6[{"John","Doe",12}]
(das einen leeren Wert erzeugt, wenn der Schlüssel nicht vorhanden ist) verwenden.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:
unordered_map
separat definieren, anstatt den Gleichheitsvergleichsoperator (operator==
) zu verwenden. Dies kann beispielsweise hilfreich sein, wenn Sie letzteres verwenden möchten, um alle Elemente zweierNode
Objekte miteinander zu vergleichen, jedoch nur einige bestimmte Elemente als Schlüssel einesunordered_map
.Alles in allem
Node
könnte der Code für Ihre Klasse wie folgt geschrieben werden:Anmerkungen:
quelle
unordered_map
Konstruktors an . Das8
repräsentiert die sogenannte "Bucket Count". Ein Bucket ist ein Slot in der internen Hash-Tabelle des Containers.unordered_map::bucket_count
Weitere Informationen finden Sie z .8
zufällig ausgewählt. Abhängig von dem Inhalt, den Sie in Ihrem speichern möchten,unordered_map
kann die Anzahl der Buckets die Leistung des Containers beeinträchtigen.