CKTIS / C++
std::deque: fila de duas extremidades com acesso aleatório
std::deque oferece operações rápidas nas duas extremidades e acesso aleatório, mas não garante um único bloco contíguo para todos os elementos.
Versão: C++23
Sintaxe
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>, é um contentor sequencial com iteradores random access. Inserir ou apagar um elemento em qualquer extremidade custa tempo constante; operações no meio são lineares. Ao contrário de std::vector, os elementos não têm de ser contíguos, pelo que &d[0] não é o início de um array que contenha toda a deque.
Uma inserção no meio invalida todos os iteradores e referências. Inserir numa extremidade invalida todos os iteradores, mas preserva referências a elementos existentes. Apagar o último elemento invalida o iterador past-the-end e os acessos aos elementos apagados; apagar o primeiro, mas não o último, afeta apenas os apagados, enquanto uma remoção central invalida tudo. Assim, pop_front() numa deque com um elemento também apaga o último elemento e invalida end().
operator[] não verifica o índice; at() lança std::out_of_range. front(), back() e pop_* exigem um contentor não vazio. Trabalhar frequentemente nas duas extremidades é o uso natural; se for necessário armazenamento contíguo ou iteradores estáveis ao acrescentar, reconsidera o contentor.
Exemplos
#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