Réponse

std::vector et std::list sont différents conteneurs STL avec des implémentations et des comportements distincts.

• std::vector implémente un tableau dynamique, les éléments sont disposés de manière continue en mémoire. Accès rapide par index (O(1)), ajout rapide à la fin (amortissement O(1)), insertions et suppressions coûteuses au milieu (O(n)), car les éléments doivent être décalés.
• std::list est une liste doublement chaînée. Accès aléatoire lent (O(n)), insertions et suppressions rapides à n'importe quel endroit de la liste (O(1)), plus de frais généraux de mémoire (deux pointeurs par élément) et des allocations/désallocations fréquentes.

Quand choisir :

• Utilisez std::vector presque toujours, à moins que des insertions/suppressions fréquentes au milieu ne soient nécessaires.
• std::list est justifié uniquement lorsque des insertions/suppressions sont requises à n'importe quel endroit avec un grand volume de données, lorsque le déplacement des éléments de vector est trop coûteux.
• Pour de petites collections, même si des ajouts au milieu sont nécessaires, std::vector est souvent plus rapide en raison de la localisation des données.

Exemple :

std::vector<int> v;
v.push_back(1);
v[0] = 2; // accès rapide par index

std::list<int> l;
l.push_back(1);
// l[0] = 2; // Erreur : std::list n'a pas d'accès par index !

Question piège

"Pourquoi std::list est-elle presque jamais utilisée dans les projets C++ modernes, malgré son avantage théorique pour les insertions fréquentes au milieu de la collection ?"

Réponse : Parce qu'en pratique, en raison de nombreuses petites allocations, pertes de localisation des données (friendly cache), complexité de la structure et mauvaise prise en charge de certaines opérations (std::list est inefficace même pour de grandes listes en raison du temps perdu sur l'allocation et la désallocation, et le ralentissement dû aux manques dans le cache surpasse souvent les gains d'asymptotique). De plus, les processeurs modernes sont très sensibles à la localisation cache, donc même avec de grands volumes de données, std::vector est souvent plus rapide dans des conditions réelles.

Exemples d'erreurs réelles dues à l'ignorance des subtilités du sujet

---

Histoire

Dans les systèmes temps réel, un std::list a été choisi pour stocker la file d'attente des événements en raison des suppressions fréquentes depuis des positions aléatoires. En conséquence, le système est devenu 10 fois plus lent en raison des fréquents accès au heap et de la mauvaise localisation des données en mémoire.

---

Histoire

Dans un processeur graphique, des tableaux de voisins ont été stockés sous forme de std::list pour des insertions. Cela a conduit à une augmentation dramatique de l'utilisation de la mémoire et à une dégradation des caches L1/L2, alors qu'aucun gain réel de vitesse n'a été obtenu.

---

Histoire

Dans un service de génération de rapports, chaque rapport était constitué d'objets Linked List. Lors des tests de stress, le service a commencé à "ralentir" et le profilage a montré des goulets d'étranglement dans les coûts d'allocation lors du travail avec des listes. Ils sont passés à vector — le résultat s'est amélioré plusieurs fois.