CKTIS / C++
std::deque: cola de dos extremos con acceso aleatorio
std::deque ofrece operaciones rápidas en ambos extremos y acceso aleatorio, pero no garantiza un único búfer contiguo para todos sus elementos.
Versión: C++23
Sintaxis
template<class T, class Allocator = std::allocator<T>>
class deque;
void push_front(const T& value);
void push_back(const T& value);
void pop_front();
void pop_back();std::deque<T>, de <deque>, es un contenedor de secuencia con iteradores random access. Insertar o borrar un elemento en cualquier extremo cuesta tiempo constante; hacerlo en el centro es lineal. A diferencia de std::vector, los elementos no tienen que ser contiguos, por lo que &d[0] no es el inicio de un array que contenga toda la deque.
Insertar en el centro invalida todos los iteradores y referencias. Insertar en un extremo invalida todos los iteradores, pero conserva referencias a elementos existentes. Borrar el último elemento invalida el iterador past-the-end y los accesos a elementos borrados; borrar el primero pero no el último afecta solo a los borrados, mientras que un borrado central lo invalida todo. Por tanto, pop_front() en una deque de un elemento también borra el último elemento e invalida end().
operator[] no comprueba el índice; at() lanza std::out_of_range. front(), back() y pop_* exigen un contenedor no vacío. Trabajar con frecuencia en ambos extremos es el uso natural; si se requiere almacenamiento contiguo o iteradores estables al añadir, debe reconsiderarse el contenedor.
Ejemplos
#include <deque>
#include <iostream>
int main() {
std::deque<int> values;
values.push_back(2);
values.push_back(3);
values.push_front(1);
values.pop_back();
std::cout << values.size() << ' ' << values.front() << ' ' << values.back() << '\n';
}
Resultado
2 1 2
std::deque → 2 1 2