J'essaie d'utiliser une classe personnalisée comme clé pour un unordered_map
, comme suit:
#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;
}
Cependant, g ++ me donne l'erreur suivante:
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
Je suppose que j'ai besoin de dire à C ++ comment hacher la classe Node
, cependant, je ne sais pas trop comment le faire. Comment puis-je accomplir ces tâches?
Réponses:
Pour pouvoir utiliser
std::unordered_map
(ou l'un des autres conteneurs associatifs non ordonnés) avec un type de clé défini par l'utilisateur, vous devez définir deux choses:Une fonction de hachage ; il doit s'agir d'une classe qui remplace
operator()
et calcule la valeur de hachage en fonction d'un objet de type clé. Une façon particulièrement simple de procéder consiste à spécialiser lestd::hash
modèle pour votre type de clé.Une fonction de comparaison pour l'égalité ; cela est nécessaire car le hachage ne peut pas compter sur le fait que la fonction de hachage fournira toujours une valeur de hachage unique pour chaque clé distincte (c'est-à-dire qu'elle doit pouvoir gérer les collisions), elle a donc besoin d'un moyen de comparer deux clés données pour une correspondance exacte. Vous pouvez l'implémenter soit en tant que classe qui remplace
operator()
, soit en tant que spécialisationstd::equal
, ou - le plus simple de tous - en surchargeantoperator==()
votre type de clé (comme vous l'avez déjà fait).La difficulté avec la fonction de hachage est que si votre type de clé se compose de plusieurs membres, vous aurez généralement la fonction de hachage calculer les valeurs de hachage pour les membres individuels, puis les combiner en quelque sorte en une seule valeur de hachage pour l'objet entier. Pour de bonnes performances (c.-à-d. Peu de collisions), vous devez réfléchir soigneusement à la façon de combiner les valeurs de hachage individuelles pour vous assurer d’éviter d’obtenir trop souvent la même sortie pour différents objets.
Un assez bon point de départ pour une fonction de hachage est celui qui utilise le décalage de bits et XOR au niveau du bit pour combiner les valeurs de hachage individuelles. Par exemple, en supposant un type de clé comme celui-ci:
Voici une fonction de hachage simple (adaptée de celle utilisée dans l' exemple cppreference pour les fonctions de hachage définies par l'utilisateur ):
Avec cela en place, vous pouvez instancier un
std::unordered_map
pour le type de clé:Il sera automatiquement utilisé
std::hash<Key>
comme défini ci-dessus pour les calculs de valeur de hachage, etoperator==
défini comme fonction membre deKey
pour les contrôles d'égalité.Si vous ne souhaitez pas spécialiser le modèle dans l'
std
espace de noms (bien que cela soit parfaitement légal dans ce cas), vous pouvez définir la fonction de hachage en tant que classe distincte et l'ajouter à la liste des arguments de modèle pour la carte:Comment définir une meilleure fonction de hachage? Comme indiqué ci-dessus, la définition d'une bonne fonction de hachage est importante pour éviter les collisions et obtenir de bonnes performances. Pour un bien réel, vous devez prendre en compte la distribution des valeurs possibles de tous les champs et définir une fonction de hachage qui projette cette distribution dans un espace de résultats possibles aussi large et uniformément distribué que possible.
Cela peut être difficile; la méthode XOR / bit-shifting ci-dessus n'est probablement pas un mauvais début. Pour un démarrage légèrement meilleur, vous pouvez utiliser le modèle de fonction
hash_value
ethash_combine
de la bibliothèque Boost. Le premier agit de la même manière questd::hash
pour les types standard (récemment, il inclut également des tuples et d'autres types standard utiles); ce dernier vous aide à combiner des valeurs de hachage individuelles en une seule. Voici une réécriture de la fonction de hachage qui utilise les fonctions d'assistance Boost:Et voici une réécriture qui n'utilise pas de boost, mais utilise une bonne méthode de combinaison des hachages:
la source
KeyHasher
?std::hash
méthode spécialisée pour ma clé comme vous l'avez fait. Je mets cela au fond de mon dossier Key.cpp mais je reçois l'erreur suivante: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
. Je suppose que le compilateur ne trouve pas ma méthode de hachage? Dois-je ajouter quelque chose à mon fichier Key.h?std::hash
n'est pas en fait une structure, mais un modèle (spécialisation) pour une structure . Ce n'est donc pas une implémentation - elle sera transformée en implémentation lorsque le compilateur en aura besoin. Les modèles doivent toujours aller dans les fichiers d'en-tête. Voir aussi stackoverflow.com/questions/495021/…find()
renvoie un itérateur, et cet itérateur pointe vers une "entrée" de la carte. Une entrée eststd::pair
constituée d'une clé et d'une valeur. Donc, si vous le faitesauto iter = m6.find({"John","Doe",12});
, vous obtiendrez la cléiter->first
et la valeur (c'est-à-dire la chaîne"example"
)iter->second
. Si vous voulez directement la chaîne, vous pouvez utiliserm6.at({"John","Doe",12})
(qui lèvera une exception si la clé ne se termine pas), oum6[{"John","Doe",12}]
(cela créera une valeur vide si la clé n'existe pas).Je pense que le jogojapan a donné une très bonne et exhaustive réponse . Vous devriez définitivement y jeter un œil avant de lire mon article. Cependant, je voudrais ajouter ce qui suit:
unordered_map
séparément, au lieu d'utiliser l'opérateur de comparaison d'égalité (operator==
). Cela peut être utile, par exemple, si vous souhaitez utiliser ce dernier pour comparer tous les membres de deuxNode
objets les uns aux autres, mais uniquement certains membres spécifiques comme clé d'ununordered_map
.Dans l'ensemble, pour votre
Node
classe, le code pourrait être écrit comme suit:Remarques:
la source
unordered_map
constructeur . Le8
représente le soi-disant "nombre de compartiments". Un compartiment est un emplacement dans la table de hachage interne du conteneur, voir par exempleunordered_map::bucket_count
pour plus d'informations.8
au hasard. Selon le contenu que vous souhaitez stocker dans votreunordered_map
, le nombre de compartiments peut affecter les performances du conteneur.