Respuesta

std::vector y std::list son diferentes contenedores de STL con implementaciones y comportamientos distintos.

• std::vector implementa un arreglo dinámico, los elementos están ubicados de forma continua en la memoria. Acceso rápido por índice (O(1)), rápida adición al final (O(1) amortizado), costosas inserciones y eliminaciones en el medio (O(n)), ya que los elementos se desplazan.
• std::list es una lista doblemente enlazada. Acceso aleatorio lento (O(n)), rápidas inserciones y eliminaciones en cualquier lugar de la lista (O(1)), más sobrecosto de memoria (dos punteros por elemento) y asignaciones/desasignaciones frecuentes.

Cuándo elegir:

• Utilice std::vector casi siempre, a menos que necesite inserciones/eliminaciones frecuentes en el medio.
• std::list solo es justificable cuando se necesitan inserciones/eliminaciones en cualquier lugar con grandes volúmenes de datos, cuando mover elementos en un vector resulta demasiado costoso.
• Para colecciones pequeñas, incluso si se necesita agregar en el medio, std::vector suele ser más rápido debido a la localidad de los datos.

Ejemplo:

std::vector<int> v;
v.push_back(1);
v[0] = 2; // acceso rápido por índice

std::list<int> l;
l.push_back(1);
// l[0] = 2; // Error: ¡std::list no tiene acceso por índice!

Pregunta engañosa

"¿Por qué std::list casi no se usa en proyectos modernos de C++, a pesar de la ventaja teórica en inserciones frecuentes en el medio de la colección?"

Respuesta: Porque en la práctica, debido a numerosas pequeñas asignaciones, pérdidas de localidad de datos (amigable con caché), la complejidad de la estructura y el pobre soporte para ciertas operaciones (std::list no es eficiente incluso para listas grandes debido al tiempo perdido en asignaciones y desasignaciones, y la desaceleración debida a saltos en la caché a menudo contrarresta la ganancia en asintótica). Además, los procesadores modernos son muy sensibles a la localidad de la caché, por lo que incluso con grandes volúmenes de datos, std::vector a menudo es más rápido en condiciones reales.

Ejemplos de errores reales debido a la falta de conocimiento de los matices del tema

---

Historia

En sistemas de tiempo real, para almacenar una cola de eventos, se eligió std::list debido a las frecuentes eliminaciones desde posiciones arbitrarias. Como resultado, el sistema se volvió 10 veces más lento debido a los frecuentes accesos al heap y la mala localización de los datos en memoria.

---

Historia

En un procesador gráfico, se almacenaron arreglos de vecinos en forma de std::list por las inserciones. Esto resultó en un aumento dramático del uso de memoria y degradación de las cachés L1/L2, sin obtener beneficios reales en velocidad.

---

Historia

En un servicio de generación de informes, cada informe se reunía a partir de objetos de Linked List. En pruebas de estrés, el servicio comenzó a "ralentizarse", y el perfilado mostró cuellos de botella en los gastos de asignación al trabajar con listas. Se cambiaron a vector — el resultado mejoró drásticamente.