Comment choisir entre map et unordered_map ?

Question

Supposons que je veuille mettre en correspondance des données avec une chaîne de caractères comme clé. Quel conteneur aurais-je dû choisir ? map o unordered_map ? unordered_map consomme plus de mémoire. Supposons que la mémoire ne soit pas un problème et que le souci soit la vitesse.

unordered_map devrait généralement donner une complexité moyenne de O(1) avec le pire cas de O(n). Dans quels cas pourrait-on atteindre O(n) ? Quand est-ce qu'un map sont plus efficaces en termes de temps que unordered_map ? Cela se produit-il lorsque n est petit ?

En supposant que j'utiliserais STL unordered_map avec le haser Vs par défaut. map. string est la clé.

Si je dois itérer sur les éléments plutôt que d'accéder à un élément individuel à chaque fois, dois-je préférer map ?

Answer 1

                       | map              | unordered_map
---------------------------------------------------------
element ordering       | strict weak      | n/a 
                       |                  |
common implementation  | balanced tree    | hash table
                       | or red-black tree|  
                       |                  |
search time            | log(n)           | O(1) if there are no hash collisions
                       |                  | Up to O(n) if there are hash collisions 
                       |                  | O(n) when hash is the same for any key
                       |                  |     
Insertion time         | log(n)+rebalance | Same as search
                       |                  | 
Deletion time          | log(n)+rebalance | Same as search
                       |                  | 
needs comparators      | only operator <  | only operator ==
                       |                  |
needs hash function    | no               | yes
                       |                  |
common use case        | when good hash is| In most other cases. 
                       | not possible or  | 
                       | too slow. Or when|
                       | order is required|

Answer 2

En pratique, si la mémoire n'est pas un problème, unordered_map est toujours plus rapide si vous voulez un accès à un seul élément.

Le pire cas est théorique et lié à un seul hachage comptabilisant l'ensemble des éléments. Cela n'a pas d'importance pratique. Le site unordered_map devient plus lent dès que l'on a au moins log N éléments appartenant au même hachage. Cela n'a pas non plus d'importance pratique. Dans certains scénarios particuliers, vous pouvez utiliser un algorithme de hachage spécifique qui assure une distribution plus uniforme. Pour les chaînes de caractères ordinaires qui ne partagent pas un motif spécifique, les fonctions de hachage génériques fournies avec le logiciel unordered_map sont tout aussi bons.

Si vous souhaitez parcourir la carte (en utilisant des itérateurs) de manière triée, vous ne pouvez pas utiliser la fonction unordered_map . Au contraire, map ne permet pas seulement cela, mais peut également vous fournir l'élément suivant dans une carte basée sur une approximation de la clé (cf. lower_bound et upper_bound méthodes).

Answer 3

Dans quels cas cela pourrait-il atteindre O(n) ?

si vous avez un tel mauvais fonction de hachage qui produit la même valeur de hachage pour tous les mélanges d'entrée (c'est-à-dire qui produit des collisions)...

Quel conteneur aurais-je dû choisir, map ou unordered_map ?

Il faut toujours se poser la question des exigences et du type ou de la quantité de données dont on dispose.

Quand une carte devient-elle plus efficace en termes de temps qu'unordered_map ?

Il s'agit simplement de structures différentes. Il est préférable de choisir l'une d'entre elles en fonction de vos cas d'utilisation typiques (en tenant compte du type de données dont vous disposez et de leur quantité).

Cela se produit-il lorsque n est petit ?

Dans le cas d'une petite quantité de données, tout dépend de l'implémentation particulière de la STL... Donc parfois, même un simple vecteur/rayon peut être plus rapide que des conteneurs associatifs...

Answer 4

Quel conteneur aurais-je dû choisir, map ou unordered_map ? Unordered_map prend plus de mémoire, donc supposons que la mémoire n'est pas un problème, et que le souci est la vitesse.

Faites votre profil et décidez ensuite. unordered_map est généralement plus rapide, mais cela varie selon les cas.

Dans quels cas cela pourrait-il atteindre O(n) ?

Lorsque le hachage n'est pas bon et qu'un tas d'éléments sont affectés aux mêmes cases.

Quand une carte devient-elle plus efficace en termes de temps qu'unordered_map ? Est-ce que cela arrive quand n est petit ?

Probablement pas, mais profilez-le si vous y tenez vraiment. Il semble extrêmement improbable qu'un conteneur de petite taille soit le goulot d'étranglement de votre programme. Quoi qu'il en soit, un simple vector avec une recherche linéaire peut être plus rapide pour de tels cas.

---

La chose la plus importante lors de la prise de décision est l'exigence de l'ordre et l'absence d'invalidation des itérateurs. Si vous avez besoin de l'un ou l'autre, vous devez pratiquement utiliser map . Autrement, unordered_map .

Answer 5

Std::map stocke en interne les éléments dans une BST équilibrée. Par conséquent, les éléments seront stockés dans l'ordre trié des clés.

std::unordered_map stocke les éléments en utilisant une table de hachage. Par conséquent, les éléments ne seront pas stockés dans un ordre trié. Ils seront stockés dans un ordre arbitraire.

Utilisation de la mémoire :

L'utilisation de la mémoire est plus importante dans unordered_map par rapport à map parce que unordered_map a besoin d'espace pour stocker la table de hachage aussi.

Complexité temporelle de la recherche d'un élément :

La complexité du temps pour la recherche d'éléments dans std::map est O(log n). Même dans le pire des cas, elle sera de O(log n) car

Alors que, dans le meilleur des cas, la complexité temporelle de la recherche dans std::unordered_map est de O(1). Si la fonction de code de hachage n'est pas bonne, la complexité dans le pire des cas peut être O(n).