unordered_map avec la paire comme clé – pas de compilation

Vous devez fournir une fonction de hachage adaptée à votre type de clé. Un exemple simple:

 #include  #include  #include  #include  // Only for pairs of std::hash-able types for simplicity. // You can of course template this struct to allow other hash functions struct pair_hash { template  std::size_t operator () (const std::pair &p) const { auto h1 = std::hash{}(p.first); auto h2 = std::hash{}(p.second); // Mainly for demonstration purposes, ie works but is overly simple // In the real world, use sth. like boost.hash_combine return h1 ^ h2; } }; using Vote = std::pair; using Unordered_map = std::unordered_map; int main() { Unordered_map um; } 

Cela fonctionnera, mais n’aura pas les meilleures propriétés de hachage ^† . Vous voudrez peut-être jeter un coup d’œil à quelque chose comme boost.hash_combine pour obtenir des résultats de meilleure qualité lors de la combinaison des hachages.

Pour une utilisation réelle: Boost fournit également la fonction hash_value qui fournit déjà une fonction de hachage pour std::pair , ainsi que std::tuple et la plupart des conteneurs standard.

^† Plus précisément, cela produira trop de collisions. Par exemple, chaque paire symésortingque hachera à 0 et les paires qui ne diffèrent que par permutation auront le même hachage. C’est probablement bien pour votre exercice de programmation, mais cela pourrait sérieusement nuire aux performances du code réel.

Pour résoudre ce problème, ma méthode préférée consiste à définir une fonction key qui transforme votre paire en un entier unique (ou tout type de données à caractère extensible). Cette clé n’est pas la clé de hachage. C’est l’ID unique de la paire de données qui sera ensuite hachée de manière optimale par le unordered_map . Par exemple, vous vouliez définir une unordered_map du type

  unordered_map,double> Map; 

Et vous voulez utiliser Map[make_pair(i,j)]=value ou Map.find(make_pair(i,j)) pour fonctionner sur la carte. Ensuite, vous devrez dire au système comment hacher une paire d’entiers make_pair(i,j) . Au lieu de cela, nous pouvons définir

  inline size_t key(int i,int j) {return (size_t) i << 32 | (unsigned int) j;} 

puis changez le type de la carte en

  unordered_map Map; 

Nous pouvons maintenant utiliser Map[key(i,j)]=value ou Map.find(key(i,j)) pour opérer sur la carte. Chaque make_pair maintenant la fonction de key inline.

Cette méthode garantit que la clé sera hachée de manière optimale, car à présent, la partie de hachage est effectuée par le système, qui choisira toujours la taille de la table de hachage interne comme étant optimale pour garantir la même probabilité pour chaque compartiment. Mais vous devez vous assurer à 100% que la key est unique pour chaque paire, c'est-à-dire que deux paires distinctes ne peuvent pas avoir la même clé ou qu'il peut y avoir des bogues très difficiles à trouver.

Comme votre erreur de compilation l’indique, il n’y a pas d’instanciation valide de std::hash> dans votre espace de noms std.

Selon mon compilateur:

Erreur C2338 La norme C ++ ne fournit pas de hachage pour ce type. c: \ fichiers de programme (x86) \ microsoft visual studio 14.0 \ vc \ include \ xstddef 381

Vous pouvez fournir votre propre spécialisation pour std::hash comme suit:

 #include  #include  #include  using namespace std; using Vote = pair; using Unordered_map = unordered_map; namespace std { template<> struct hash { size_t operator()(Vote const& v) const { // ... hash function here ... } }; } int main() { Unordered_map m; } 

Pour la clé de paire, nous pouvons utiliser la fonction de hachage de paire renforcée:

 #include  #include  #include  using namespace std; int main() { unordered_map, int, boost::hash>> m; m[make_pair("123", "456")] = 1; cout << m[make_pair("123", "456")] << endl; return 0; } 

De même, nous pouvons utiliser le hachage de boost pour les vecteurs,

 #include  #include  #include  #include  using namespace std; int main() { unordered_map, int, boost::hash>> m; vector a({"123", "456"}); m[a] = 1; cout << m[a] << endl; return 0; }