Comment choisir entre la carte et unordered_map?

Supposons que je voulais données de carte avec une chaîne comme la clé.
Ce conteneur doit, je l'ai choisi, map ou unordered_map? unordered_map prend plus de mémoire donc, supposons que la mémoire n'est pas un problème, le problème est la vitesse.

unordered_map doit généralement donner de moyenne complexité de O(1) avec le pire des cas en O(n).
Dans ce cas, serait-il arriver à O(n)?
Quand un map obtenir plus efficace que la unordered_map? T-il se passer lorsque n est petit?

En supposant que je voudrais utiliser la STL unordered_map avec la valeur par défaut haser Vs. carte. la chaîne est la clé.

Si je vais effectuer une itération sur les éléments plutôt que d'accéder à un élément particulier chaque fois, devrais-je préfère map?

  • Avez-vous besoin à des éléments de la cartographie à trier?
  • La mise en œuvre de unordered_map utilise plus de mémoire?
  • Vous avez toujours surcharge de la mémoire dans une table de hachage carte, mais il est généralement négligeable.
  • C'est un point mineur, mais comme vous le mentionnez l'itération, il est intéressant de souligner que si vous itérez lors de l'insertion d'éléments, vous devriez favoriser carte sur unordered_map.
  • Double Possible de Est-il un avantage de l'utilisation de la carte sur unordered_map en cas de trivial clés?
InformationsquelleAutor StackHeapCollision | 2012-12-10
  1. 59

    Dans la pratique, si la mémoire n'est pas question, unordered_map est toujours plus rapide si vous souhaitez que seul l'accès à l'élément.

    Le pire des cas est théorique et lié à un seul de hachage de la comptabilité pour tous les éléments. Ce n'est pas pratique. Le unordered_map devient plus lent dès que vous avez au moins un journal de N éléments appartenant à la même hash. Ce n'est également pas d'intérêt pratique. Dans certains scénarios, vous pourriez utiliser un algorithme de hachage qui permet d'assurer une distribution plus uniforme. Pour les chaînes ordinaires qui ne partagent pas un modèle spécifique, le générique de fonctions de hachage à venir avec unordered_map sont tout aussi bonnes.

    Si vous souhaitez parcourir la carte (à l'aide d'itérateurs) triés mode, vous ne pouvez pas utiliser unordered_map. Au contraire, map non seulement permet, mais peut également vous fournir l'élément suivant dans une carte basée sur une approximation de la clé (voir lower_bound et upper_bound méthodes).

    • Cette réponse est trompeuse. Ce n'est pas vrai que "unordered_map est toujours plus rapide pour seul accès à l'élément" -- la seule chose à laquelle je pense c'est toujours vrai, c'est que c'est toujours plus rapide amortis et asymptotiquement. Le "amorti" est une mise en garde importante dans practce: en supposant qu'il est mis en œuvre comme une table de hachage d'une certaine sorte, si je me souviens de mes tables de hachage correctement, comme vous le cultiver par l'insertion d'éléments, il sera le "hoquet" avec un Ω(n) opération chaque tellement souvent. Qui peut ou ne peut pas être quelque chose de tout particulier app peut tolérer.
    InformationsquelleAutor ypnos
  2. 188
                           | 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|
    • Commentaire à propos de la mise en œuvre commune: Un rouge–noir est un arbre type de l'équilibre de l'arbre (ou plus précisément, une sorte d'auto-équilibrage arbre de recherche binaire).
    • rééquilibrer prendrait pas plus de log(n)
    • Qu'en est itération sur tous les éléments?
    InformationsquelleAutor
  3. 7

    Dans ce cas, serait-il arriver à O(n)?

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

    Ce récipient que j'ai choisi, de carte ou de unordered_map?

    C'est toujours la questions des exigences et de la nature ou de la quantité de données que vous avez.

    Quand une carte obtenir de plus efficace que la unordered_map?

    C'est juste différent des structures. Vous feriez mieux de faire une chiose à utiliser l'un d'eux en fonction de votre cas d'utilisation typique (takeing en compte ce type de données avez-vous des et son montant)

    T-il hppaen lorsque n est petit?

    En cas de petite quantité de données, tout dépend de particulier STL mise en œuvre...
    Donc, parfois même un simple vecteur/matrice pourrait être plus rapide que les conteneurs associatifs...

    InformationsquelleAutor zaufi
  4. 7

    Ce récipient que j'ai choisi, de carte ou de unordered_map? unordered_map prend plus de mémoire donc, supposons que la mémoire n'est pas un problème, le problème est la vitesse.

    Profil et de décider ensuite. unordered_map est généralement plus rapide, mais il varie selon les cas.

    Dans ce cas, serait-il arriver à O(n)?

    Lorsque le hachage n'est pas bonne, et tout un tas d'éléments sont affectés à la même catégorie.

    Quand une carte obtenir de plus efficace que la unordered_map? Est-il happaen lorsque n est petit?

    Probablement pas, mais le profil, si vous vous souciez vraiment. Avoir un conteneur avec une petite taille d'être le goulot d'étranglement de votre programme semble très peu probable. De toute façon, un simple vector avec recherche linéaire peut être plus rapide pour de tels cas.

    La chose la plus importante pour décider est la exigences de la commande et le manque de itérateur d'invalidation. Si vous avez besoin, vous devez utiliser map. Sinon, unordered_map.

    InformationsquelleAutor Pubby