Comment puis-je sélectionner efficacement un conteneur de bibliothèque standard dans C ++ 11?

Il existe une image bien connue (aide-mémoire) appelée "Choix du conteneur C ++". C'est un organigramme pour choisir le meilleur conteneur pour l'utilisation souhaitée.

Est-ce que quelqu'un sait s'il existe déjà une version C ++ 11 de celui-ci?

C'est le précédent:

Pas que je sache, mais cela peut être fait textuellement, je suppose. En outre, le graphique est légèrement décalé, car ce listn'est pas un si bon conteneur en général, et ni l'un ni l'autre forward_list. Les deux listes sont des conteneurs très spécialisés pour des applications de niche.

Pour créer un tel graphique, vous avez juste besoin de deux directives simples:

• Choisissez d'abord la sémantique
• Lorsque plusieurs choix sont disponibles, optez pour le plus simple

Se soucier des performances est généralement inutile au début. Les grandes considérations O ne prennent vraiment effet que lorsque vous commencez à gérer quelques milliers (ou plus) d'éléments.

Il existe deux grandes catégories de conteneurs:

• Conteneurs associatifs : ils ont une findopération
• Conteneurs de séquences simples

et vous pouvez construire plusieurs adaptateurs sur eux: stack, queue, priority_queue. Je vais laisser les adaptateurs ici, ils sont suffisamment spécialisés pour être reconnaissables.

Question 1: Associatif ?

• Si vous avez besoin de rechercher facilement par une clé, vous avez besoin d'un conteneur associatif
• Si vous avez besoin de trier les éléments, vous avez besoin d'un conteneur associatif ordonné
• Sinon, passez à la question 2.

Question 1.1: commandé ?

• Si vous n'avez pas besoin d'une commande spécifique, utilisez un unordered_conteneur, sinon utilisez son équivalent commandé traditionnel.

Question 1.2: Clé séparée ?

• Si la clé est distincte de la valeur, utilisez a map, sinon utilisez unset

Question 1.3: Duplicata ?

• Si vous souhaitez conserver les doublons, utilisez a multi, sinon ne le faites pas.

Exemple:

Supposons que plusieurs personnes soient associées à un identifiant unique et que je souhaite récupérer les données d'une personne à partir de son identifiant le plus simplement possible.

1. Je veux une findfonction, donc un conteneur associatif

   1.1. Je me fiche de la commande, donc d'un unordered_conteneur

   1.2. Ma clé (ID) est distincte de la valeur à laquelle elle est associée, donc unmap

   1.3. L'ID est unique, donc aucun doublon ne doit s'y glisser.

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

Question 2: Mémoire stable ?

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

Question 2.1: Lequel ?

• Installez-vous pour un list; a forward_listn'est utile que pour une moindre empreinte mémoire.

Question 3: dimensionné dynamiquement ?

• Si le conteneur a une taille connue (au moment de la compilation), et que cette taille ne sera pas modifiée au cours du programme, et que les éléments sont constructibles par défaut ou que vous pouvez fournir une liste d'initialisation complète (en utilisant la { ... }syntaxe), alors utilisez un array. Il remplace le C-array traditionnel, mais avec des fonctions pratiques.
• Sinon, passez à la question 4.

Question 4: Double-terminé ?

• Si vous souhaitez pouvoir supprimer des éléments de l'avant et de l'arrière, utilisez a deque, sinon utilisez a vector.

Vous noterez que, par défaut, sauf si vous avez besoin d'un conteneur associatif, votre choix sera un vector. Il s'avère que c'est aussi la recommandation de Sutter et Stroustrup .

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

Quand NE PAS utiliser std :: vector

Par défaut, si vous avez besoin d'un conteneur de trucs, utilisez std::vector. Ainsi, tout autre conteneur n'est justifié qu'en fournissant une fonctionnalité alternative à std::vector.

Constructeurs

std::vectorexige que son contenu soit constructible par déplacement, car il doit être capable de mélanger les éléments. Ce n'est pas un fardeau terrible à placer sur le contenu (notez que les constructeurs par défaut ne sont pas nécessaires , grâce à emplaceet ainsi de suite). Cependant, la plupart des autres conteneurs ne nécessitent aucun constructeur particulier (encore une fois, grâce à emplace). Donc, si vous avez un objet pour lequel vous ne pouvez absolument pas implémenter un constructeur de déplacement, vous devrez choisir autre chose.

Un std::dequeserait le remplacement général, ayant de nombreuses propriétés de std::vector, mais vous ne pouvez insérer qu'aux deux extrémités du deque. Les inserts au milieu nécessitent un déplacement. A std::listn'impose aucune exigence sur son contenu.

Besoin de booléens

std::vector<bool>n'est pas. Eh bien, c'est standard. Mais ce n'est pas un vectordans le sens habituel, car les opérations qui le std::vectorpermettent normalement sont interdites. Et il ne contientbool certainement pas l' art .

Par conséquent, si vous avez besoin d'un vectorcomportement réel d'un conteneur de bools, vous n'allez pas l'obtenir std::vector<bool>. Vous devrez donc respecter un std::deque<bool>.

Recherche

Si vous avez besoin de trouver des éléments dans un conteneur et que la balise de recherche ne peut pas être simplement un index, vous devrez peut-être abandonner std::vectoren faveur de setet map. Notez le mot clé « peut »; un tri std::vectorest parfois une alternative raisonnable. Ou Boost.Container's flat_set/map, qui implémente un fichier trié std::vector.

Il existe désormais quatre variantes de celles-ci, chacune ayant ses propres besoins.

• Utilisez a maplorsque la balise de recherche n'est pas la même chose que l'élément que vous recherchez. Sinon, utilisez un set.
• À utiliser unorderedlorsque vous avez beaucoup d'éléments dans le conteneur et que les performances de recherche doivent absolument l'être O(1)plutôt que O(logn).
• À utiliser multisi vous avez besoin que plusieurs éléments aient la même balise de recherche.

Commande

Si vous avez besoin qu'un conteneur d'éléments soit toujours trié en fonction d'une opération de comparaison particulière, vous pouvez utiliser un fichier set. Ou multi_setsi vous avez besoin de plusieurs éléments pour avoir la même valeur.

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

Stabilité

L'invalidation des itérateurs et des références pose parfois problème. Si vous avez besoin d'une liste d'éléments, de telle sorte que vous ayez des itérateurs / pointeurs vers ces éléments à divers autres endroits, alors std::vectorl'approche de l'invalidation peut ne pas être appropriée. Toute opération d'insertion peut entraîner une invalidation, selon la taille et la capacité actuelles.

std::listoffre une garantie ferme: un itérateur et ses références / pointeurs associés ne sont invalidés que lorsque l'élément lui-même est retiré du conteneur. std::forward_listest là si la mémoire est un problème sérieux.

Si c'est une garantie trop forte, std::dequeoffre une garantie plus faible mais utile. L'invalidation résulte d'insertions au milieu, mais les insertions en tête ou en queue ne provoquent que l'invalidation des itérateurs , pas des pointeurs / références aux éléments dans le conteneur.

Performances d'insertion

std::vector ne fournit qu'une insertion bon marché à la fin (et même dans ce cas, cela devient coûteux si vous soufflez de capacité).

std::listest cher en termes de performances (chaque élément nouvellement inséré coûte une allocation de mémoire), mais il est cohérent . Il offre également la capacité parfois indispensable de mélanger des articles pour pratiquement aucun coût de performance, ainsi que d'échanger des articles avec d'autres std::listconteneurs du même type sans perte de performance. Si vous devez beaucoup mélanger les choses , utilisez std::list.

std::dequefournit une insertion / retrait en temps constant à la tête et à la queue, mais l'insertion au milieu peut être assez coûteuse. Donc, si vous avez besoin d'ajouter / supprimer des éléments de l'avant comme de l'arrière, c'est std::dequepeut-être ce dont vous avez besoin.

Il convient de noter que, grâce à la sémantique de déplacement, std::vectorles performances d'insertion peuvent ne pas être aussi mauvaises qu'auparavant. Certaines implémentations ont implémenté une forme de copie d'élément basée sur la sémantique (la soi-disant "swaptimisation"), mais maintenant que le déplacement fait partie du langage, il est mandaté par le standard.

Aucune allocation dynamique

std::arrayest un bon conteneur si vous voulez le moins d'allocations dynamiques possibles. C'est juste un wrapper autour d'un C-array; cela signifie que sa taille doit être connue au moment de la compilation . Si vous pouvez vivre avec cela, utilisez std::array.

Cela étant dit, utiliser std::vectoret utiliser reserveune taille fonctionnerait tout aussi bien pour un borné std::vector. De cette façon, la taille réelle peut varier et vous n'obtenez qu'une seule allocation de mémoire (sauf si vous faites exploser la capacité).

Voici la version C ++ 11 de l'organigramme ci-dessus. [publié à l'origine sans attribution à son auteur original, Mikael Persson ]

Voici un tour rapide, même s'il a probablement besoin de travail

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 énormément de la version C ++ 03, principalement en raison du fait que je n'aime vraiment pas les nœuds liés. Les conteneurs de nœuds liés peuvent généralement être battus en performances par un conteneur non lié, sauf dans quelques rares situations. Si vous ne savez pas quelles sont ces situations et que vous avez accès à Boost, n'utilisez pas de conteneurs de nœuds liés. (std :: list, std :: slist, std :: map, std :: multimap, std :: set, std :: multiset). Cette liste se concentre principalement sur les conteneurs petits et moyens, car (A) c'est 99,99% de ce que nous traitons dans le code, et (B) Un grand nombre d'éléments nécessitent des algorithmes personnalisés, pas des conteneurs différents.