vector vs inserción deque en medio

Question

sé que deque es más eficiente que el vector cuando inserciones están en el frente o al final del vector y es mejor si tenemos que hacer la aritmética de punteros. ¿Pero cuál usar cuando tenemos que realizar inserciones en el medio? y por qué.?

Answer 1

Se podría pensar que un deque tendría la ventaja, porque almacena los datos divididos en bloques. Sin embargo, implementar operator[] en tiempo constante requiere que todos esos bloques tengan el mismo tamaño. Insertar o eliminar un elemento en el medio todavía requiere desplazar todos los valores en un lado u otro, al igual que vector. Dado que el vector es más simple y tiene una mejor ubicación para el almacenamiento en caché, debería salir adelante.

Answer 2

Deque todavía sería más eficiente, ya que no tiene que mover la mitad de la matriz cada vez que inserta un elemento.

Por supuesto, esto solo importará si considera un gran número de elementos, e incluso si es recomendable ejecutar un punto de referencia y ver cuál funciona mejor en su caso particular. Recuerde que premature optimization is the root of all evil.

Answer 3

std::dequepodría realizar mejor para recipientes grandes, ya que se implementa típicamente como una secuencia enlazada de bloques de datos contiguos, en oposición al bloque único usado en un std::vector. Por lo tanto, una inserción en el medio daría como resultado que se copiarían menos datos de un lugar a otro, y potencialmente menores reasignaciones.

Por supuesto, ya sea que importe o no, depende del tamaño de los contenedores y del costo de copiar los elementos almacenados. Con la semántica del movimiento de C++ 11, el costo de este último es menos importante. Pero al final, la única forma de saber es perfilar con una aplicación realista.

Answer 4

Criterios de selección con la biblioteca contenedores estándar es, se selecciona un contenedor dependiendo de:

1. tipo de datos que desea almacenar &
2. El tipo de operación que desea realizar en los datos.

Si desea realizar una gran cantidad de inserciones en el medio, es mucho mejor que utilice un std::list.

Si la elección es sólo entre un std::deque y std::vector entonces hay una serie de factores a tener en cuenta:

• Por lo general, hay una más indirecta en caso de doble cola para acceder a los elementos, por lo que el elemento acceso y el movimiento iterativo de deques suele ser un poco más lento.
• En sistemas que tienen limitaciones de tamaño para bloques de memoria, un deque puede contener más elementos porque usa más de un bloque de memoria. Por lo tanto, max_size() podría ser más grande para deques.
• Deques no proporcionan soporte para controlar la capacidad y el momento de la reasignación. En en particular, 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. Sin embargo, la reasignación puede funcionar mejor que para los vectores, porque según su estructura interna típica , los deques no tienen que copiar todos los elementos en la reasignación.
• bloques de memoria podría obtener liberados cuando ya no se utilizan, por lo que el tamaño de la memoria de un deque podría reducir el tamaño (esto no es una condición impuesta por la norma, pero la mayoría de las implementaciones de hacer)