C ++ unordered_map verwendet einen benutzerdefinierten Klassentyp als Schlüssel
Ich versuche, verwenden Sie eine benutzerdefinierte Klasse als Schlüssel für unordered_map, wie die folgenden,
#include <iostream>
#include <algorithm>
#include <unordered_map>
//#include <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;
}
Ich glaube, ich muss das sagen, C++, wie hash-Klasse Knoten, allerdings bin ich mir nicht ganz sicher, wie es zu tun. Gibt es irgendein Beispiel für diese Art von Aufgaben?
Im folgenden wird der Fehler von g++:
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
InformationsquelleAutor der Frage Alfred Zhong | 2013-06-10
Du musst angemeldet sein, um einen Kommentar abzugeben.
Nutzen zu können
std::unordered_map
(oder einer der anderen ungeordnete assoziative Container) mit einer user-defined-Taste-geben, die Sie brauchen, um zu definieren, sind zwei Dinge:Einen hash-Funktion; dieser muss eine Klasse sein, überschreibt
operator()
und berechnet den hash-Wert eines Objekts der key-Typ. Eine besonders geradlinige Art und Weise dies zu tun ist, spezialisieren sich diestd::hash
Vorlage für Ihre Schlüssel-Typ.Einen Vergleich-Funktion für die Gleichstellung; dies ist erforderlich, da der Hashwert kann nicht auf die Tatsache stützen, dass die hash-Funktion immer einen eindeutigen hash-Wert für jeden eindeutigen Schlüssel (D. H., es muss in der Lage sein Umgang mit Kollisionen), so muss es eine Möglichkeit zum Vergleich von zwei bestimmten Tasten für eine exakte übereinstimmung. Implementieren Sie diese entweder als eine Klasse, überschreibt
operator()
oder als Spezialisierung vonstd::equal
oder – einfachste von allen – durch überlastungoperator==()
für Ihren Schlüssel geben (wie Sie es bereits).Die Schwierigkeit, mit der hash-Funktion ist, dass, wenn Sie Ihre Schlüssel-Typ besteht aus mehreren Mitgliedern, werden Sie in der Regel die hash-Funktion berechnet hash-Werte für die einzelnen Mitglieder, und dann irgendwie kombinieren Sie in einer hash-Werts für das gesamte Objekt. Für eine gute Leistung (d.h., wenige Kollisionen) sollten Sie sorgfältig darüber nachdenken, wie man kombinieren die einzelnen hash-Werte, um sicherzustellen, dass Sie vermeiden, immer die gleiche Ausgabe für verschiedene Objekte zu oft.
Ein ziemlich guter Ausgangspunkt für eine hash-Funktion ist eine, die verwendet bit-Verschiebung und bitweise XOR-Verknüpfung zu kombinieren, die die einzelnen hash-Werte. Zum Beispiel, vorausgesetzt, eine key-Art wie dieses:
Hier ist eine einfache hash-Funktion (angepasst an die in der cppreference Beispiel für Benutzer-definierte hash-Funktionen):
In diesem Ort, können Sie instanziieren ein
std::unordered_map
für den Schlüssel-Typ:Wird es automatisch
std::hash<Key>
wie oben definiert für die hash-Wert-Berechnungen, und dieoperator==
definiert als member-Funktion derKey
für Gleichheit überprüft.Wenn Sie nicht wollen, sich zu spezialisieren Vorlage innerhalb der
std
namespace (obwohl es vollkommen legal ist, in diesem Fall), können Sie definieren die hash-Funktion als eine separate Klasse, und fügen Sie dem template-argument-list für die map:So definieren Sie eine bessere hash-Funktion? Wie oben schon gesagt, die Definition eines guten hash-Funktion ist wichtig, um Kollisionen zu vermeiden und bekommen eine gute Leistung. Für einen wirklich guten ein, die Sie benötigen zu berücksichtigen, die Verteilung der möglichen Werte aller Felder und definieren Sie eine hash-Funktion, die Projekte, die Verbreitung auf einen Raum von möglichen Ergebnissen, wie breit und gleichmäßig wie möglich.
Dies kann schwierig sein; das XOR - /bit-shifting-Methode oben ist wahrscheinlich kein schlechter start. Für einen etwas besseren start, können Sie die
hash_value
undhash_combine
- funktionsvorlage aus der Boost-library. Der ehemalige fungiert in einer ähnlichen Weise wiestd::hash
für standard-Typen (neuerdings auch Tupel und andere nützliche standard-Typen); die beiden letzteren hilft Ihnen, kombinieren Sie die einzelnen hash-Werte in einem. Hier ist ein umschreiben der hash-Funktion mit der Boost-helper-Funktionen:Und hier ist ein umschreiben nicht verwenden, steigern, noch verwendet gute Methode der Kombination des hashes:
InformationsquelleAutor der Antwort jogojapan