¿Por qué preferiría usar vector para deque

86

Ya que

  1. ambos son contenedores de memoria contiguos;
  2. En cuanto a las características, deque tiene casi todo lo que tiene el vector, pero más, ya que es más eficiente insertarlo en el frente.

¿Por qué alguien preferiría std::vectorhacerlo std::deque?

León
fuente
2
La implementación de Visual C ++ de std::dequetiene un tamaño de bloque máximo muy pequeño (~ 16 bytes, si recuerdo correctamente; tal vez 32) y, como tal, no funciona muy bien para aplicaciones realistas. A deque<T>donde sizeof(T) > 8(o 16? Es un número pequeño) tiene aproximadamente las mismas características de rendimiento que a vector<T*>, donde cada elemento se asigna dinámicamente. Otras implementaciones tienen diferentes tamaños de bloque máximos, por lo que escribir código que tenga relativamente las mismas características de rendimiento en diferentes plataformas es difícil deque.
James McNellis
12
Deque no es un contenedor de memoria continua.
Mohamed El-Nakib
@ravil No, ese es el duplicado, apuntando a esta pregunta.
1
Es difícil de creer que una pregunta con un error fáctico flagrante sin resolver tenía un saldo de 34 votos
undercore_d
2
@underscore_d por eso es una pregunta. Historia diferente si fuera una respuesta;)
Assimilater

Respuestas:

115

Los elementos de a nodeque son contiguos en la memoria; los elementos están garantizados. Entonces, si necesita interactuar con una biblioteca C simple que necesita matrices contiguas, o si le importa (mucho) la localidad espacial, entonces puede preferir . Además, dado que hay algo de contabilidad adicional, es probable que otras operaciones sean (ligeramente) más caras que sus operaciones equivalentes . Por otro lado, el uso de muchas o grandes instancias de puede provocar una fragmentación innecesaria del montón (ralentizar las llamadas a ).vectorvectorvectorvectornew

Además, como se señaló en otra parte de StackOverflow , hay más buena discusión aquí: http://www.gotw.ca/gotw/054.htm .

phooji
fuente
3
Parece que el enlace a "otro lugar" ahora está muerto (¿debido a la moderación?).
esilk
37

Para conocer la diferencia hay que saber cómo dequese implementa en general. La memoria se asigna en bloques de igual tamaño y están encadenados (como una matriz o posiblemente un vector).

Entonces, para encontrar el enésimo elemento, busque el bloque apropiado y luego acceda al elemento dentro de él. Este es un tiempo constante, porque siempre son exactamente 2 búsquedas, pero aún es más que el vector.

vectortambién funciona bien con las API que desean un búfer contiguo porque son API de C o son más versátiles para poder tomar un puntero y una longitud. (Por lo tanto, puede tener un vector debajo o una matriz regular y llamar a la API desde su bloque de memoria).

Donde dequetiene sus mayores ventajas son:

  1. Al aumentar o reducir la colección desde cualquier extremo
  2. Cuando se trata de colecciones de gran tamaño.
  3. Cuando se trata de bools y realmente desea bools en lugar de bitset.

El segundo de estos es menos conocido, pero para tamaños de colección muy grandes:

  1. El costo de la reasignación es grande
  2. La sobrecarga de tener que encontrar un bloque de memoria contiguo es restrictiva, por lo que puede quedarse sin memoria más rápido.

Cuando estaba tratando con colecciones grandes en el pasado y me mudé de un modelo contiguo a un modelo de bloque, pudimos almacenar una colección aproximadamente 5 veces más grande antes de que nos quedáramos sin memoria en un sistema de 32 bits. Esto se debe en parte a que, al reasignar, en realidad necesitaba almacenar el bloque antiguo y el nuevo antes de copiar los elementos.

Habiendo dicho todo esto, puede tener problemas con los std::dequesistemas que utilizan una asignación de memoria "optimista". Si bien sus intentos de solicitar un tamaño de búfer grande para una reasignación de a vectorprobablemente serán rechazados en algún momento con a bad_alloc, es probable que la naturaleza optimista del asignador siempre otorgue la solicitud del búfer más pequeño solicitado por a dequey que probablemente cause el sistema operativo para matar un proceso para intentar adquirir algo de memoria. Cualquiera que elija puede que no sea demasiado agradable.

Las soluciones en tal caso son establecer indicadores a nivel del sistema para anular la asignación optimista (no siempre es factible) o administrar la memoria de manera algo más manual, por ejemplo, usando su propio asignador que verifica el uso de memoria o similar. Obviamente no es ideal. (Lo que puede responder a su pregunta de preferir el vector ...)

CashCow
fuente
29

Implementé tanto vector como deque varias veces. deque es mucho más complicado desde el punto de vista de la implementación. Esta complicación se traduce en más código y código más complejo. Por lo tanto, normalmente verá un tamaño de código cuando elija deque sobre vector. También puede experimentar un pequeño golpe de velocidad si su código usa solo las cosas en las que el vector sobresale (es decir, push_back).

Si necesita una cola de dos extremos, deque es el claro ganador. Pero si está haciendo la mayoría de sus inserciones y borra en la parte posterior, vector será el claro ganador. Cuando no esté seguro, declare su contenedor con un typedef (para que sea fácil cambiar de un lado a otro) y mida.

Howard Hinnant
fuente
3
Pregunta: ¿ha considerado el comité agregar un híbrido de los dos (digamos, un "mazo") a C ++? (es decir, de dos extremos vector). He escrito una implementación vinculada a continuación en mi respuesta . Puede ser tan rápido como un vectorpero mucho más aplicable (por ejemplo, al hacer una cola rápida).
user541686
5

std::dequeno tiene memoria continua garantizada y, a menudo, es algo más lento para el acceso indexado. Una deque se implementa típicamente como una "lista de vectores".

Erik
fuente
14
No creo que una "lista de vectores" sea correcta: tenía entendido que la mayoría de las implementaciones eran un "vector de punteros a matrices", aunque depende de su definición de "lista" (leí "lista" como "lista vinculada , "que no cumpliría con los requisitos de complejidad).
James McNellis
2

Según http://www.cplusplus.com/reference/stl/deque/ , "a diferencia de los vectores, no se garantiza que los deques tengan todos sus elementos en ubicaciones de almacenamiento contiguas, eliminando así la posibilidad de un acceso seguro mediante aritmética de punteros".

Los Deques son un poco más complicados, en parte porque no necesariamente tienen un diseño de memoria contiguo. Si necesita esa función, no debe usar un deque.

(Anteriormente, mi respuesta planteaba una falta de estandarización (de la misma fuente que arriba, "las bibliotecas específicas pueden implementar deques de diferentes maneras"), pero eso en realidad se aplica a casi cualquier tipo de datos de biblioteca estándar).

patrickvacek
fuente
5
std::dequeno está menos estandarizado que std::vector. No creo que los requisitos de complejidad de std::dequese puedan cumplir con el almacenamiento contiguo.
Jerry Coffin
1
Quizás mi redacción fue pobre: ​​aunque es cierto que la estandarización no es completa, según tengo entendido, los vectores están estandarizados para ser una secuencia conitugoa y los deques no. Ese parece ser el factor decisivo.
patrickvacek
1
@JerryCoffin: ¿Qué requisitos de complejidad dequeno se pueden cumplir con el almacenamiento contiguo?
user541686
1
@Mehrdad: Para ser honesto, no recuerdo lo que tenía en mente. No he mirado esa parte del estándar lo suficientemente recientemente como para sentirme cómodo al afirmar categóricamente que mi comentario anterior estaba equivocado, pero mirándolo ahora mismo, tampoco puedo pensar en cómo sería correcto.
Jerry Coffin
3
@JerryCoffin: Los requisitos de complejidad son en realidad triviales: podría asignar una matriz grande y comenzar a empujar su secuencia desde el medio hacia afuera (supongo que esto es lo que hace la implementación de Mehrdad), luego reasignar cuando llegue al final. El problema con este enfoque es que no satisface uno de los requisitos de deque, a saber, que la inserción en los extremos no invalidará la referencia a los elementos existentes. Este requisito implica memoria discontinua.
Yakov Galka
0

Un deque es un contenedor de secuencia que permite el acceso aleatorio a sus elementos, pero no se garantiza que tenga un almacenamiento contiguo.

Sean
fuente
0

Me parece buena idea hacer una prueba de rendimiento de cada caso. Y tome una decisión confiando en estas pruebas.

Preferiría std::dequeque std::vectoren la mayoría de los casos.

George Gaál
fuente
1
La pregunta, si se puede extraer alguno de entre los errores fácticos y las palabras faltantes, era por qué alguien preferiría vector. Podemos inferir que por qué no es un corolario. Decir que prefiere deque, por razones desconocidas, de pruebas no especificadas, no es una respuesta.
underscore_d
0

Por un lado, el vector es con bastante frecuencia simplemente más rápido que deque. Si en realidad no necesita todas las características de deque, use un vector.

Por otra parte, a veces se hace rasgos necesidad vector que no le da, en cuyo caso se debe utilizar un deque. Por ejemplo, desafío a cualquiera a que intente reescribir este código , sin usar una deque y sin alterar enormemente el algoritmo.

BenGoldberg
fuente
En realidad, en la misma serie de operaciones push_backy pop_back, deque<int>siempre es al menos un 20% más rápido que vector<int>en mis pruebas (gcc con O3). Supongo que por eso dequees la opción estándar para cosas como std::stack...
igel
-1

Tenga en cuenta que la memoria vectorial se reasigna a medida que crece la matriz. Si tiene punteros a elementos vectoriales, dejarán de ser válidos.

Además, si borra un elemento, los iteradores se vuelven inválidos (pero no "para (auto ...)").

Editar: cambió 'deque' a 'vector'

Pierre
fuente
-1: Insertar y borrar al principio o al final NO invalida las referencias y punteros a otros elementos. (Aunque insertar y borrar en el medio sí)
Sjoerd
@Sjoerd lo cambié a 'vector'.
Pierre