Comment puis-je sélectionner efficacement un conteneur de la bibliothèque Standard du C ++11 ?

Question

Il y a une image bien connue (antisèche) intitulée « Choice conteneur C++ ». C’est un diagramme de choisir le meilleur récipient pour l’usage voulu.

Quelqu'un sait-il s’il existe déjà une version C ++11 de celui-ci ?

Il s’agit de l’antérieure :

Answer 1

Pas que je sache, cependant, il peut être fait sous forme de texte, je suppose. Aussi, le tableau est légèrement en dehors, parce qu' list n'est pas un bon récipient en général, et ni est - forward_list; les deux listes sont très emballages spécialisés pour des applications de niche.

Pour construire un tel graphique, vous avez juste besoin de deux simples lignes directrices:

• Choisissez pour la sémantique de la première
• Lorsque plusieurs choix sont disponibles, rendez-vous pour le plus simple

Se soucier de la performance est généralement inutile au premier abord, le big O seulement vraiment le coup lorsque vous commencez à la manipulation de quelques milliers (ou plus) d'éléments.

Il y a deux grandes catégories de conteneurs:

• Associatif conteneurs: ils ont un find fonctionnement
• Simple Séquence de conteneurs

et puis vous pouvez créer plusieurs cartes sur le dessus d'eux: stack, queue, priority_queue. Je vais laisser les cartes ici, ils sont assez spécialisés pour être reconnaissable.

---

Question 1: Associatif ?

• Si vous avez besoin pour effectuer facilement une recherche par une clé, alors vous avez besoin d'un conteneur associatif
• Si vous avez besoin d'avoir les éléments triés, alors vous besoin d'un ordre conteneur associatif
• Sinon, passer à la question 2.

Question 1.1: Commandé ?

• Si vous n'avez pas besoin d'un ordre spécifique, utiliser un unordered_ conteneur, sinon utiliser son traditionnel commandé homologue.

Question 1.2: Clé Distinct ?

• Si la clé est séparée de la valeur, utiliser un map, sinon utiliser un set

Question 1.3: Les Doublons ?

• Si vous souhaitez conserver les doublons utiliser un multi, sinon, ne pas.

Exemple:

Supposons que j'ai plusieurs personnes avec un ID unique associée, et je voudrais récupérer une personne données à partir de son ID aussi simplement que possible.

1. Je veux un find la fonction, donc un conteneur associatif

   1.1. Je me moque de l'ordre, ainsi que l' unordered_ conteneur

   1.2. Mon key (ID) est distincte de la valeur, il est associé avec, donc, une map

   1.3. L'ID est unique, donc pas de duplicata doit ramper dans.

La réponse finale est: std::unordered_map<ID, PersonData>.

---

Question 2: la Mémoire stable ?

• Si les éléments doivent être stables en mémoire (c'est à dire, ils ne devrait pas bouger lorsque le conteneur lui-même est modifié), puis utiliser quelques - list
• Sinon, passer à la question 3.

Question 2.1: Qui ?

• Se contenter d'un list; forward_list n'est utile que pour la moindre empreinte mémoire.

---

Question 3: Dynamiquement la taille ?

• Si le conteneur a une taille connue (au moment de la compilation), et de cette taille ne sera pas modifié pendant la durée du programme, et les éléments sont par défaut constructibles , ou vous pouvez fournir une liste d'initialisation (à l'aide de l' { ... } de la syntaxe), puis utiliser une array. Il remplace la traditionnelle C-tableau, mais avec des fonctions pratiques.
• Sinon, passer à la question 4.

---

Question 4: Double-clos ?

• Si vous souhaitez être en mesure de supprimer des éléments de l'avant et à l'arrière, puis d'utiliser un deque, sinon utiliser un vector.

---

Il est à noter que, par défaut, sauf si vous avez besoin d'un conteneur associatif, votre choix sera un vector.

Answer 2

J'aime Matthieu réponse, mais je vais reformuler l'organigramme comme ceci:

Quand ne PAS utiliser std::vector

Par défaut, si vous avez besoin d'un conteneur de trucs, utilisez std::vector. Ainsi, tous les autres conteneur n'est justifiée par la fourniture de certaines fonctionnalités alternative à l' std::vector.

Les constructeurs

std::vector exige que son contenu sont déplacer constructible, car il doit être capable de mélanger les éléments autour. Ce n'est pas un fardeau terrible à placer sur le contenu (à noter que les constructeurs par défaut sont pas nécessaires, grâce à l' emplace et ainsi de suite). Cependant, la plupart des autres contenants ne nécessitent pas toute particulière constructeur (encore une fois, grâce à l' emplace). Donc, si vous avez un objet où vous absolument ne peut pas mettre en œuvre un constructeur de déplacement, alors vous aurez à choisir autre chose.

Un std::deque serait le remplacement général, ayant de nombreuses propriétés de l' std::vector, mais vous ne pouvez insérer qu'aux extrémités de la deque. Des Inserts au milieu nécessitent le déplacement. Un std::list n'impose aucune exigence sur son contenu.

Besoins Bool

std::vector<bool> ... n'est pas. Eh bien, c'est du standard. Mais ce n'est pas un vector dans le sens habituel du terme, comme des activités qui std::vector permet en principe interdit. Et le plus certainement ne contient pas d' bools.

Par conséquent, si vous avez besoin d'une réelle vector comportement à partir d'un conteneur de bools, vous n'allez pas à l'obtenir à partir d' std::vector<bool>. De sorte que vous aurez à faire avec un std::deque<bool>.

La recherche

Si vous avez besoin de trouver des éléments dans un conteneur, et le tag de recherche ne peut pas simplement être un indice, alors vous pourriez avoir besoin d'abandonner std::vector en faveur de l' set et map. Remarque le mot-clé "mai"; une triés std::vector est parfois une solution de rechange raisonnable. Ou Boost.Conteneur flat_set/map, qui met en œuvre triés std::vector.

Il y a maintenant quatre variantes de ces, chacune avec leurs propres besoins.

• Utiliser un map lors de la recherche de la balise n'est pas la même chose que le point que vous êtes à la recherche pour elle-même. Sinon, utiliser un set.
• Utiliser unordered quand vous avez beaucoup d'éléments dans le conteneur et la recherche de la performance doit absolument être O(1), plutôt que d' O(logn).
• Utiliser multi si vous avez besoin de plusieurs éléments ont le même tag de recherche.

La commande

Si vous avez besoin d'un conteneur d'éléments de toujours être triés sur la base de la comparaison opération, vous pouvez utiliser un set. Ou un multi_set si vous avez besoin de plusieurs éléments ont la même valeur.

Ou vous pouvez utiliser un triées std::vector, mais vous devrez garder de tri.

La stabilité

Lorsque les itérateurs et les références sont invalidés est parfois un sujet de préoccupation. Si vous avez besoin d'une liste d'éléments, tels que vous avez des itérateurs/pointeurs vers ces articles dans divers autres lieux, alors std::vectors'approche à l'invalidation peut ne pas être approprié. Tout d'insertion opération peut entraîner l'invalidation, en fonction de la taille et de la capacité.

std::list offre une garantie solide: un itérateur et de ses références/pointeurs ne sont invalidés lorsque l'élément est supprimé du conteneur. std::forward_list est-il si la mémoire est une source de grave préoccupation.

Si c'est trop fort une garantie, std::deque offre une plus faible mais utile de garantie. L'Invalidation des résultats de insertions dans le milieu, mais les insertions à la tête ou de queue, ne provoque que l'invalidation des itérateurs, pas des pointeurs/références à des éléments dans le conteneur.

L'Insertion De La Performance

std::vector seulement fournit à bas prix d'insertion à la fin (et même alors, il devient coûteux si vous souffler la capacité).

std::list est coûteux en termes de performances (chaque nouvel élément inséré des coûts de l'allocation de mémoire), mais c'est cohérent. Il offre également la parfois indispensable capacité à mélanger des éléments autour de pratiquement aucune incidence sur les performances, ainsi que pour échanger des objets avec d'autres std::list des conteneurs de même type, sans perte de performance. Si vous avez besoin de mélanger les choses autour d' un lot, utilisez std::list.

std::deque fournit à constante de temps de l'insertion/retrait à la tête et la queue, mais l'insertion dans le milieu peut être assez cher. Donc, si vous avez besoin d'ajouter/enlever des choses de l'avant et à l'arrière, std::deque pourrait être ce dont vous avez besoin.

Il convient de noter que, grâce à la sémantique de déplacement, std::vector d'insertion de la performance ne peut pas être aussi mauvais qu'il l'habitude d'être. Certaines implémentations mis en place un formulaire de déplacer la sémantique en fonction de l'élément de la copie (le soi-disant "swaptimization"), mais maintenant que le déménagement est une partie de la langue, il est mandaté par le standard.

Aucun Des Allocations Dynamiques

std::array est une amende conteneur si vous voulez le moins possible des allocations dynamiques. C'est juste un wrapper autour d'une C-tableau; ce qui signifie que sa taille doit être connu au moment de la compilation. Si vous pouvez vivre avec ça, puis utilisez std::array.

Cela étant dit, l'utilisation d' std::vector et reserveing une taille aussi bien délimité std::vector. De cette façon, la taille réelle peut varier, et vous n'aurez qu'une seule allocation de mémoire (à moins que vous souffler la capacité).

Answer 3

Voici la version +11 de C ++ de l’organigramme ci-dessus.

Answer 4

Voici un tour rapide, mais il a probablement besoin de travailler

Should the container let you manage the order of the elements?
Yes:
  Will the container contain always exactly the same number of elements? 
  Yes:
    Does the container need a fast move operator?
    Yes: std::vector
    No: std::array
  No:
    Do you absolutely need stable iterators? (be certain!)
    Yes: boost::stable_vector (as a last case fallback, std::list)
    No: 
      Do inserts happen only at the ends?
      Yes: std::deque
      No: std::vector
No: 
  Are keys associated with Values?
  Yes:
    Do the keys need to be sorted?
    Yes: 
      Are there more than one value per key?
      Yes: boost::flat_map (as a last case fallback, std::map)
      No: boost::flat_multimap (as a last case fallback, std::map)
    No:
      Are there more than one value per key?
      Yes: std::unordered_multimap
      No: std::unordered_map
  No:
    Are elements read then removed in a certain order?
    Yes:
      Order is:
      Ordered by element: std::priority_queue
      First in First out: std::queue
      First in Last out: std::stack
      Other: Custom based on std::vector????? 
    No:
      Should the elements be sorted by value?
      Yes: boost::flat_set
      No: std::vector

Vous remarquerez peut-être que cela diffère sauvagement à partir du C++03 version, principalement en raison du fait que je n'aime vraiment pas liée nœuds. Le nœud lié conteneurs peuvent généralement être battu dans les performances par un non-lié conteneur, sauf dans quelques rares situations. Si vous ne savez pas ce que ces situations sont, et ont accès à stimuler, n'utilisez pas lié nœud de conteneurs. (std::list, std::slist, std::map, std::multimap, std::set, std::multiset). Cette liste se concentre principalement sur les petites et moyennes récipients à paroi, parce que (Un) c'est de 99,99% de ce que nous traitons dans le code, et (B) un Grand nombre d'éléments des algorithmes personnalisés, pas des récipients différents.