std:: deque

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

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

El almacenamiento de un deque se expande y contrae automáticamente según sea necesario. La expansión de un deque es más económica que la expansión de un std::vector porque no implica la copia de los elementos existentes a una nueva ubicación de memoria. Por otro lado, los deques típicamente tienen un alto costo mínimo de memoria; un deque que contiene solo un elemento debe asignar su arreglo interno completo (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 en deques es la siguiente:

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

std::deque cumple con los requisitos de Container , AllocatorAwareContainer , SequenceContainer y ReversibleContainer .

#include <deque>
#include <iostream>
int main()
{
    // Crear un deque que contenga enteros
    std::deque<int> d = {7, 5, 16, 8};
    // Agregar un entero al principio y al final del deque
    d.push_front(13);
    d.push_back(25);
    // Iterar e imprimir valores del deque
    for (int n : d)
        std::cout << n << ' ';
    std::cout << '\n';
}

13 7 5 16 8 25