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 le C++, en particulier la section sur la STL et ses conteneurs. Je comprends maintenant que chacun d'entre eux a ses 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 préférable.

Answer 1

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

Consultez l'organigramme en bas de page pour savoir lequel utiliser dans différents scénarios d'utilisation :

_{Créé par <a href="http://linuxsoftware.co.nz/" rel="noreferrer">David Moore </a>y <a href="http://creativecommons.org/licenses/by-sa/3.0/nz/" rel="noreferrer">sous licence CC BY-SA 3.0</a>}

Answer 2

Voici un organigramme inspiré de la version de David Moore (voir ci-dessus) que j'ai créée et qui est à jour (en grande partie) avec la nouvelle norme (C++11). Ce n'est que mon point de vue personnel, il n'est pas indiscutable, mais j'ai pensé qu'il pourrait être utile à cette discussion :

Answer 3

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

Quand tu trouves un cas où tu te dis : "Mince alors, std::vector ne fonctionne pas bien ici à cause de X", allez-y sur la base de X.

Answer 4

Regardez Effective STL par Scott Meyers. Il explique bien comment utiliser la STL.

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

Si vous voulez stocker un nombre indéterminé d'objets, mais que vous allez les ajouter et les supprimer, alors vous voulez probablement une liste... parce que vous pouvez supprimer un élément sans déplacer les éléments suivants - contrairement au vecteur. En effet, vous pouvez supprimer un élément sans déplacer les éléments suivants, contrairement à un vecteur. Cependant, la liste 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 groupe d'éléments et trouver uniquement les valeurs uniques de ces éléments, vous pouvez les lire dans un ensemble et les trier pour vous.

Si vous avez beaucoup de paires clé-valeur, et que vous voulez les trier par clé, alors une map est utile... mais elle ne peut contenir qu'une seule valeur par clé. Si vous avez besoin de plus d'une valeur par clé, vous pouvez utiliser un vecteur/une liste comme valeur dans la map, ou utiliser une multimap.

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 chercher par clé, et que vous ne vous souciez pas de leur ordre, vous pourriez vouloir utiliser un hash - qui est tr1::unordered_map. Je l'ai utilisé avec Visual C++ 7.1, où il était appelé stdext::hash_map. Il a un lookup de O(1) au lieu d'un lookup de O(log n) pour map.

Answer 5

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

vector : Disposition compacte avec peu ou pas de surcharge mémoire par objet contenu. Efficacité de l'itération. L'ajout, l'insertion et l'effacement peuvent être coûteux, en particulier pour les objets complexes. Bon marché pour trouver un objet contenu par index, par exemple monVecteur[10]. A utiliser là où vous auriez utilisé un tableau en C. Bon lorsque vous avez beaucoup d'objets simples (par exemple int). N'oubliez pas d'utiliser reserve() avant d'ajouter beaucoup d'objets dans le conteneur.

list : Faible surcharge de mémoire par objet contenu. Efficace pour l'itération. Append, insert et erase sont bon marché. A utiliser là où vous auriez utilisé une liste chaînée en C.

set (et multiset ) : Surcharge importante de mémoire par objet contenu. A utiliser lorsque vous avez besoin de savoir rapidement si ce conteneur contient un objet donné, ou de fusionner efficacement des conteneurs.

map (et multimap ) : Surcharge importante de mémoire par objet contenu. À utiliser lorsque vous souhaitez stocker des paires clé-valeur et rechercher rapidement des valeurs par clé.

Le diagramme de flux sur le antisèche suggéré par zdan fournit un guide plus exhaustif.