La STL (Standard Template Library) de C++ ofrece dos contenedores muy similares: el famoso std::vector y la poco usada std::deque (Double Ended Queue = cola doblemente terminada). Ambos contenedores ofrecen acceso aleatorio a un bloque de memoria continuo. Es decir, son arrays.

¿Qué es la diferencia? El concepto de un vector es un array con un inicio fijo y un fin variable. Una deque es un array con tanto el inicio como el fin variable. Por eso, el contenedor deque es útil cuando quiero tener un acceso aleatorio como en un vector, pero poder insertar delante el índice cero o eliminar elementos al inicio.

Tanto el vector como la deque son contenedores de acceso aleatorio. Sin embargo, internamente tienen una diferencia importante: un vector garantiza que los elementos están guardados en una memoria continua. Es decir, puedo usar un puntero como iterador. De hecho muchas implementaciones usan punteros como iteradores sobre vectores. La deque a contrario no garantiza guardar los elementos en una memoria contigua. Se puede implementar como un vector con un puntero variable al primer elemento del array. Pero el estándar no lo impone. Se puede implementar también, por ejemplo, como dos vectores – uno creciendo hacia indices más altos, el otro creciendo hacia “abajo” para insertar elementos al inicio del contenedor.

Otra diferencia está en los elementos que se reservan de más. Ambos contenedores tienen el método size() que devuelve el número de elementos válidos en el contenedor, pero sólo vector tiene el método capacity(), que devuelve el número de elementos reservados en la memoria.

Por ejemplo, si el método size() de un vector devuelve cinco, entonces mi array aparenta tener el tamaño cinco. Si el método capacity() de la misma instancia de vector devuelve ocho, entonces habrá memoria reservada para ocho elementos. Si añado un sexto elemento al final del vector, la operación es muy rápida, ya que no hace falta reservar más memoria para el un nuevo objeto: el elemento ya existe físicamente y sólo hace falta construirlo con los datos para el nuevo elemento.

Esta reserva de memoria ayuda a mejorar la velocidad cuando añado elementos a un contenedor. Si no fuera así, el contenedor debería reservar memoria para n+1 elementos, copiar los n que ya tiene y escribir el último al final cada vez cuando añado un elemento nuevo. Por eso los contenedores de la STL pueden reservar memoria para más elementos que corresponde a su tamaño.

Se puede forzar la capacidad mínima de un vector con el método reserve(). El contenedor deque no tiene esta característica. (La deque debería tener un método reserve_front() y reserve_back()para esto, pero esto la STL no lo ofrece.)

Por lo tanto, si quiero añadir a un array ya existente un número de elementos conocidos a priori con el método push_back(), es ventajoso usar un vector. No obstante, si ya conozco el número de elementos a la hora de creación del contenedor no tengo esta limitación. Tanto el vector como la deque tienen un constructor que especifica el número de elementos iniciales. Y lógicamente puedo llamar al método resize() en cada momento para especificar el número de elementos en ambos contenedores.

Compara

std::vector vec;
vec.reserve(numero_de_elementos);
for (int i = 0; i < numero_de_elementos; ++i)
{
    vec.push_back(nuevo_elemento);
}

con

std::vector vec2;
vec2.resize(numero_de_elementos);
for (int i = 0; i < numero_de_elementos; ++i)
{
    vec2[i] = nuevo_elemento;
}

La primera versión con reserve() es más flexible cuando quiero sustituir el vector por una lista. Aún así la mayoría de los programadores usaría la segunda forma con resize() que funciona tanto para la deque como el vector.

La limitación de un vector se manifiesta cuando quiero eliminar i elementos del principio. Como su inicio es fijo y el elemento con el índice i será el nuevo con el índice 0, debo copiar todos los elementos de i a n para que ocupen el rango de índices 0 a n-i. El contenedor deque, en cambio, no necesita borrar los elementos. Simplemente sube un puntero al primer elemento en i posiciones y invalida así los elementos a borrar. Estos elementos se quedan en la memoria para ser reciclados si se añadieran nuevas elementos al principio.

La deque requiere un poco más de gestión por tener el inicio variable, pero teniendo en cuenta que la mayor parte del trabajo de un contenedor es trabajar con los elementos y no con el contenedor mismo, la diferencia es mínima. Por lo tanto, conviene optar por una deque siempre y cuando no esté asegurado que no se quieren eliminar elementos del inicio del array.

Un vector es la elección si quiero reservar un número de elementos conocido después de la creación del contenedor, ya que puedo aprovecharme del método reserve() que la deque no tiene. Sin embargo, la reserva previa de elementos se puede sustituir muchas veces por una construcción con resize().

Pero tampoco hay muchas ocasiones en que necesito añadir elementos al principio de un array. Por lo tanto no extraña que la deque es menos conocida que el vector: simplemente se necesita poco. Pero conviene saber de su existencia.