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 .

Parámetros de plantilla

Invalidación de iteradores

Notas de invalidación

• Al insertar en cualquiera de los extremos del deque, las referencias no se invalidan por insert y emplace .
• push_front , push_back , emplace_front y emplace_back no invalidan ninguna referencia a elementos del deque.
• Al eliminar en cualquiera de los extremos del deque, las referencias a elementos no eliminados no se invalidan por erase , pop_front y pop_back .
• Una llamada a resize con un tamaño menor no invalida ninguna referencia a elementos no eliminados.
• Una llamada a resize con un tamaño mayor no invalida ninguna referencia a elementos del deque.

Tipos de miembros

Funciones miembro

Funciones no miembro

Notas

Ejemplo

#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

Informes de defectos

Los siguientes informes de defectos que modifican el comportamiento se aplicaron retroactivamente a los estándares de C++ publicados anteriormente.

Véase también