usar - map c++

¿Cuál es la diferencia entre deque y lista de contenedores STL?

Question

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

¿¿Es eso correcto??

Answer 1

Déjame enumerar las diferencias:

• Deque administra sus elementos con una matriz dinámica , proporciona acceso aleatorio y tiene casi la misma interfaz que un vector.
• List administra sus elementos como una lista doblemente enlazada y no proporciona acceso aleatorio .

• Deque proporciona inserciones y eliminaciones rápidas tanto al final como al principio. Insertar y eliminar elementos en el medio es relativamente lento porque todos los elementos hasta cualquiera de los dos extremos pueden moverse para hacer espacio o para llenar un espacio.
• En la Lista , insertar y quitar elementos es rápido en cada posición, incluidos los dos extremos.

• Deque : cualquier inserción o eliminación de elementos que no sean al principio o al final invalida todos los punteros, referencias e iteradores que hacen referencia a los elementos del deque.
• Lista : insertar y eliminar elementos no invalida los punteros, las referencias y los 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 2

Las diferencias de rendimiento han sido bien explicadas por otros. Solo quería agregar que las 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 asuma 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 ambas implementan attack () y make_noise ().

Answer 3

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 envolvente. Ya que también garantiza O (1) acceso aleatorio, puede estar seguro de que no está utilizando (solo) una lista doblemente enlazada.

Answer 4

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

• Un vector es un bloque de memoria contiguo único.
• Un 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 "bloque" de memoria.

Tenga en cuenta que el deque fue diseñado para tratar de equilibrar las ventajas de ambos, vector y lista, sin sus respectivos inconvenientes. Es un contenedor especialmente interesante en plataformas de memoria limitada, por ejemplo, microcontroladores.

La estrategia de almacenamiento en 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 aplicación determinada.

Answer 5

list es básicamente una lista doblemente enlazada.

deque , por otro lado, se implementa más como std::vector . Tiene un tiempo de acceso constante por índice, así como la 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 6

Desde el resumen de deque SGI STL (con fecha, pero muy útil):

Un deque es muy parecido a un vector: como vector, es una secuencia que admite el acceso aleatorio a elementos, la inserción y eliminación constante de elementos al final de la secuencia, y la inserción y eliminación de elementos lineales en el medio.

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

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

Una lista es una lista doblemente enlazada. Es decir, es una secuencia que admite el desplazamiento tanto hacia delante como hacia atrás, y la inserción y eliminación constante (amortizada) 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 los elementos, y que incluso la eliminación invalida solo los iteradores que apuntan a los elementos que se eliminan. El orden de los iteradores se puede cambiar (es decir, list :: iterator puede tener un predecesor o sucesor diferente después de una operación de lista de la que tenía antes), pero los iteradores en sí mismos no se invalidarán ni se harán que apunten a elementos diferentes a menos que la 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 varían de un contenedor a otro . Esto es muy importante cuando se considera cuál de estos contenedores se debe usar para una tarea: tener en cuenta cómo se usará con mayor frecuencia el contenedor (por ejemplo, más para buscar que para insertar / eliminar) le ayuda mucho a dirigirlo al contenedor correcto .