Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

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

Fontes