c++ - library - ¿Cuándo prefiere usar std:: list<T> en lugar de std:: vector<T>?

stl c++ español (11)

Así que mi pregunta es: ¿cuándo prefieres exactamente std::list sobre std::vector ?

Cuando necesito un contenedor secuencial en un área sensible al rendimiento y el perfil muestra que std::list es más rápido.

Hasta ahora, esto nunca me ha pasado.

(Podría sentir la tentación de probar std::list primero cuando tendría que almacenar objetos muy grandes con mucha inserción / extracción en el medio. Sin embargo, en la práctica, nunca me he encontrado con un caso de uso así).

Nunca he usado std::list<T> yo mismo. Me preguntaba cuándo la gente lo usa cuando ya tenemos std::vector<T> que es como matrices con memoria contigua. std::vector parece una elección perfecta cuando necesitamos un contenedor secuencial!

Así que mi pregunta es

¿Cuándo prefieres exactamente std::list sobre std::vector ? y por que exactamente
¿Cuándo prefieres std::vector sobre std::list ? ¿y por qué?

Si hay consideración de rendimiento, enuméralas también con una explicación / información detallada.

Si es posible, cita algunas referencias también, para apoyar tu respuesta.

Además de otras respuestas, los contenedores de base de nodo ( list / contenedores asociativos) pueden proporcionar una garantía de excepción sólida.
Incluso si una operación de mutación de contenedor (por ejemplo, inserción) lanza una excepción, todos los punteros / referencias / iteradores a los elementos siguen siendo válidos.
Sin embargo, los contenedores de memoria lineal (celda de memoria contigua por partes) pueden proporcionar solo una garantía básica. Cuando una inserción se lanza, incluso si la inserción no se ejecuta realmente, los punteros / referencias / iteradores se pueden invalidar (aunque el contenedor mismo se puede destruir de forma segura).

Algunos dirían que, posiblemente, nunca más debería volver a utilizar la lista vinculada en su código . ;)

Un problema es que los vectores tienen una ubicación de referencia mucho mejor, y las grandes ganancias de rendimiento resultantes de esto, en muchos casos, superarán las ventajas de operaciones más (algorítmicamente) eficientes para cosas como eliminar e insertar en una lista vinculada.

(Consulte la publicación del blog que se encuentra más arriba para conocer más sobre este tema específico, con puntos de referencia, etc.)

Por lo tanto, a menudo un std :: vector superará a std :: list, incluso si está realizando un cierto número de operaciones para las cuales una lista sería más natural (por ejemplo, la eliminación de elementos arbitrarios, la inserción en una posición arbitraria o el empalme).

Pero tenga en cuenta que, incluso cuando realiza muchas operaciones de este tipo, puede que sea mejor que "aloje" su lista dentro del búfer contiguo de un std :: vector.

Discuto esto con más detalle en esta publicación del blog, con algunos diagramas y ejemplos de código: http://upcoder.com/12/vector-hosted-lists/

En el caso específico cuando necesita eliminar elementos arbitrarios, pero no necesita insertar en posiciones o empalmes arbitrarios, una buena alternativa a una lista enlazada completa puede ser simplemente marcar las entradas como "muertas" y omitir estas entradas muertas durante la iteración.

Debería usar una lista cuando esté haciendo muchas eliminaciones / inserciones.

Se puede usar Vector si el tamaño total de los elementos no cambia mucho, y si se hace algún intercambio.

Hay algunos compromisos que deben considerarse al elegir entre std :: list y std :: vector. Además, std :: list no se trata de memoria contigua, puede ser muy útil si no puede permitirse la invalidación del iterador o si necesita una inserción de tiempo constante amortizado en el inicio / medio / final.

Las únicas (pocas) veces que preferí std::list se debe a la función de miembro list::splice . Si está mezclando subintervalos dentro de una lista o entre listas, esta operación puede ser significativamente más rápida que usar std::vector .

Las listas son mejores para insertar o eliminar en cualquier lugar en el medio, los vectores son mejores para insertar al final.

Los vectores también son mejores para acceder a los elementos.

Este es un artefacto de la forma en que se implementan.

Entonces, si una colección cambia muy poco (en comparación con los accesos) o los cambios se concentran al final, usaría un vector.

Si la cantidad de cambios es sustancial (en comparación con los accesos) y no están al final, usaría una lista.

A modo de ejemplo, leer en una colección al inicio del programa y casi nunca cambiarlo (o si los cambios se están agregando al final), esto sería un buen candidato para un vector.

Por otro lado, una aplicación de guía telefónica para una estrella del rock particularmente popular y voluble, estaría mirando hacia una lista. En realidad, estaría buscando una conexión de base de datos, pero ese fue el mejor ejemplo que pude encontrar en poco tiempo :-)

En cuanto a las referencias, el último borrador de C ++ 0x indica en parte (23.3.4, listas):

Una lista es un contenedor de secuencias que admite iteradores bidireccionales y permite operaciones constantes de inserción y borrado en cualquier lugar dentro de la secuencia, con la administración del almacenamiento manejada automáticamente. A diferencia de los vectores y los deques, el acceso aleatorio rápido a los elementos de la lista no es compatible.

Sección 23.3.5 (sobre vectores):

Un vector es un contenedor de secuencias que admite iteradores de acceso aleatorio. Además, admite operaciones de inserción y borrado de tiempo constante (amortizado) al final; Insertar y borrar en el medio tomar tiempo lineal.

No necesito repetir lo básico, pero lo que aprendí de la manera difícil es que si el rendimiento de la inserción es relevante y tienes objetos "grandes", entonces realmente deberías considerar una lista std ::, incluso si solo estás insertando al final. (Bueno, una lista o posiblemente un vector de puntero inteligente / ptr_vector.)

Tuvimos algunos casos de uso en los que tuvimos que crear colecciones de un tamaño desconocido a priori de estructuras de múltiples pequeñas cadenas std :: y usar un rendimiento de inserción std :: vector totalmente eliminado y agregamos una sobrecarga de memoria no despreciable.

El problema con std :: vector en el escenario de inserción de conteo desconocido es:

Como el vector siempre se asignará en exceso, pagará el 50% del peor caso de sobrecarga de espacio para las implementaciones típicas (un solo vector de cadena, donde un objeto tiene, por ejemplo, 24 bytes (MSVC), dados los escasos 100.000 elementos, podría tener una sobrecarga de espacio de 2MB . Y se multiplicará por objetos más grandes con más cadenas u otros miembros más grandes.)
Cada vez que el vector tiene que reasignarse, tiene que copiar todos los objetos alrededor, y eso no es barato si tiene algo complejo. Obviamente, la semántica de movimiento ayudará, pero si los objetos son grandes, la copia repetida puede seguir siendo relevante. No importa si el tiempo promedio de inserción amortizado (al final) es teóricamente constante, si copia todos los objetos varias veces durante la construcción del vector. Puede notar este golpe de rendimiento.
Los objetos se agrandan realmente rápido: una estructura de solo dos cadenas std :: ya vacías tiene 48 bytes no movibles en MSVC.

Esto no es para bash std :: vector, todavía lo uso por defecto, ¡pero sé qué esperar de sus estructuras de datos!

Utilice una lista cuando la semántica de invalidación y las características de rendimiento coincidan con sus requisitos.

La lista puede insertar / borrar / empalmar en cualquier lugar en O (1), y esto no invalida ningún iterador. El vector es O (n) para insertar / borrar excepto al final, e incluso entonces solo para insertar si tamaño <capacidad; el vector no puede empalmar El rendimiento es incluso más sutil que esto, con la localidad de almacenamiento en caché mencionada en otra respuesta, por ejemplo.

Utiliza std :: list cuando necesita modificar frecuentemente la secuencia en otros lugares que no sean el frente o el reverso. La sobrecarga de tales operaciones es grande en std :: vector en comparación std :: list.

std::list es mi preferido casi exclusivamente para una propiedad que el vector no comparte, y eso es saber que mis punteros en una list siempre serán válidos. Debido a esto, puedo usar esto para contener todas las instancias de cualquier activo que necesite en una sola área, al mismo tiempo que presta referencias a otros objetos para usar. El mejor ejemplo que podría pensar sería en un cargador de imágenes que solo mantiene una copia de píxeles en la memoria, mientras presta prestados punteros a múltiples entidades para que todos puedan aprovecharlos.

Todo el vector tiene es el tiempo de acceso O (1). Si bien eso suena como un gran activo, en la práctica rara vez he necesitado acceder a elementos en una estructura de datos fuera de "primero" a "último"