Contenedores STL: diferencia entre vector, lista y deque

Question

¿Debo usar deque en lugar de vector si quisiera insertar elementos también en el inicio del contenedor? ¿Cuándo debería usar la lista y de qué sirve?

Answer 1

Utilice deque si necesita una inserción/extracción eficiente al principio y al final de la secuencia y acceso aleatorio; use list si necesita una inserción eficiente en cualquier lugar, sacrificando el acceso aleatorio. Los iteradores y las referencias a los elementos list son muy estables en casi cualquier mutación del contenedor, mientras que deque tiene normas de invalidación de referencia e iterador muy peculiares (por lo tanto, pruébelos cuidadosamente).

También, list es un contenedor basado en nodos, mientras que deque utiliza fragmentos de memoria contigua, por lo que la localidad de memoria puede tener efectos de rendimiento que no se pueden capturar mediante estimaciones de complejidad asintótica.

deque puede servir como un reemplazo para vector en casi todas partes y probablemente debería haber sido considerado el contenedor "predeterminado" en C++ (debido a sus requisitos de memoria más flexibles); la única razón para preferir vector es cuando debe tener un diseño de memoria contigua garantizado de su secuencia.

Answer 2

deque y vector proporcionan acceso aleatorio, list proporciona solo accesos lineales. Entonces, si necesita poder hacer el contenedor [i], eso excluye list. Por otro lado, puede insertar y eliminar elementos en cualquier lugar en un list de manera eficiente, y las operaciones en el medio de vector y deque son lentas.

deque y vector son muy similares, y son básicamente intercambiables para la mayoría de los propósitos. Solo hay dos diferencias que vale la pena mencionar. Primero, vector solo puede agregar nuevos elementos de manera eficiente al final, mientras que deque puede agregar elementos en cada extremo de manera eficiente. Entonces, ¿por qué alguna vez usarías un vector? A diferencia de deque, vector garantiza que todos los elementos se almacenarán en ubicaciones de memoria contigua, lo que hace que la iteración a través de ellos sea más rápida en algunas situaciones.