ce que je sais c que la difference entre une map est une multimap, c au niveau des doublons
mais quelle difference y a t il entre les deux conteneurs precedants et la hash_map ???
ce que je sais c que la difference entre une map est une multimap, c au niveau des doublons
mais quelle difference y a t il entre les deux conteneurs precedants et la hash_map ???
Une hash_map n'est pas triée, et son acces est généralement plus rapide (généralement simplifié en O(1) au lieu de O(Log N)).
Par contre, j'ignore si elle peut ou non contenir des doublons, mais j'en doute.
SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.
"Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
Apparently everyone. -- Raymond Chen.
Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.
Salut,
L'un des premiers liens fournis par google est http://www.sgi.com/tech/stl/hash_map.html
Assez bizarement, la description qui en est donnée sur cette page ressemble énormément à la map
Une autre recherche essayant de mettre les deux en parallelle semble indiquer que le but de la hash_map est d'améliorer le temps de recherche par rapport à la map
Mais la litérature que j'ai trouvée ne semble pas indiquer précisement comment ils comptent s'y prendre![]()
A méditer: La solution la plus simple est toujours la moins compliquée
Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
Compiler Gcc sous windows avec MinGW
Coder efficacement en C++ : dans les bacs le 17 février 2014
mon tout nouveau blog
std::map est un arbre binaire ordonné (enfin, c'est juste une conséquence de ses spécifications dans la norme), la recherche est donc en temps logarithmique puisqu'il faut au pire des cas parcourir toute la hauteur de l'arbre.
hash_map est une table de hachage, càd que la clé donne directement l'indice de l'élément correspondant par hachage (les algorithmes de hachages pour les types courants sont bien connus), ce qui implique le temps de recherche en temps constant. Selon le type de table de hachage, les collisions (plusieurs clés ayant la même valeur de hachage) peuvent être gérées, dans ce cas une clé renverra non pas à un élément, mais à une liste d'éléments.
Voir un cours d'algo / structures de données pour plus de détails.
Mieux que SDL : découvrez SFML
Mes tutoriels 2D/3D/Jeux/C++, Cours et tutoriels C++, FAQ C++, Forum C++.
Partager