vectors example c++ stl vector deque

example - stack c++



¿Por qué preferiría usar vector para deque (9)

Creo que es una buena idea hacer una prueba de rendimiento de cada caso. Y tome una decisión basándose en estas pruebas.

Preferiría std::deque que std::vector en la mayoría de los casos.

Ya que

  1. ambos son contenedores de memoria contiguos;
  2. En cuanto a la funcionalidad, 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::vector a std::deque ?

Implementé vector y 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 golpeado cuando elija deque sobre vector. También puede experimentar un pequeño golpe de velocidad si su código utiliza solo las cosas en las que sobresale el vector (es decir, push_back).

Si necesita una cola de doble final, deque es el claro ganador. Pero si está haciendo la mayoría de sus inserciones y las borra en la parte posterior, el 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.

Los elementos en una deque no son contiguos en la memoria; vector elementos del vector están garantizados para ser. Entonces, si necesita interactuar con una biblioteca simple de C que necesita arreglos contiguos, o si le importa (mucho) la localidad espacial, entonces podría preferir el vector . Además, dado que existe una contabilidad adicional, es probable que otras operaciones (un poco) sean más costosas que sus operaciones equivalentes de vector . Por otro lado, el uso de muchas / grandes instancias de vector puede llevar a una fragmentación de montón innecesaria (ralentizando las llamadas a new ).

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

Para saber la diferencia, uno debe saber cómo se implementa generalmente el deque . La memoria se asigna en bloques de igual tamaño, y se encadenan entre sí (como una matriz o posiblemente un vector).

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

vector también funciona bien con las API que desean un búfer contiguo porque son API C o son más versátiles al 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 deque tiene sus mayores ventajas son:

  1. Al crecer o reducir la colección de cualquiera de los extremos
  2. Cuando se trata de tamaños de colección muy grandes.
  3. Cuando se trata de bools y realmente quieres 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 contigua es restrictiva, por lo que puede agotar la memoria más rápido.

Cuando lidiaba con grandes colecciones en el pasado y pasaba de un modelo contiguo a un modelo de bloque, pudimos almacenar una colección aproximadamente 5 veces mayor antes de que se nos agotara la memoria en un sistema de 32 bits. Esto se debe en parte a que, al reasignar, realmente se necesitaba almacenar tanto el bloque viejo como el nuevo antes de copiar los elementos.

Habiendo dicho todo esto, puede tener problemas con std::deque en sistemas que usan asignación de memoria "optimista". Mientras que sus intentos de solicitar un tamaño de búfer grande para una reasignación de un vector probablemente serán rechazados en algún momento con un bad_alloc , es probable que la naturaleza optimista del asignador otorgue siempre la solicitud del búfer más pequeño solicitado por un deque y que sea es probable que cause que el sistema operativo mate un proceso para tratar de adquirir algo de memoria. Cualquiera que elija puede no ser muy agradable.

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

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

Por otro lado, a veces necesitas funciones que el vector no te da, en cuyo caso debes usar un deque. Por ejemplo, desafío a cualquiera a intentar reescribir este código , sin utilizar un deque, y sin alterar enormemente el algoritmo.

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 a través de aritmética de punteros".

Los Deques son un poco más complicados, en parte porque no necesariamente tienen un diseño de memoria contigua. Si necesita esa característica, no debe usar un deque.

(Anteriormente, mi respuesta planteó una falta de estandarización (de la misma fuente que la anterior, "deques pueden ser implementadas por bibliotecas específicas de diferentes maneras"), pero eso realmente 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.

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