El rendimiento relativo de std::vector vs std::list vs std::slist?

La estructura de datos predeterminada en la que pensar en C++ es el Vector .

Considere los siguientes puntos...

1] Recorrido:
Los nodos de la lista están dispersos por todas partes en la memoria y, por lo tanto, el recorrido de la lista conduce a errores de caché. Pero el recorrido de los vectores es suave.

2] Inserción y supresión:
El promedio de 50% de los elementos debe ser desplazado cuando se hace eso a un vector, pero cachés son muy buenos en eso! Pero, con listas, necesitas to atravesar hasta el punto de inserción/supresión... otra vez... cache falla! ¡Y sorprendentemente los vectores ganan este caso también!

3] Almacenamiento:
Cuando se utilizan listas, hay 2 punteros por elementos (hacia adelante y hacia atrás) por lo que una Lista es mucho más grande que un vector! Los vectores necesitan solo un poco más de memoria que los elementos reales necesitan.

Usted debe tener una razón para no utilizar un vector.

Simplemente no. La lista tiene ventajas sobre el Vector, pero el acceso secuencial no es una de ellas - si eso es todo lo que estás haciendo, entonces un vector es mejor.

Sin embargo.. un vector es más caro para agregar elementos adicionales que una lista, especialmente si está insertando en el medio.

Comprenda cómo se implementan estas colecciones: un vector es una matriz secuencial de datos, una lista es un elemento que contiene los datos y punteros a los siguientes elementos. Una vez que entiendas eso, comprenda por qué las listas son buenas para inserciones y malas para el acceso aleatorio.

(por lo tanto, la iteración inversa de un vector es exactamente lo mismo que para la iteración hacia adelante: el iterador solo resta el tamaño de los elementos de datos cada vez, la lista todavía tiene que saltar al siguiente elemento a través del puntero)

Si necesita un recorrido hacia atrás, es poco probable que una slist sea la estructura de datos para usted.

Una lista convencional (doblemente) vinculada le da tiempo constante de inserción y eliminación en cualquier parte de la lista; un vector solo da tiempo constante amortizado de inserción y eliminación al final de la lista. Para un vector, el tiempo de inserción y eliminación es lineal en cualquier lugar que no sea el final. Esta no es toda la historia; también hay factores constantes. Un vector es una estructura de datos más simple que tiene ventajas y desventajas según el contexto.

La mejor manera de entender esto es entender cómo se implementan. Una lista vinculada tiene un puntero siguiente y un puntero anterior para cada elemento. Un vector tiene una matriz de elementos abordados por index. A partir de esto, puede ver que ambos pueden hacer un recorrido eficiente hacia adelante y hacia atrás, mientras que solo un vector puede proporcionar un acceso aleatorio eficiente. También puede ver que la sobrecarga de memoria de una lista vinculada es por elemento, mientras que para el vector es constante. Y también se puede ver por qué el tiempo de inserción es diferente entre las dos estructuras.

Algunos parámetros rigurosos sobre el tema: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

Como han señalado otros, el almacenamiento de memoria contigua significa que std::vector es mejor para la mayoría de las cosas. Prácticamente no hay una buena razón para usar std::list, excepto por pequeñas cantidades de datos (donde todos pueden caber en la caché) y/o donde el borrado y la reinserción son frecuentes. Las garantías de complejidad no se relacionan con el rendimiento en el mundo real debido a la diferencia entre las velocidades de caché y memoria principal (200x) y cómo el acceso a memoria contigua afecta el uso de caché. Ver Chandler Carruth (Google) hablar sobre el tema aquí: https://www.youtube.com/watch?v=fHNmRkzxHWs

Y el Diseño Orientado a Datos de Mike Acton hablan aquí: https://www.youtube.com/watch?v=rX0ItVEVjHc

Consulte esta pregunta para obtener más detalles sobre los costos:
¿Cuáles son las garantías de complejidad de los contenedores estándar

Si tiene una ranura y ahora desea recorrerla en orden inverso, ¿por qué no cambiar el tipo a list everywhere?