Dans quel scénario dois-je utiliser un conteneur STL particulier?

Question

J'ai lu des articles sur les conteneurs STL dans mon livre sur C ++, plus précisément sur la section consacrée à 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 ... Mais je ne comprends pas encore dans quel scénario chacun d’entre eux est utilisé.

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

Answer 1

Cette aide-mémoire fournit un assez bon résumé des différents conteneurs.

Consultez l'organigramme en bas pour vous guider dans différents scénarios d'utilisation:

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

Answer 2

Voici un organigramme inspiré de la version de David Moore (voir ci-dessus) que j'ai créée et 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:

Answer 3

Réponse simple: utilisez std :: vector pour tout sauf si vous avez une vraie raison de faire autrement.

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

Answer 4

Regardez Effective STL par Scott Meyers. C’est bon pour expliquer comment utiliser le STL.

Si vous souhaitez stocker un nombre d'objets déterminé / indéterminé et que vous ne supprimez jamais d'objet, vous devez choisir un vecteur. C'est le remplacement par défaut pour un tableau C, et cela 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 souhaiterez probablement une liste ... car vous pouvez supprimer un élément sans déplacer aucun des éléments suivants - contrairement à vector. 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 valeur par clé. Si vous avez besoin de plus d'une valeur par clé, vous pouvez utiliser un vecteur / une liste comme valeur sur la carte ou utiliser une carte multiple.

Ce n'est pas dans la STL, mais dans la mise à jour de la TR1 de la TR1: 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 voudrez peut-être 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 contient une recherche de O (1) au lieu d’une recherche de O (log n) pour la carte.

Answer 5

J'ai repensé le diagramme pour lui donner 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 utilisent les conteneurs de base pour mettre en œuvre une politique.
2. Dans un premier temps, l’organigramme doit diviser le processus de décision en fonction des principales situations sur lesquelles nous devons nous prononcer, puis préciser chaque cas.
3. Certains conteneurs étendus ont la possibilité de choisir un conteneur de base différent comme conteneur interne. L’organigramme doit prendre en compte les situations dans lesquelles chacun des conteneurs de base peut être utilisé.

L'organigramme:

Plus d'informations dans ce lien .

Answer 6

Un point important mentionné brièvement jusqu'à présent est que si vous avez besoin de mémoire contiguë (comme un tableau C), vous ne pouvez utiliser que vecteur , tableau , ou chaîne .

Utilisez array si la taille est connue au moment de la compilation.

Utilisez chaîne si vous devez uniquement utiliser des types de caractères et avez besoin d'une chaîne, pas seulement d'un conteneur à usage général.

Utilisez vector dans tous les autres cas ( vector devrait néanmoins être le choix par défaut du conteneur dans la plupart des cas).

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

Answer 7

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

vecteur : mise en page 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 de trouver un objet contenu par index, par ex. myVector [10]. Utilisez l’endroit où vous auriez utilisé un tableau en C. Bien où vous avez beaucoup d’objets simples (par exemple, int). N'oubliez pas d'utiliser reserve () avant d'ajouter de nombreux objets au conteneur.

list : faible surcharge de mémoire par objet contenu. Efficace pour itérer. Ajouter, insérer et effacer sont bon marché. Utilisez l’emplacement où vous auriez utilisé une liste chaînée dans C.

set (et multiset ): surcharge de mémoire importante par objet contenu. Utilisez-le lorsque vous avez besoin de savoir rapidement si ce conteneur contient un objet donné ou de fusionner les conteneurs efficacement.

carte (et carte multiple ): surcharge de mémoire importante par objet contenu. Utilisez l’emplacement où vous souhaitez stocker les paires clé-valeur et recherchez rapidement les valeurs par clé.

L’organigramme du aide-mémoire proposé par zdan fournit un guide plus exhaustif.

Answer 8

L’une des leçons que j’ai apprises est la suivante: Essayez de l’emballer 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ébut et vous fait gagner du temps en débogage lorsque vous souhaitez interrompre l'exécution dès que quelqu'un exécute l'opération x sur cette structure.

Sélection de la structure de données idéale pour un travail:

Chaque structure de données fournit certaines opérations pouvant varier en complexité temporelle:

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

Vous devez essentiellement deviner, sur quelles opérations seront effectuées le plus, et utiliser une structure de données qui a cette opération sous la forme O (1).

Simple, n'est-ce pas (-:

Answer 9

J'ai développé le organigramme fantastique de Mikael Persson . J'ai ajouté des catégories de conteneurs, le conteneur de tableaux et des notes. Si vous souhaitez disposer de votre propre copie, ici est le dessin Google. . Merci, Mikael d'avoir préparé le terrain! Sélecteur de conteneurs C ++

Answer 10

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

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

Voici le lien pour 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 présente des mesures plus concrètes. https://baptiste-wicht.com/ posts / 2012/12 / cpp-benchmark-vector-list-deque.html .