C++ Deque: code a due estremi

Le deque (code a due estremi, pronunciate 'deck') sono simili ai vettori, ma permettono di fare inserimenti e cancellazioni veloci ad entrambe le estremità del container.

Le deque sono comunemente implementate come array allocati dinamicamente che possono essere estesi ad entrambe le estremità. Questo garantisce accesso a tempo costante, inserimenti e cancellazioni alle estremità a tempo costante ammortizzato e infine inserimenti e cancellazioni a posizioni interne alla coda a tempo lineare

Costruttori	creano deques e le popolano di dati
Operatori	confrontano, assegnano, e accedono elementi di una deque
assign	assigna elementi ad una deque
at	returna un elemento ad una specifica locazione
back	ritorna una reference all'ultimo elemento di una deque
begin	ritorna un iteratore che punta all'inzio di una deque
clear	rimuove tutti gli elementi di una deque
empty	ritorna true se la deque non ha elementi
end	ritorna un iteratore alla prima posizione dopo l'ultimo elemento della deque
erase	rimuove elementi della deque
front	ritorna una reference al primo elemento di una deque
insert	inserisce elementi nella deque
max_size	ritorna il massimo numero di elementi che la deque può contenere
pop_back	rimuove l'ultimo elemento di una deque
pop_front	rimuove il primo elemento di una deque
push_back	aggiunge un elemento alla fine della deque
push_front	aggiunge un elemento all'inzio della deque
rbegin	ritorna un reverse_iterator che punta alla fine della deque
rend	ritorna un reverse_iterator che punta all'inizio della deque
resize	cambia la dimensione della deque
size	ritorna il numero di item della deque
swap	scambia elementi della deque con quelli di un'altra istanza

Note

Il nome deque viene pronunciato "deck" e sta per "double-ended queue". Donald Knuth riferisce che il nome è stato coniato da E. J. Schweppe. vedi D. E. Knuth, The Art of Computer Programming. Volume 1: Fundamental Algorithms, second edition. Addison-Wesley, 1973. Sezione 2.2.1