¿Cuál es la diferencia entre los contenedores STL deque y list?

Question

¿Cuál es la diferencia entre los dos? Quiero decir que los métodos son todos iguales. Entonces, para un usuario, funcionan de manera idéntica.

¿Es eso correcto?

Answer 1

Del (fechado pero aún muy útil) SGI STL resumen de deque :

  

Una deque es muy parecida a un vector: como vector, es una secuencia que admite acceso aleatorio a elementos, inserción y eliminación de elementos en tiempo constante al final de la secuencia, e inserción y eliminación de elementos en tiempo lineal. medio.

     

La forma principal en que difiere deque de vector es que deque también admite la inserción y eliminación de elementos en el tiempo constante al comienzo de la secuencia. Además, deque no tiene ninguna función miembro análoga a la capacidad del vector () y la reserva (), y no proporciona ninguna de las garantías de validez de iterador asociadas con esas funciones miembro.

Aquí está el resumen en list del mismo sitio:

  

Una lista es una lista doblemente vinculada. Es decir, es una secuencia que admite el desplazamiento hacia adelante y hacia atrás, y la inserción y eliminación de tiempo constante (amortizado) de elementos al principio o al final, o en el medio. Las listas tienen la propiedad importante de que la inserción y el empalme no invalidan los iteradores para enumerar elementos, y que incluso la eliminación invalida solo los iteradores que apuntan a los elementos que se eliminan. El orden de los iteradores puede cambiarse (es decir, list :: iterator podría tener un predecesor o sucesor diferente después de una operación de lista que antes), pero los iteradores en sí no serán invalidados ni obligados a señalar elementos diferentes a menos que esa invalidación o la mutación es explícita.

En resumen, los contenedores pueden tener rutinas compartidas, pero las garantías de tiempo para esas rutinas difieren de un contenedor a otro . Esto es muy importante cuando se considera cuál de estos contenedores usar para una tarea: tener en cuenta cómo el contenedor se usará con más frecuencia (por ejemplo, más para buscar que para insertar / eliminar) es muy útil en dirigirlo al contenedor correcto.

Answer 2

Permítanme enumerar las diferencias:

• Deque gestiona sus elementos con un matriz dinámica , proporciona aleatorio acceder , y tiene casi lo mismo interfaz como un vector.
• List gestiona sus elementos como lista doblemente vinculada y no proporcionar acceso aleatorio .

---

• Deque proporciona inserciones y eliminaciones rápidas en tanto el final como el principio. Insertar y eliminar elementos en el medio es relativamente lento porque todos los elementos hasta cualquiera de los dos los extremos se pueden mover para hacer espacio o para llenar un vacío.
• En Lista , la inserción y eliminación de elementos es rápida en cada posición, incluidos ambos extremos.

---

• Deque : cualquier inserción o eliminación de elementos que no sea al principio o al final invalida todos los punteros, referencias, e iteradores que se refieren a elementos del deque.
• Lista : la inserción y eliminación de elementos no invalidar punteros, referencias, e iteradores a otros elementos.

---

Complejidad

             Insert/erase at the beginning       in middle        at the end

Deque:       Amortized constant                  Linear           Amortized constant
List:        Constant                            Constant         Constant

Answer 3

std :: list es básicamente un lista doblemente vinculada.

std :: deque , en Por otro lado, se implementa más como std :: vector . Tiene un tiempo de acceso constante por índice, así como inserción y eliminación al principio y al final, lo que proporciona características de rendimiento dramáticamente diferentes a las de una lista.

Answer 4

No. Un deque solo admite la inserción y eliminación de O (1) en la parte frontal y posterior. Puede, por ejemplo, implementarse en un vector con envoltura. Dado que también garantiza el acceso aleatorio O (1), puede estar seguro de que no está utilizando (solo) una lista doblemente vinculada.

Answer 5

Otra garantía importante es la forma en que cada contenedor diferente almacena sus datos en la memoria:

• Un vector es un único bloque de memoria contiguo.
• Una deque es un conjunto de bloques de memoria vinculados, donde se almacena más de un elemento en cada bloque de memoria.
• Una lista es un conjunto de elementos dispersos en la memoria, es decir: solo se almacena un elemento por memoria " bloque " ;.

Tenga en cuenta que la deque fue diseñada para intentar equilibrar las ventajas de ambos vectores y listas sin sus respectivos inconvenientes. Es un contenedor especialmente interesante en plataformas con memoria limitada, por ejemplo, microcontroladores.

La estrategia de almacenamiento de memoria a menudo se pasa por alto, sin embargo, con frecuencia es una de las razones más importantes para seleccionar el contenedor más adecuado para una determinada aplicación.

Answer 6

Las diferencias de rendimiento han sido bien explicadas por otros. Solo quería agregar que interfaces similares o incluso idénticas son comunes en la programación orientada a objetos, parte de la metodología general de escribir software orientado a objetos. DE NINGUNA MANERA debe suponer que dos clases funcionan de la misma manera simplemente porque implementan la misma interfaz, como tampoco debe suponer que un caballo funciona como un perro porque ambos implementan attack () y make_noise ().