Usiłuję użyć niestandardowej klasy jako klucza do unordered_map
, jak poniżej:
#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;
}
Jednak g ++ daje mi następujący błąd:
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
Chyba potrzebuję powiedzieć C ++, jak haszować klasę Node
, jednak nie jestem do końca pewien, jak to zrobić. Jak mogę wykonać te zadania?
Odpowiedzi:
Aby móc używać
std::unordered_map
(lub jednego z innych nieuporządkowanych kontenerów asocjacyjnych) z kluczem zdefiniowanym przez użytkownika, musisz zdefiniować dwie rzeczy:Funkcja skrótu ; musi to być klasa, która zastępuje
operator()
i oblicza wartość skrótu, biorąc pod uwagę obiekt typu klucza. Jednym szczególnie prostym sposobem na to jest specjalizacjastd::hash
szablonu dla twojego typu klucza.Funkcja porównania dla równości ; jest to wymagane, ponieważ skrót nie może polegać na tym, że funkcja skrótu zawsze zapewnia unikalną wartość skrótu dla każdego odrębnego klucza (tj. musi być w stanie poradzić sobie z kolizjami), więc musi mieć sposób na porównanie dwóch podanych kluczy dla dokładnego dopasowania. Możesz to zaimplementować albo jako klasę, która zastępuje
operator()
, albo specjalizacjęstd::equal
, albo - najłatwiej ze wszystkich - przez przeciążenieoperator==()
dla twojego typu klucza (jak to już zrobiłeś).Trudność związana z funkcją skrótu polega na tym, że jeśli typ klucza składa się z kilku elementów, zazwyczaj funkcja skrótu oblicza wartości skrótu dla poszczególnych elementów, a następnie łączy je w jedną wartość skrótu dla całego obiektu. Aby uzyskać dobrą wydajność (tj. Kilka kolizji), powinieneś dokładnie przemyśleć, jak łączyć poszczególne wartości skrótu, aby uniknąć zbyt częstego uzyskiwania tego samego wyniku dla różnych obiektów.
Dość dobrym punktem wyjścia dla funkcji skrótu jest taki, który wykorzystuje przesunięcie bitów i bitowe XOR do łączenia poszczególnych wartości skrótu. Na przykład zakładając taki typ klucza:
Oto prosta funkcja skrótu (dostosowana z funkcji użytej w przykładzie cppreference dla funkcji skrótu zdefiniowanych przez użytkownika ):
Dzięki temu możesz utworzyć instancję
std::unordered_map
dla typu klucza:Będzie automatycznie używał,
std::hash<Key>
jak zdefiniowano powyżej, do obliczeń wartości skrótu ioperator==
zdefiniowanej jako funkcja elementuKey
dla kontroli równości.Jeśli nie chcesz specjalizować szablonu w
std
przestrzeni nazw (chociaż w tym przypadku jest to całkowicie legalne), możesz zdefiniować funkcję skrótu jako oddzielną klasę i dodać ją do listy argumentów szablonu dla mapy:Jak zdefiniować lepszą funkcję skrótu? Jak wspomniano powyżej, zdefiniowanie dobrej funkcji skrótu jest ważne, aby uniknąć kolizji i uzyskać dobrą wydajność. Dla prawdziwego dobra należy wziąć pod uwagę rozkład możliwych wartości wszystkich pól i zdefiniować funkcję skrótu, która rzutuje tę dystrybucję na przestrzeń możliwych wyników tak szeroką i równomiernie rozłożoną, jak to możliwe.
To może być trudne; powyższa metoda zmiany bitów / XOR prawdopodobnie nie jest zła. Aby nieco lepiej zacząć, możesz użyć szablonu
hash_value
ihash_combine
funkcji z biblioteki Boost. Ten pierwszy działa w podobny sposób, jak wstd::hash
przypadku standardowych typów (ostatnio także krotek i innych przydatnych standardowych typów); ten ostatni pomaga łączyć poszczególne wartości skrótu w jedną. Oto przepis funkcji haszującej, która korzysta z funkcji pomocniczych Boost:A oto przepisanie, które nie używa wzmocnienia, ale używa dobrej metody łączenia skrótów:
źródło
KeyHasher
?std::hash
metodę dla mojego klucza. Ja to w dolnej części mojego pliku Key.cpp ale otrzymuję następujący błąd: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
. Zgaduję, że kompilator nie znajduje mojej metody mieszania? Czy powinienem coś dodawać do mojego pliku Key.h?std::hash
nie jest w rzeczywistości struct, ale szablonem (specjalizacją) dla struct . Więc to nie jest implementacja - zostanie przekształcona w implementację, gdy kompilator będzie jej potrzebował. Szablony powinny zawsze wchodzić do plików nagłówkowych. Zobacz także stackoverflow.com/questions/495021/…find()
zwraca iterator, który wskazuje na „wejście” mapy. Wpisstd::pair
składa się z klucza i wartości. Więc jeśli to zrobiszauto iter = m6.find({"John","Doe",12});
, dostaniesz klucziter->first
i wartość (tj. Ciąg"example"
) witer->second
. Jeśli chcesz bezpośrednio napisu, możesz użyćm6.at({"John","Doe",12})
(spowoduje to wyjątek, jeśli klucz nie wyjdzie) lubm6[{"John","Doe",12}]
(utworzy pustą wartość, jeśli klucz nie istnieje).Myślę, że jogojapan udzielił bardzo dobrej i wyczerpującej odpowiedzi . Zdecydowanie powinieneś rzucić na to okiem, zanim przeczytasz mój post. Chciałbym jednak dodać następujące:
unordered_map
osobno, zamiast używać operatora porównania równości (operator==
). Może to być pomocne, na przykład, jeśli chcesz użyć tego ostatniego do porównania wszystkich członków dwóchNode
obiektów ze sobą, ale tylko niektórych określonych członków jako klucza anunordered_map
.Podsumowując, dla twojej
Node
klasy kod można zapisać w następujący sposób:Uwagi:
źródło
unordered_map
konstruktora .8
Reprezentuje tzw „Count wiadro”. Wiadro to miejsce w wewnętrznej tabeli mieszającej kontenera, patrz np.unordered_map::bucket_count
Więcej informacji.8
losowo. W zależności od zawartości, którą chcesz przechowywaćunordered_map
, liczba segmentów może wpływać na wydajność kontenera.