Choisir entre std :: map et std :: unordered_map

Maintenant que std a une vraie carte de hachage dans unordered_map , pourquoi (ou quand) voudrais-je quand même utiliser la bonne vieille map sur unordered_map sur les systèmes où elle existe réellement? Y a-t-il des situations évidentes que je ne peux pas voir immédiatement?

Comme déjà mentionné , map permet de parcourir les éléments de manière sortingée, contrairement à unordered_map . Ceci est très important dans de nombreuses situations, par exemple en affichant une collection (par exemple un carnet d’adresses). Cela se manifeste également par d’autres moyens indirects comme: (1) Commencer à itérer à partir de l’iterator renvoyé par find() ou (2) l’existence de fonctions membres telles que lower_bound() .

De plus, je pense qu’il y a une différence dans la complexité de la recherche dans le pire des cas .

  • Pour la map , c’est O (lg N)

  • Pour unordered_map , il s’agit de O (N) [Cela peut arriver lorsque la fonction de hachage n’est pas bonne, ce qui entraîne trop de collisions de hachage.]

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

En plus des réponses ci-dessus, notez que le fait que unordered_map soit une vitesse constante ( O(1) ) ne signifie pas que c’est plus rapide que map (du log(N) de commandes log(N) ). La constante peut être plus grande que log(N) surtout que N est limité à 2 32 (ou 2 64 ).

Ainsi, en plus des autres réponses (la map maintient l’ordre et les fonctions de hachage peuvent être difficiles), il se peut que la map soit plus performante.

Par exemple, dans un programme que j’ai lancé pour un article de blog, j’ai constaté que pour VS10, std::unordered_map unordered_map était plus lent que std::map (bien que boost::unordered_map était plus rapide que les deux).

Graphique de performance

Notez les 3ème et 5ème mesures.

Ceci est dû à Chandler Carruth de Google dans sa conférence CppCon 2014

std::map est (considéré par beaucoup comme étant inutile) pour un travail orienté performance: Si vous voulez un access avec un format O (1), utilisez un tableau associatif approprié (ou par défaut, std::unorderded_map ); Si vous voulez un access séquentiel sortingé, utilisez quelque chose basé sur un vecteur.

De plus, std::map est un arbre équilibré; et vous devez le parcourir ou le rééquilibrer, très souvent. Celles-ci sont respectivement des opérations de cache-killer et de cache-apocalypse … il suffit donc de dire NON à std::map .

Vous pourriez être intéressé par cette question SO sur les implémentations efficaces de cartes de hachage.

(PS- std::unordered_map est hostile au cache car il utilise des listes liées comme des compartiments.)

Je pense qu’il est évident que vous utiliseriez la std::map vous avez besoin pour parcourir les éléments de la carte dans l’ordre sortingé.

Vous pouvez également l’utiliser lorsque vous préférez écrire un opérateur de comparaison (qui est intuitif) au lieu d’une fonction de hachage (qui est généralement très peu intuitive).

Disons que vous avez de très grandes clés, peut-être de grandes chaînes. Pour créer une valeur de hachage pour une grande chaîne, vous devez parcourir toute la chaîne du début à la fin. Il faudra au moins un temps linéaire à la longueur de la clé. Cependant, lorsque vous recherchez uniquement un arbre binary à l’aide de l’opérateur > de la clé, chaque comparaison de chaîne peut revenir lorsque la première incompatibilité est trouvée. C’est généralement très tôt pour les grandes chaînes.

Ce raisonnement peut être appliqué à la fonction find de std::unordered_map et std::map . Si la nature de la clé est telle qu’il faut plus de temps pour produire un hachage (dans le cas de std::unordered_map ) qu’il n’en faut pour trouver l’emplacement d’un élément en utilisant la recherche binary (dans le cas de std::map ), il devrait être plus rapide de rechercher une clé dans std::map . Il est assez facile de penser à des scénarios où ce serait le cas, mais ils seraient assez rares dans la pratique, je crois.