Rendimiento relativo de std :: vector vs. std :: list vs. std :: slist?

Para una lista simple vinculada en la que el acceso aleatorio a los elementos de la lista no es un requisito, ¿hay ventajas significativas (de rendimiento o de otro tipo) para usar std::list lugar de std::vector ? Si se requiere un recorrido hacia atrás, ¿sería más eficiente usar std::slist e reverse() la lista antes de iterar sobre sus elementos?

Como de costumbre, la mejor respuesta a las preguntas de rendimiento es perfilar ambas implementaciones para su caso de uso y ver cuál es más rápido.

En general, si tiene inserciones en la estructura de datos (que no sea al final), el vector puede ser más lento; de lo contrario, en la mayoría de los casos, se espera que el vector tenga un mejor rendimiento que la list si solo se trata de datos locales. son adyacentes en el conjunto de datos adyacentes en la memoria, entonces el siguiente elemento ya estará en la memoria caché del procesador y no tendrá que pasar la memoria a la memoria caché.

También tenga en cuenta que la sobrecarga de espacio para un vector es constante (3 punteros) mientras que la sobrecarga de espacio para una list se paga por cada elemento, esto también reduce la cantidad de elementos completos (datos más gastos generales) que pueden residir en el caché en cualquier momento.

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

Considere los siguientes puntos …

1] Recorrido:
Los nodos de lista se encuentran diseminados por todas partes en la memoria y, por lo tanto, el cruce de lista conduce a errores de caché . Pero el cruce de vectores es suave.

2] Inserción y eliminación:
El promedio del 50% de los elementos se debe cambiar cuando lo haces a un Vector, ¡pero los cachés son muy buenos para eso! Pero, con las listas, debe atravesar el punto de inserción / eliminación … así que de nuevo … ¡el caché falla! ¡Y sorprendentemente los vectores ganan este caso también!

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

Yout debe tener una razón para no usar un vector.


Referencia:
Aprendí esto en una charla de El señor Bjarne Stroustrup: https://youtu.be/0iWb_qi2-uI?t=2680

Simplemente no. La lista tiene ventajas sobre Vector, pero el acceso secuencial no es uno de ellos, 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 se 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 comprenda eso, comprenderá por qué las listas son buenas para inserciones y malas para el acceso aleatorio.

(Entonces, la iteración inversa de un vector es exactamente la misma que para la iteración directa: el iterador solo resta el tamaño de los elementos de datos cada vez, la lista todavía tiene que pasar al siguiente elemento mediante el puntero)

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

Una lista convencional (doblemente) vinculada le proporciona un tiempo constante de inserción y eliminación en cualquier parte de la lista; un vector solo da inserción y eliminación de tiempo constante amortizado al final de la lista. Para un vector de inserción y el tiempo de 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 comprender cómo se implementan. Una lista vinculada tiene un puntero siguiente y uno anterior para cada elemento. Un vector tiene una matriz de elementos direccionados por índice. De esto se puede ver que ambos pueden hacer avances y retrocesos eficaces, 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 puede ver por qué el tiempo de inserción es diferente entre las dos estructuras.

Algunos puntos de referencia rigurosos sobre el tema: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

Como han observado otros, el almacenamiento contiguo de memoria significa que std :: vector es mejor para la mayoría de las cosas. Prácticamente no existe una buena razón para usar std :: list, excepto para 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 la memoria caché y las velocidades de memoria principal (200x) y cómo el acceso de memoria contigua afecta el uso de la memoria caché. Ver Chandler Carruth (google) hablar sobre el problema aquí: https://www.youtube.com/watch?v=fHNmRkzxHWs

Y el diseño orientado a datos de Mike Acton aquí: https://www.youtube.com/watch?v=rX0ItVEVjHc

Vea esta pregunta para detalles sobre los costos:
¿Cuáles son las garantías de complejidad de los contenedores estándar?

Si tiene una barra deslizante y ahora quiere recorrerla en orden inverso, ¿por qué no cambiar el tipo a la lista en todas partes?