Quelle est la meilleure façon d’utiliser un HashMap en C ++?

Je sais que STL a une API HashMap, mais je ne trouve aucune documentation valable et complète avec de bons exemples à ce sujet.

Tout bon exemple sera apprécié.

La STL inclut les std::map ordonnés et non ordonnés ( std::map et std::unordered_map ). Dans une carte ordonnée, les éléments sont sortingés par clé, insert et access est en O (log n)). Habituellement, la STL utilise en interne des arbres rouges noirs pour les cartes ordonnées. Mais ce n’est qu’un détail d’implémentation. Dans une carte non ordonnée, l’insertion et l’access se font dans O (1). C’est juste un autre nom pour une hashtable.

Un exemple avec std::map :

 #include  #include  #include  int main(int argc, char **argv) { std::map m; m["hello"] = 23; // check if key is present if (m.find("world") != m.end()) std::cout << "map contains key world!\n"; // retrieve std::cout << m["hello"] << '\n'; std::map::iterator i = m.find("hello"); assert(i != m.end()); std::cout << "Key: " << i->first << " Value: " << i->second << '\n'; return 0; } 

Sortie:

 23
 Clé: bonjour valeur: 23

Si vous avez besoin de commander dans votre conteneur et que vous avez bien raison avec l'environnement d'exécution O (log n), utilisez simplement std::map .

Sinon, si vous avez vraiment besoin d'une table de hachage (insert / access O (1)), consultez std::unordered_map , qui a une std::map similaire à std::map (par exemple, dans l'exemple ci-dessus, il suffit de chercher et de remplacer map avec unordered_map ).

Le conteneur unordered_map été introduit avec la révision standard C ++ 11 . Ainsi, en fonction de votre compilateur, vous devez activer les fonctionnalités C ++ 11 (par exemple, lorsque vous utilisez GCC 4.8, vous devez append -std=c++11 au CXXFLAGS).

Même avant la sortie de C ++ 11, GCC supportait unordered_map - dans l'espace de noms std::tr1 . Ainsi, pour les anciens compilateurs GCC, vous pouvez essayer de l’utiliser comme ceci:

 #include  std::tr1::unordered_map m; 

Cela fait également partie du boost, c’est-à-dire que vous pouvez utiliser l’en -tête boost correspondant pour une meilleure portabilité.

Un hash_map est une version plus ancienne et non standardisée de ce qui, à des fins de normalisation, est appelé unordered_map (actuellement disponible dans le cadre de TR1 et sera inclus dans C ++ 0x). Comme son nom l’indique, il est différent de std::map principalement parce qu’il n’est pas ordonné – si, par exemple, vous parcourez une carte de begin() à end() , vous obtenez des éléments dans la clé 1 , mais si vous itérez à travers un unordered_map de begin() à end() , vous obtenez des éléments dans un ordre plus ou moins arbitraire.

Une unordered_map devrait normalement avoir une complexité constante. Autrement dit, une insertion, une recherche, etc. prend essentiellement une durée fixe, quel que soit le nombre d’éléments contenus dans la table. Un std::map a une complexité logarithmique sur le nombre d’éléments stockés – ce qui signifie que le temps d’insertion ou de récupération d’un élément augmente, mais très lentement , à mesure que la carte s’agrandit. Par exemple, s’il faut 1 microseconde pour rechercher l’un des 1 million d’éléments, il faut compter environ 2 microsecondes pour rechercher l’un des 2 millions d’éléments, 3 microsecondes pour l’un des 4 millions, 4 microsecondes pour l’un des 8 millions. articles, etc.

D’un sharepoint vue pratique, ce n’est pas vraiment toute l’histoire. Par nature, une simple table de hachage a une taille fixe. L’adaptation aux exigences de taille variable pour un conteneur à usage général est quelque peu banale. Par conséquent, les opérations qui (potentiellement) augmentent ou réduisent la table (par exemple, l’insertion et la suppression) sont souvent relativement lentes. Les recherches, qui ne peuvent pas changer la taille de la table, sont généralement beaucoup plus rapides. En conséquence, la plupart des tables basées sur le hachage ont tendance à être à leur meilleur lorsque vous effectuez beaucoup de recherches et relativement peu d’insertions et de suppressions. Pour les situations où vous insérez beaucoup de données, puis parcourez une fois la table pour récupérer les résultats (par exemple, compter le nombre de mots uniques dans un fichier), il est probable qu’une std::map soit aussi rapide, voire même plus rapide.

1 Où l’ordre est défini par le troisième paramètre du modèle lorsque vous créez la carte, std::less par défaut.

Voici un exemple plus complet et plus flexible qui ne doit pas nécessairement inclure des erreurs de compilation:

 #include  #include  class Hashtable { std::unordered_map htmap; public: void put(const void *key, const void *value) { htmap[key] = value; } const void *get(const void *key) { return htmap[key]; } }; int main() { Hashtable ht; ht.put("Bob", "Dylan"); int one = 1; ht.put("one", &one); std::cout << (char *)ht.get("Bob") << "; " << *(int *)ht.get("one"); } 

Toujours pas particulièrement utile pour les clés, sauf si elles sont prédéfinies comme des pointeurs, car une valeur correspondante ne fera pas l'affaire! (Cependant, comme j'utilise normalement des chaînes pour les clés, remplacer "const void *" par "ssortingng" dans la déclaration de la clé devrait résoudre ce problème.)

Comment utiliser une classe personnalisée et une fonction de hachage avec unordered_map

Cette réponse cloue: C ++ unordered_map utilisant un type de classe personnalisé comme clé

Extrait: égalité:

 struct Key { std::ssortingng first; std::ssortingng second; int third; bool operator==(const Key &other) const { return (first == other.first && second == other.second && third == other.third); } }; 

Fonction de hachage:

 namespace std { template <> struct hash { std::size_t operator()(const Key& k) const { using std::size_t; using std::hash; using std::ssortingng; // Compute individual hash values for first, // second and third and combine them using XOR // and bit shifting: return ((hash()(k.first) ^ (hash()(k.second) << 1)) >> 1) ^ (hash()(k.third) << 1); } }; }