std::deque

template<
    class T,
    class Allocator = std::allocator<T>
> class deque;

namespace pmr {
    template <class T>
    using deque = std::deque<T, std::pmr::polymorphic_allocator<T>>;
}

std::deque (cola doblemente terminada) es un contenedor de secuencia indexada que permite una rpida insercin y eliminacin tanto al principio como al final. Adems, la insercin y eliminacin 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 tpicas usan una secuencia de arrays de tamao 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 comparacin con el acceso indexado del vector, que realiza solo una.

El almacenamiento de un deque se expande y contrae automticamente segn sea necesario. La expansin de una deque es ms barata que la expansin de un std::vector porque no implica copiar los elementos existentes a una nueva ubicacin de memoria. Por otro lado, las colas doblemente terminadas suelen tener un gran coste de memoria mnimo; una cola doblemente terminada que contiene solo un elemento tiene que asignar su array interno complet (por ejemplo, 8 veces el tamao del objeto en libstdc++ de 64 bits; 16 veces el tamao 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).
• Insercin o eliminacin de elementos al final o al comienzo - constante O(1).
• Insercin o eliminacin de elementos - lineal O(n).

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

Parmetros de plantilla

Invalidacin de iteradores

Todava hay algunas inexactitudes en esta seccin, consulta las pginas de funciones miembro individuales para obtener ms detalles.

Notas de invalidacin

• 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 tamao ms pequeo no invalida ninguna referencia a los elementos no borrados.
• Una llamada a resize con un tamao ms grande no invalida ninguna referencia a los elementos de la cola doblemente terminada.

Tipos miembro

Funciones miembro

Funciones no miembro

Guas de deduccin(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

Vase tambin