Quelle est la complexité des opérations pour les conteneurs std::vector et std::list en C++?

std::vector

• Accès par index: O(1)
• Ajout à la fin (push_back): amorti O(1)
• Insertion ou suppression au milieu: O(n), car nécessite un décalage des éléments
• Itération: O(n)

std::list (liste doublement chaînée)

• Accès par index: O(n), car nécessite une traversée séquentielle
• Insertion et suppression à n'importe quel endroit (si un itérateur est disponible): O(1)
• Itération: O(n)

Ainsi, vector est efficace pour un accès rapide et l'ajout à la fin, tandis que list est adapté pour des insertions et suppressions fréquentes au milieu sans avoir besoin de déplacer les éléments.