CKTIS / C++
std::deque: coda a doppia estremità con accesso casuale
std::deque offre operazioni rapide a entrambe le estremità e accesso casuale, ma non garantisce un unico buffer contiguo per tutti gli elementi.
Versione: C++23
Sintassi
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> di <deque> è un contenitore sequenziale con iteratori random access. Inserire o eliminare un singolo elemento a una delle estremità costa tempo costante, mentre le operazioni centrali sono lineari. A differenza di std::vector, gli elementi non devono essere contigui: &d[0] non è l’inizio di un array che contiene l’intera deque.
Un inserimento centrale invalida tutti gli iteratori e riferimenti. Inserire a un’estremità invalida tutti gli iteratori ma conserva i riferimenti agli elementi esistenti. Eliminare l’ultimo elemento invalida l’iteratore past-the-end e gli accessi agli elementi rimossi; eliminare il primo ma non l’ultimo riguarda solo i rimossi, mentre un’eliminazione centrale invalida tutto. Pertanto pop_front() su una deque di un elemento elimina anche l’ultimo elemento e invalida end().
operator[] non controlla l’indice, mentre at() lancia std::out_of_range. front(), back() e pop_* richiedono un contenitore non vuoto. Operare spesso su entrambe le estremità è l’uso naturale; se servono memoria contigua o iteratori stabili dopo un’aggiunta, va rivalutato il contenitore.
Esempi
#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';
}
Risultato
2 1 2
std::deque → 2 1 2