¿Por qué preferiría usar vector para deque

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?

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 .

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 ...)

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.

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".

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).

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

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.

No preferiría el vector a la deque según los resultados de estas pruebas (con la fuente).

Por supuesto, debe probar en su aplicación / entorno, pero en resumen:

• push_back es básicamente el mismo para todos
• insertar, borrar en deque son mucho más rápidos que la lista y marginalmente más rápidos que el vector

Algunas reflexiones más y una nota para considerar circular_buffer.

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.

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'