std::deque (cola doblemente terminada) es un contenedor de secuencia indexada que permite una rápida inserción y eliminación tanto al principio como al final. Además, la inserción y eliminación en cualquier extremo de una cola doblemente terminada nunca invalida los punteros o referencias al resto de los elementos.

A diferencia de std::vector, los elementos de una cola doblemente terminada no se almacenan contiguamente: las implementaciones típicas usan una secuencia de arrays de tamaño fijo asignados individualmente, con contabilidad adicional, lo que significa que el acceso indexado a una cola doblemente terminada debe realizar dos desreferencias de puntero, en comparación con el acceso indexado del vector, que realiza solo una.

El almacenamiento de un deque se expande y contrae automáticamente según sea necesario. La expansión de una deque es más barata que la expansión de un std::vector porque no implica copiar los elementos existentes a una nueva ubicación de memoria. Por otro lado, las colas doblemente terminadas suelen tener un gran coste de memoria mínimo; una cola doblemente terminada que contiene solo un elemento tiene que asignar su array interno complet (por ejemplo, 8 veces el tamaño del objeto en libstdc++ de 64 bits; 16 veces el tamaño del objeto o 4096 bytes, lo que sea mayor, en libc++ de 64 bits).

La complejidad (eficiencia) de las operaciones comunes sobre colas doblemente terminadas es la siguiente:

• Acceso aleatorio - constante O(1).
• Inserción o eliminación de elementos al final o al comienzo - constante O(1).
• Inserción o eliminación de elementos - lineal O(n).

std::deque cumple con los requerimientos de Contenedor, ContenedorConscienteDeAsignador, ContenedorDeSecuencia y ContenedorReversible.

Parámetros de plantilla

Todavía hay algunas inexactitudes en esta sección, consulta las páginas de funciones miembro individuales para obtener más detalles.

Notas de invalidación

• Al insertar en cualquier extremidad de la cola doblemente terminada, las referencias no se invalidan por insert y emplace.
• push_front, push_back, emplace_front y emplace_back no invalidan ninguna referencia a los elementos de la cola doblemente terminada.
• Al borrar en cualquier extremidad de la cola doblemente terminada, las referencias a los elementos no borrados no se invalidan por erase, pop_front y pop_back.
• Una llamada a resize con un tamaño más pequeño no invalida ninguna referencia a los elementos no borrados.
• Una llamada a resize con un tamaño más grande no invalida ninguna referencia a los elementos de la cola doblemente terminada.

Tipos miembro

Funciones miembro

Funciones no miembro

Guías de deducción(desde C++17)

Ejemplo

#include <iostream>
#include <deque>

int main()
{
    // Crear cola doblemente terminada que contiene enteros
    std::deque<int> d = {7, 5, 16, 8};

    // Agregar un entero al principio y al final de la cola
    d.push_front(13);
    d.push_back(25);

    // Iterar e imprimir los valores en la cola
    for(int n : d) {
        std::cout << n << '\n';
    }
}

13
7
5
16
8
25

Véase también