-
Quel conteneur choisir ?
Salut,
Je dois coder un programme qui réalise énormément d'opérations sur les strings dans un conteneur et je n'arrive pas a déterminer lequel choisir.
Mes critères :
-recherche la plus rapide possible .
-l'ajout/modification/suppression n'est pas du tout important.
Merci d'avance.
-
unordered_set / unordered_map ?
-
si tes chaines resterons uniques, alors tu peut prendre le std::set<>, il trie les chaines quand tu l'ajoute, et il permet une réception rapide de la chaîne, mais c'est un jeu, il ne permet pas que des éléments soient placés en doubles
-
multiset c'est la même chose qui permet les doublons...
-
et une multimap s'il veux associer une clef avec ses chaînes ^^
ou encore une hash map s'il veux une recherche encore plus rapide
-
Déjà cité plus haut, unordered_map est la version standard de hash_map.
-
+1, dans une table de hashage la recherche est effectuée en temps constant, donc unordered_set/map
Par contre cela ne peut servir qu'à détecter la présence d'une donnée.
Exemple: imaginons un tableau dans lequel tu stockes des entiers. Tu veux pouvoir effectuer une recherche renvoyant le plus petit entier du tableau qui soit plus grand qu'un entier donné. Ca ne fonctionnera pas avec une table de hashage, la meilleure complexité pour ça est logarithmique (avec un tableau trié ou un arbre binaire de recherche).
-
-
la FAQ est très belle mais faudrait peut être intégrer les conteneurs du TR1.
(ne pensez pas à moi, j'ai déjà du travail)
-
Mais je t'en prie, complète le schéma :lol: