Dans quel scénario utiliser un conteneur STL particulier?

185

J'ai lu sur les conteneurs STL dans mon livre sur C ++, en particulier la section sur la STL et ses conteneurs. Maintenant, je comprends que chacun d'entre eux a ses propres propriétés spécifiques, et je suis sur le point de les mémoriser tous ... Mais ce que je ne saisis pas encore, c'est dans quel scénario chacun d'eux est utilisé.

Quelle est l'explication? Un exemple de code est de loin préférable.

Daniel Sloof
la source
voulez-vous dire carte, vectot, ensemble, etc.?
Thomas Tempelmann
Même en regardant ce diagramme, je ne peux pas dire quel serait le meilleur à utiliser dans mon quastion stackoverflow.com/questions/9329011/…
sergiol
2
@sbi: Suppression de la balise C ++ Faq de celle-ci et l'ajout à la plus récente et C ++ 11 inclus Comment puis-je sélectionner efficacement un conteneur de bibliothèque Standard dans C ++ 11?
Alok Save

Réponses:

338

Cette feuille de triche fournit un assez bon résumé des différents conteneurs.

Consultez l'organigramme en bas comme guide à utiliser dans différents scénarios d'utilisation:

http://linuxsoftware.co.nz/containerchoice.png

Créé par David Moore et sous licence CC BY-SA 3.0

zdan
la source
14
Cet organigramme est en or, j'aurais aimé avoir quelque chose comme ça en c #
Bruno
2
Lien mis à jour: C ++ Containers Cheat Sheet .
Bill Door
3
Le point de départ doit être vectorplutôt vide. stackoverflow.com/questions/10699265/…
eonil
5
Vous avez maintenant unordered_mapet unordered_set(et leurs multiples variantes) qui ne sont pas dans l'organigramme, mais sont de bons choix lorsque vous ne vous souciez pas de la commande mais que vous avez besoin de trouver des éléments par clé. Leur recherche est généralement O (1) au lieu de O (log n).
Aidiakapi
2
@ shuttle87 non seulement cette taille ne variera jamais, mais plus important encore, cette taille est déterminée au moment de la compilation et ne variera jamais.
YoungJohn
188

Voici un organigramme inspiré de la version de David Moore (voir ci-dessus) que j'ai créée, qui est à jour (principalement) avec le nouveau standard (C ++ 11). Ce n'est que mon point de vue personnel, ce n'est pas indiscutable, mais j'ai pensé que cela pourrait être utile pour cette discussion:

enter image description here

Mikael Persson
la source
4
Pouvez-vous rendre l'original disponible? C'est un excellent graphique. Peut-être coller sur un blog ou GitHub?
kevinarpe
1
C'est un excellent graphique. Mais quelqu'un peut-il m'expliquer ce que l'on entend par «positions persistantes»?
IDDQD
3
@STALKER Des positions persistantes signifient que si vous avez un pointeur ou un itérateur vers un élément du conteneur, ce pointeur ou itérateur restera valide (et pointant vers le même élément) indépendamment de ce que vous ajoutez ou supprimez du conteneur (tant qu'il n'est pas l'élément en question).
Mikael Persson
1
C'est vraiment un excellent graphique, mais je pense que vector (sorted)c'est un peu incompatible avec le reste. Ce n'est pas un type de conteneur différent, juste le même std::vectormais trié. Plus important encore, je ne vois pas pourquoi on ne pourrait pas utiliser une std::setpour une itération ordonnée si c'est le comportement standard de l'itération à travers un ensemble. Bien sûr, si la réponse parle d'un accès ordonné aux valeurs de l'auge du conteneur [], alors ok vous ne pouvez le faire qu'avec un soted std::vector. Mais dans les deux cas, la décision doit être prise juste après la question "ordre est nécessaire"
AR
1
@ user2019840 Je voulais limiter le graphique aux conteneurs standard. Ce qui devrait apparaître à la place de "vecteur trié" est "flat_set" (de Boost.Container ), ou équivalent (chaque bibliothèque majeure ou base de code a un équivalent flat_set, AFAIK). Mais ceux-ci ne sont pas standard et constituent une omission flagrante de la part de la STL. Et la raison pour laquelle vous ne voulez pas parcourir std :: set ou std :: map (du moins pas fréquemment) est qu'il est très inefficace de le faire .
Mikael Persson
41

Réponse simple: à utiliser std::vectorpour tout sauf si vous avez une vraie raison de faire autrement.

Lorsque vous trouvez un cas où vous pensez, "Gee, std::vectorne fonctionne pas bien ici à cause de X", allez sur la base de X.

David Thornley
la source
1
Cependant .. faites attention à ne pas supprimer / insérer des éléments lors de l'itération ... utilisez const_iterator autant que possible pour éviter cela ..
vrdhn
11
Hmm ... Je pense que les gens utilisent abusivement le vecteur. La raison en est que le cas "ne fonctionne pas" ne se produira pas facilement - donc les gens s'en tiennent au conteneur le plus souvent utilisé et en abusent pour stocker des listes, des files d'attente, ... À mon avis - ce qui correspond à l'organigramme - on devrait choisir le conteneur en fonction de l'usage prévu au lieu d'appliquer le "un semble convenir à tous".
Noir
13
@Black Point est que le vecteur est généralement plus rapide même sur des opérations qui en théorie devraient fonctionner plus lentement.
Bartek Banachewicz
1
@Vardhan std::remove_ifest presque toujours supérieur à l'approche "supprimer pendant l'itération".
fredoverflow
1
Certains points de repère aideraient vraiment cette discussion à être moins subjective.
Felix D.
11

Regardez le STL efficace par Scott Meyers. C'est bon pour expliquer comment utiliser la STL.

Si vous souhaitez stocker un nombre déterminé / indéterminé d'objets et que vous n'allez jamais en supprimer, un vecteur est ce que vous voulez. C'est le remplacement par défaut d'un tableau C, et il fonctionne comme un, mais ne déborde pas. Vous pouvez également définir sa taille au préalable avec reserve ().

Si vous souhaitez stocker un nombre indéterminé d'objets, mais que vous les ajouterez et les supprimerez, vous voudrez probablement une liste ... car vous pouvez supprimer un élément sans déplacer les éléments suivants - contrairement au vecteur. Cependant, cela prend plus de mémoire qu'un vecteur et vous ne pouvez pas accéder séquentiellement à un élément.

Si vous voulez prendre un tas d'éléments et ne trouver que les valeurs uniques de ces éléments, les lire tous dans un ensemble le fera, et il les triera également pour vous.

Si vous avez beaucoup de paires clé-valeur et que vous souhaitez les trier par clé, une carte est utile ... mais elle ne contiendra qu'une seule valeur par clé. Si vous avez besoin de plus d'une valeur par clé, vous pouvez avoir un vecteur / liste comme valeur dans la carte, ou utiliser une multi-carte.

Ce n'est pas dans la STL, mais c'est dans la mise à jour TR1 de la STL: si vous avez beaucoup de paires clé-valeur que vous allez rechercher par clé, et que vous ne vous souciez pas de leur ordre, vous pourriez voulez utiliser un hachage - qui est tr1 :: unordered_map. Je l'ai utilisé avec Visual C ++ 7.1, où il s'appelait stdext :: hash_map. Il a une recherche de O (1) au lieu d'une recherche de O (log n) pour la carte.

Mark Krenitsky
la source
J'ai entendu quelques anecdotes suggérant maintenant que Microsoft hash_mapn'est pas une très bonne implémentation. J'espère qu'ils ont fait mieux unordered_map.
Mark Ransom
3
Des listes - "vous ne pouvez pas accéder séquentiellement à un élément." - Je pense que vous voulez dire que vous ne pouvez pas accéder au hasard ou indexer directement à un élément ....
Tony Delroy
^ Oui, car l'accès séquentiel est précisément ce que listfait a. Erreur plutôt flagrante là-bas.
underscore_d
7

J'ai repensé l'organigramme pour avoir 3 propriétés:

  1. Je pense que les conteneurs STL sont divisés en 2 classes principales. Les conteneurs de base et ceux-ci exploitent les conteneurs de base pour mettre en œuvre une stratégie.
  2. Dans un premier temps, l'organigramme doit diviser le processus de décision entre les principales situations sur lesquelles nous devons décider, puis élaborer sur chaque cas.
  3. Certains conteneurs étendus ont la possibilité de choisir un conteneur de base différent comme conteneur intérieur. L'organigramme doit tenir compte des situations dans lesquelles chacun des conteneurs de base peut être utilisé.

L'organigramme: enter image description here

Plus d'informations fournies dans ce lien .

Ebrahim
la source
5

Un point important que brièvement mentionné jusqu'à présent, est que si vous avez besoin de mémoire contiguë (comme un tableau C donne), alors vous ne pouvez utiliser vector, arrayou string.

À utiliser arraysi la taille est connue au moment de la compilation.

À utiliser stringsi vous avez uniquement besoin de travailler avec des types de caractères et que vous avez besoin d'une chaîne, pas seulement d'un conteneur à usage général.

Utiliser vectordans tous les autres cas (vector devrait être le choix par défaut du conteneur dans la plupart des cas de toute façon).

Avec ces trois éléments, vous pouvez utiliser la data()fonction membre pour obtenir un pointeur vers le premier élément du conteneur.

Jonathan Wakely
la source
3

Tout dépend de ce que vous souhaitez stocker et de ce que vous souhaitez faire avec le conteneur. Voici quelques exemples (très non exhaustifs) des classes de conteneurs que j'ai tendance à utiliser le plus:

vector: Disposition compacte avec peu ou pas de surcharge de mémoire par objet contenu. Efficace pour itérer. L'ajout, l'insertion et l'effacement peuvent être coûteux, en particulier pour les objets complexes. Pas cher pour trouver un objet contenu par index, par exemple myVector [10]. Utilisez là où vous auriez utilisé un tableau en C. Bon où vous avez beaucoup d'objets simples (par exemple int). N'oubliez pas d'utiliserreserve() avant d'ajouter beaucoup d'objets au conteneur.

list: Petite surcharge de mémoire par objet contenu. Efficace pour itérer. L'ajout, l'insertion et l'effacement sont bon marché. Utilisez là où vous auriez utilisé une liste chaînée en C.

set(et multiset): surcharge importante de la mémoire par objet contenu. Utilisez là où vous avez besoin de savoir rapidement si ce conteneur contient un objet donné ou fusionnez des conteneurs efficacement.

map (et multimap ): surcharge importante de la mémoire par objet contenu. Utilisez l'endroit où vous souhaitez stocker les paires clé-valeur et recherchez rapidement les valeurs par clé.

L'organigramme sur la feuille de triche suggérée par zdan fournit un guide plus exhaustif.

Offres
la source
"Petite surcharge de mémoire par objet contenu" n'est pas vrai pour la liste. std :: list est implémenté en tant que liste doublement chaînée et maintient donc 2 pointeurs par objet stocké, ce qui n'est pas à négliger.
Hanna Khalil
Je compterais toujours deux pointeurs par objet stocké comme «petit».
Enchère
comparé à quoi? std :: forward_list est un conteneur qui a été principalement suggéré pour avoir moins de méta-données stockées par objet (un seul pointeur). Alors que std :: vector contient 0 méta-données par objet. Donc, 2 pointeurs ne sont pas négociables par rapport aux autres conteneurs
Hanna Khalil
Tout dépend de la taille de vos objets. J'ai déjà dit que le vecteur a une "mise en page compacte avec peu ou pas de surcharge de mémoire par objet contenu". Je dirais quand même que la liste a une petite surcharge de mémoire par rapport à set et map, et une surcharge de mémoire légèrement plus grande que vector. Je ne sais pas vraiment à quel point vous essayez de faire TBH!
Enchère
Tous les conteneurs basés sur le mode ont tendance à avoir une surcharge importante en raison de l'allocation dynamique, qui est rarement gratuite. À moins bien sûr que vous n'utilisiez un allocateur personnalisé.
MikeMB
2

Une leçon que j'ai apprise est la suivante: essayez de l'envelopper dans une classe, car changer le type de conteneur un beau jour peut donner de grandes surprises.

class CollectionOfFoo {
    Collection<Foo*> foos;
    .. delegate methods specifically 
}

Cela ne coûte pas cher au départ et permet de gagner du temps lors du débogage lorsque vous souhaitez interrompre chaque fois que quelqu'un effectue l'opération x sur cette structure.

En venant à sélectionner la structure de données parfaite pour un travail:

Chaque structure de données fournit certaines opérations, qui peuvent être de complexité temporelle variable:

O (1), O (lg N), O (N), etc.

Vous devez essentiellement deviner au mieux quelles opérations seront les plus effectuées et utiliser une structure de données qui a cette opération comme O (1).

Simple, n'est-ce pas (-:

vrdhn
la source
5
N'est-ce pas pourquoi nous utilisons des itérateurs?
Platinum Azure
@PlatinumAzure Même les itérateurs devraient être membres typedef .. Si vous changez le type de conteneur, vous devez également changer toutes les définitions d'itérateur ... cela a été corrigé dans c ++ 1x cependant!
vrdhn
4
Pour les curieux, voici le correctif en C ++ 11: auto myIterator = whateverCollection.begin(); // <-- immune to changes of container type
Noir
1
Serait- typedef Collection<Foo*> CollectionOfFoo;ce suffisant?
Craig McQueen
5
Il est peu probable que vous puissiez simplement changer d'avis plus tard et simplement déléguer à un autre conteneur: Méfiez-vous de l'illusion du code indépendant du conteneur
fredoverflow
1

J'ai développé le fantastique organigramme de Mikael Persson . J'ai ajouté quelques catégories de conteneurs, le conteneur de tableau et quelques notes. Si vous souhaitez votre propre copie, voici le dessin Google. Merci, Mikael d'avoir fait le travail de base! Sélecteur de conteneurs C ++

John DiFini
la source
1

J'ai répondu à cela dans une autre question qui est marquée comme dupe de celle-ci. Mais je pense qu'il est agréable de se référer à quelques bons articles concernant la décision de choisir un conteneur standard.

Comme @David Thornley a répondu, std :: vector est la voie à suivre s'il n'y a pas d'autres besoins spéciaux. C'est le conseil donné par la créatrice de C ++, Bjarne Stroustrup dans un blog de 2014.

Voici le lien de l'article https://isocpp.org/blog/2014/06/stroustrup-lists

et citer celui-là,

Et, oui, ma recommandation est d'utiliser std :: vector par défaut.

Dans les commentaires, l'utilisateur @NathanOliver fournit également un autre bon blog, qui a des mesures plus concrètes. https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html .

CS Pei
la source