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 |
[modifica] 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