Choisir entre std::map et std::unordered_map

Question

Maintenant que a un hachage véritable carte en , pourquoi (ou quand) je voudrait encore d’utiliser la bonne vieille sur sur les systèmes où il existe réellement ? Y a-t-il des situations évidentes que je ne vois pas immédiatement ?

Answer 1

Comme déjà mentionné, map permet d'itérer sur les éléments triés façon, mais unordered_map ne le sont pas. Ceci est très important dans de nombreuses situations, par exemple l'affichage d'une collection (par exemple, carnet d'adresses). Cela se manifeste également dans d'autres moyens indirects, comme: (1) Début de l'itération de l'itérateur renvoyé par find(), ou (2) l'existence de fonctions de membre comme lower_bound().

Aussi, je pense qu'il y a une certaine différence dans le pire des cas, la recherche de la complexité.

• Pour map, il est O( lg N )

• Pour unordered_map, il est O( N ) [Cela peut se produire lorsque la fonction de hachage n'est pas bon conduisant à de trop nombreuses collisions de hachage.]

La même chose est applicable pour le pire des cas, la suppression de la complexité.

Answer 2

Outre les réponses ci-dessus, vous devez également noter que juste parce que l' unordered_map est la constante de vitesse (O(1)) ne signifie pas qu'il est plus rapide que d' map (de l'ordre de log(N)). La constante peut être plus grand que log(N) surtout depuis N est limitée par 2³² (ou 2⁶⁴).

Donc, en plus d'autres réponses (map maintient l'ordre et les fonctions de hachage peut être difficile) il se peut qu' map est plus performant).

Par exemple, dans un programme, j'ai couru pour un blog j'ai vu que pour VS10 std::unordered_map a été plus lente qu' std::map (bien qu' boost::unordered_map a été plus rapide que les deux).

Remarque 3ème et la 5ème bars.

Answer 3

Je pense qu’il est évident que vous utiliseriez le `` vous avez besoin effectuer une itération à travers des éléments de la carte dans un ordre trié.

Vous pouvez aussi l’utiliser lorsque vous souhaitez écrire un opérateur de comparaison (ce qui est intuitif) au lieu d’une fonction de hachage (qui est généralement très intuitif).

Answer 4

Une autre différence subtile entre et , c’est que dans la clé doit être facilement couverte dans un entier et qui n’est parfois pas facile ou impossible. Je crois que vous ne pouvez pas avoir une clé de type chaîne dans .