Les conteneurs : l’embarras du choix

Article original : I don’t know which container to use (and at this point I’m too afraid to ask) | Belay the C++ (belaycpp.com)
Traductrice : Chloé Lourseyre

Quand on parle de conteneurs en C++, c’est std::vector qui remporte la palme de la plus utile (et utilisée) d’entre toutes (juste devant l’occasionnelle std::map pour les fois où on a besoin d’une association clé-valeur¹). Ainsi, c’est facile d’oublier que d’autres types de conteneurs existent.

Chaque conteneur a ses forces et ses faiblesses. Si vous avez tendance à oublier quelles elles sont pour chacun, cet article est un bon début.

Avertissement : Tous les conteneurs C++ ne sont pas listés ici, juste ceux qui sont les plus utiles (d’après moi). Si vous voulez aller plus loin, vous trouverez deux liens en addendum qui vous renverront vers des documentations plus complètes.

Comment choisir un conteneur

Critères

Premier™ critère : séquentiel ou associatif

La première question que vous devez vous poser est : est-ce que mon conteneur est séquentiel ou associatif ?

Dans les conteneurs séquentiels, les données sont organisées de manière ordonnée et séquentielle, avec chaque valeur à la suite de la précédente. En mémoire, ce n’est pas toujours contigüe (et souvent ça ne l’est pas), mais en pratique, vous accédez à une valeur avec l’indice de sa position dans le conteneur.

Contrairement aux conteneurs séquentiels, les conteneurs associatifs ne conservent pas les données en tant que séquence, mais en associant la valeur à une clé. À la place d’utiliser un indice pour accéder à la valeur, on utilise la clé.

Critères des conteneurs séquentiels

• Est-ce que la taille du conteneur est statique ? Si oui, c’est un std::array que vous cherchez (et les autres critère ne sont de toute façon pas importants). Dans tout autre cas de figure, vous devez vous en référer aux autres critères.
• Est-ce que la taille du conteneur va beaucoup varier ? Ce critère est important pour l’allocation mémoire. Si vous faites beaucoup varier la taille d’un conteneur qui n’est pas prévu pour ça, vous pourrez ressentir des ralentissements et une surutilisation de la mémoire².
• Est-ce que l’ordre est important ? Ce critère concerne les structures de données où on ne peut ajouter et retirer des valeurs qu’au début ou à la fin (c’est à dire les structures FIFO et FILO).
• Est-ce que vous avez besoin d’insérer/supprimer des valeurs aux extrémités du conteneur (c’est-à-dire au début et à la fin) ? Certains conteneurs sont plus efficaces que d’autres pour ces opérations.
• Est-ce que vous avez besoin d’insérer/supprimer des valeurs au milieu de la structure ? Tout comme le critère précédent, parfois vous devez faire beaucoup d’ajout et de suppressions, mais au milieu de la structure. C’est l’apanage d’autres types de conteneurs.
• Est-ce que vous avez besoin de trouver le n^ième élément ? En fonction du conteneur, la recherche n’est pas toujours optimale.
• Est-ce que vous avez besoin de fusionner des collections ? En fonction du conteneur, la fusion de deux collections n’est pas toujours optimale non plus (certaines ont besoin de réallouer la mémoire et d’autres non).

Critères des conteneurs associatifs

• Il y a deux sortes de structures associatives : celles qui associent une clé à une valeur (éventuellement de types différents), ce sont les map, et celles pour lesquelles la clé est la valeur, et ce sont les set.
• Par défaut, les clés sont uniques. Mais il existe une variante pour lesquelles les clés peuvent avoir plusieurs associations. Ce sont les multimap/multiset.
• La structure interne de ces conteneurs peut être implémentée de deux façons. Par défaut, elles sont ordonnées par clé. Mais elles peuvent aussi être non-ordonnées et utiliser une clé de hachage. Ce sont les versions unordered_ de chacun des conteneurs.

Note : la distinction ordonné/non-ordonné est importante (voire primordiale) pour les conteneurs associatifs. La plupart du temps, les conteneurs associatifs ordonnés sont implémentés sur des arbres binaires équilibrés, tandis que les non-ordonnés sont des tables de hachage. Cela a un impact sur les performances et sur le fait que, pour les tables de hachage, le type de valeur n’a pas besoin d’implémenter un opérateur de comparaison.

La matrice des conteneurs

Voici deux tableaux – un pour les conteneurs séquentiels et un pour les conteneurs associatifs.

Chaque tableau représente quels critères s’appliquent le mieux pour chaque conteneur³.

Conteneurs séquentiels

Conteneurs associatifs

Résumé sous forme de diagramme de flux

Voici un résumé simple à lire, sous forme d’un diagramme de flux, qui permet de choisir quel conteneur choisir en toute circonstance⁴ : Joe Gibson’s data structure selection flowchart.

Qu’en est-il de la réalité des gens véritables ?

Comme je l’ai mentionné dans l’introduction, dans la vraie vie std::vector et std::map sont la plupart du temps largement suffisants. Avec ça en tête, à quel point est-il utile de chercher le conteneur « optimal » à chaque fois ?

Sémantiquement, chaque conteneur est lié à la manière dont on l’utilise. Quand vous voyez deque, vous pensez « insérer et supprimer aux extrémités », quand vous voyez queue, vous pensez « insérer au début et supprimer à la fin », quand vous voyez list, vous pensez « insérer et supprimer au milieu ».

On voit chaque conteneur en fonction de comment on les utilise, plus que à quel point ils sont efficaces dans telle ou telle situation (ce qui est lié mais pas équivalent). Il y a beaucoup d’opérations qui sont disponibles dans plusieurs conteneurs à la fois. Par exemple, on peut très facilement ajouter et enlever des valeurs à la fin d’un vector, de même que dans un deque (dans les deux cas, on utilise les fonctions membre push_back et pop_back).

Vous avez peut-être envie d’objecter : « Mais ajouter et supprimer des valeurs à la fin d’un vecteur peut être très inefficace ! » En théorie, oui. Mais en pratique, ce n’est le cas que si vous vous trouvez dans une section critique du code. La plupart du temps, si vous êtes dans les 80% du Principe de Pareto, utiliser un vector plutôt qu’un deque n’aura aucun effet sur les performances.

Laissez-moi alors vous poser la question : si un vector fonctionne bien et n’impacte pas les performances, pourquoi utiliser un autre conteneur ?

Le vecteur est une des structures les plus faciles à comprendre grâce à leur similarité avec les bons-vieux-tableaux. Pour la plupart des développeurs, std::vector est le conteneur qu’ils savent le mieux utiliser. On ne devrait pas complexifier le code le plus mondain ni le rendre plus dur à lire, alors que ce n’est pas nécessaire.

Bien sûr, dès que vous avez des besoins spécifiques, vous devez utiliser le conteneur le plus approprié, mais ça n’arrive pas si souvent.

(J’ai pris std::vector comme exemple ici, mais c’est aussi valable pour std::map à propos des conteneurs associatifs)

Et l’optimisation alors ?

L’optimisation doit être un comportement a posteriori, et non a priori.

Quand vous écrivez du code, vous ne devez pas penser aux performances. Vous devez l’écrire de la manière la plus claire possible.

C’est seulement après que vous pouvez penser à l’impact de ce code sur les performances globales. En faisant éventuellement des benchmarks, des analyses statiques et/ou dynamiques pour savoir si il doit être optimisé et selon quels critères d’optimisation (temps d’exécution ? Utilisation de la mémoire ? etc.).

Si le code que vous écrivez n’est pas dans les 20% du Principe de Pareto, vous ne devriez même pas penser aux performances. S’il est dans ces 20%, vous devez y penser après l’avoir écrit.

Une approche plus efficace

Laissez-moi vous présenter le diagramme de flux suivant, dans le même esprit que celui de Joe Gibson, qui résume les propos de la section précédente :

Le principe est simple. Vous avez deux questions à vous poser :

1. Est-ce que je peux faire ce dont j’ai besoin avec un vector ou une map ?
2. Est-ce que je suis dans une section critique du code ?

Si vous répondez « Oui » à la première, et « Non » à la deuxième, alors vous devriez utiliser std::vector ou std::map.

Conclusion

Il est plus qu’utile de connaître les différences entre les conteneurs du C++. Cependant, dans la vie quotidienne, il est plus pratique de ne pas trop y penser. C’est une erreur assez commune de sur-réfléchir à des problématiques qui ont des solutions simples. Mais ces connaissances ne sont pas perdues : de temps en temps, vous serez dans une situation assez spécifique qui nécessitera des connaissances avancées sur les conteneurs.

Le Principe de Pareto peut aussi s’appliquer à cela : plus de 80% des outils qu’on connaît sont utiles dans moins de 20% des situations.

Merci de votre attention et à la semaine prochaine !

Article original : I don’t know which container to use (and at this point I’m too afraid to ask) | Belay the C++ (belaycpp.com)
Traductrice : Chloé Lourseyre

Addenda

Sources et ressources

Le diagramme de flux de Gibson vient d’un repo GitHub où vous pourrez trouver d’autres informations utiles sur les conteneurs : cpp-cheat-sheet/Data Structures and Algorithms.md at master · gibsjose/cpp-cheat-sheet · GitHub.

Il existe aussi une autre fiche-résumé, plus dense, parlant des conteneurs (et d’autres sujets également) : C++ Cheat Sheets & Infographics | hacking C++ (hackingcpp.com).

Le diagramme de flux pour le choix des structures de données de Joe Gibson

Joe Gibson’s data structure selection flowchart (source: GitHub – gibsjose/cpp-cheat-sheet: C++ Syntax, Data Structures, and Algorithms Cheat Sheet)

Notes

1. En vérité, tout le monde peut se mettre d’accord sur le fait que std::unordered_map est meilleur que std::map. Mais en pratique, il y a bien plus d’usages indiscriminé de map que de sa contrrepartie.
2. De plus, ce n’est pas juste la taille globale qui importe, mais aussi la taille maximale locale. Par exemple, si un conteneur ne dépassera pas 20 valeurs dans une section critique du code, on peut pré-allouer ces 20 cases pour éviter toute réallocation sauvage, tout en conservant la flexibilité d’une structure dynamique.
3. Bien sûr, chaque conteneur peut faire la plupart des opérations indiquées. Mais les tableaux résument lesquels sont les plus efficaces pour chacune.
4. Malheureusement le diagramme ne présente pas les versions unordered_ des conteneurs associatifs. Mais vous pouvez y palier simplement en vous demandant : « Les valeurs doivent être ordonnées ? Si oui, map/set ; Si non, unordered_map/unordered_set« .