J'ai entendu beaucoup de personnes dire que si le nombre d'éléments prévus dans le récipient est relativement petite, il est préférable d'utiliser std::vector au lieu de std::map eventhough-je utiliser le conteneur pour seulement recherche et non pas de l'itération. Quelle est la vraie raison derrière tout cela ? Évidemment, la recherche de la performance de la carte ne peut pas être pire que celle du vecteur (bien qu'il puisse être en nanosecondes/microsecondes) donc a-t-elle quelque chose à voir avec l'utilisation de la mémoire ? N'vecteur de prix mieux/pire que de la carte de fragmentation de l'espace d'adressage virtuel? Je suis en utilisant la bibliothèque STL qui vient avec Visual Studio (c'est à dire mise en œuvre de microsoft) n'a que faire de toute différence avec d'autres implémentations?
Réponses
Trop de publicités?
Je présume que vous êtes en comparant map<A, B> avec vector<pair<A, B> >.
Tout d'abord, trouver un élément dans une très petite vecteur peut facilement être plus rapide que la même chose dans une carte, parce que toute la mémoire d'un vecteur est toujours contigus (et donc joue plus bien avec des ordinateurs de caches et de telles choses), et le nombre de comparaisons nécessaires pour trouver quelque chose dans un vecteur peut être le même que celui d'une carte. Trouver un élément dans une carte a besoin de moins d'opérations dans les limites de très grands conteneurs.
Le point où les cartes sont plus rapide que les vecteurs dépend de la mise en œuvre, sur votre processeur, ce qui constitue des données dans la carte, et des choses subtiles, comme ce mémoire est dans le cache du processeur. Généralement, le point où la carte devient plus rapide serait d'environ 5 à 30 éléments.
Une alternative est d'utiliser une table de hachage contenant. Ils sont souvent nommés d' hash_map ou unordered_map. Classes nommées hash_map ne font pas partie de la norme officielle (et il y a quelques variantes, y); std::tr1::unordered_map est. Un tableau associatif est souvent plus rapide qu'une normal map pour les recherches, indépendamment de la façon dont de nombreux éléments sont en elle, mais si elle est effectivement plus rapide dépend de ce que la clé est, comment il est haché, quelles sont les valeurs que vous avez à traiter avec, et la façon dont la clé est comparé dans le std::map. Il n'a pas garder les choses dans un ordre spécifique, comme std::map, mais vous avez dit que vous ne vous inquiétez pas à ce sujet. Je vous recommande de hachage cartes en particulier si les clés sont des entiers ou des pointeurs, parce que ces hachage très rapidement.
Les cartes sont généralement mises en œuvre comme des arbres binaires, et de la marche d'un arbre binaire vient toujours avec un peu de surcharge (en effectuant des comparaisons, la marche des liens, etc...) Les vecteurs sont en fait que des tableaux. Pour de très petites quantités de données, peut-être 8 ou 12 éléments, parfois il est plus rapide de faire une recherche linéaire sur un tableau que pour pied d'un arbre de recherche binaire.
Vous pouvez exécuter certains timings de vous-même pour voir où même le point de rupture est temps de recherche sur quatre éléments, puis huit, puis seize, et ainsi de suite pour trouver le sweet spot pour votre mise en œuvre de la STL.
Les cartes ont tendance à avoir un tas de petites allocations partout dans le tas, alors que les vecteurs sont contigus, de sorte que le cache-taux de succès de vecteurs peuvent parfois être un peu mieux dans le cas où vous êtes une itération sur tous les éléments de l'avant vers l'arrière.
Si vous effectuez toutes vos insertions à la fois puis effectuez de nombreuses recherches, vous pouvez utiliser un vecteur et le trier lorsque vous avez terminé l'insertion; Ensuite, utilisez lower_bound pour effectuer une recherche rapide. Cela peut être plus rapide que d'utiliser une carte, même pour un grand nombre d'éléments.
Je pense que vous devriez utiliser le conteneur qui s'adapte aux données d'abord et avant tout. std::vector est utilisé dans des situations où vous utiliseriez un tableau en C ou pré-STL C++: vous voulez un bloc contigu de mémoire pour stocker des valeurs rapide de la constante de temps de recherche. std::map doit être utilisé pour mapper les touches de valeurs. Le principal chevauchement ici est un vecteur vs une carte avec un size_t comme la clé. Dans ce cas, il y a deux préoccupations: les indices continu? Si non, vous aurez probablement être en train de perdre la mémoire avec des un vecteur. Deuxièmement, quel look-up de temps voulez-vous? Un vecteur a de la constante de temps de recherche, tandis que les std::map est généralement mis en œuvre comme un RB de l'arbre, qui est un O(log n) look-up de temps, et même une table de hachage de la carte (comme TR1 unordered_map) a généralement une aggravation de la complexité, car l'index (ou d'un hachage de celui-ci) sera associée à un seau qui peut contenir plusieurs valeurs.
Si visaient un vecteur avec des paires: vous pouvez les éléments d'un vecteur et d'utiliser find pour trouver des éléments. Mais c'est un binaire de recherche, et sera pratiquement aussi rapide qu'un std::map.
De toute façon, essayer de modéliser les données dans la manière évidente. L'optimisation prématurée souvent ne l'aide pas beaucoup.
