¿Cuál es la complejidad de las operaciones para los contenedores std::vector y std::list en C++?

std::vector

• Acceso por índice: O(1)
• Añadir al final (push_back): amortizado O(1)
• Inserción o eliminación en medio: O(n), ya que requiere desplazamiento de elementos
• Iteración: O(n)

std::list (lista doblemente enlazada)

• Acceso por índice: O(n), ya que requiere recorrido secuencial
• Inserción y eliminación en cualquier lugar (si hay un iterador): O(1)
• Iteración: O(n)

Por lo tanto, vector es eficiente para acceso rápido y añadir al final, mientras que list es adecuado para inserciones y eliminaciones frecuentes en medio sin necesidad de desplazar elementos.