La libreria <deque> fornisce il contenitore std::deque
(Double-Ended QUEue), una struttura simile a vector ma ottimizzata
per le operazioni alle estremità.
Un deque permette:
- push_front e pop_front
- push_back e pop_back
- accesso casuale O(1)
- crescita dinamica sia davanti che dietro
📌 È il contenitore ideale quando devi lavorare sia all inizio che alla fine della sequenza.
1️⃣ Differenze tra deque e vector
| Caratteristica | vector | deque |
|---|---|---|
| push_front() | ❌ Lento / non disponibile | ✔️ Veloce |
| push_back() | ✔️ Veloce | ✔️ Veloce |
| Accesso casuale | ✔️ O(1) | ✔️ O(1) |
| Memoria | Contigua | Blocchi multipli |
| Ideale per | Acceso casuale | Code a doppia estremità |
2️⃣ Inclusione della libreria
#include <deque>
using namespace std;
3️⃣ Dichiarazione e inizializzazione
deque D = {1, 2, 3};
deque nomi = {"Anna", "Luca", "Marco"};
4️⃣ Metodi principali di std::deque
| Metodo | Descrizione |
|---|---|
push_back(x) | Aggiunge in fondo |
push_front(x) | Aggiunge all inizio |
pop_back() | Rimuove ultimo elemento |
pop_front() | Rimuove primo elemento |
at(i) | Accesso sicuro con controllo limiti |
operator[i] | Accesso diretto senza controllo |
front() | Primo elemento |
back() | Ultimo elemento |
insert() | Inserisce in una posizione |
erase() | Rimuove in una posizione |
clear() | Svuota il deque |
empty() | Verifica se è vuoto |
size() | Numero elementi |
5️⃣ Inserimento alle estremità
deque D;
D.push_back(3); // [3]
D.push_front(1); // [1, 3]
D.push_back(5); // [1, 3, 5]
6️⃣ Accesso agli elementi
cout << D[0]; // accesso diretto
cout << D.at(1); // accesso controllato
cout << D.front(); // primo elemento
cout << D.back(); // ultimo elemento
7️⃣ Inserimento e rimozione con iteratori
auto it = D.begin();
advance(it, 1);
D.insert(it, 99); // inserisce in posizione 1
D.erase(it); // rimuove in posizione 1
8️⃣ Uso con algorithm
sort(D.begin(), D.end());
reverse(D.begin(), D.end());
9️⃣ Esempio completo
deque D = {7,3,9,1};
D.push_front(10);
D.push_back(5);
sort(D.begin(), D.end());
for(int x : D)
cout << x << " ";
LABORATORIO
Uso del Contenitore deque
In questo laboratorio eserciterai le principali funzioni di
std::deque, lavorando con inserimenti, cancellazioni,
ordinamenti e operazioni alle estremità.
Strumenti:
- Libreria
<deque> - Metodi push_front, push_back, insert, erase
- Libreria
<algorithm>
1 Creazione deque
Crea un deque di 10 numeri casuali.
deque D;
for(int i = 0; i < 10; i++)
D.push_back(1 + rand() % 100);
2 Inserimenti alle estremità
Inserisci 999 all inizio e 111 alla fine.
D.push_front(999);
D.push_back(111);
3 Ordinamento e inversione
sort(D.begin(), D.end());
reverse(D.begin(), D.end());
4 Inserimento in posizione
Inserisci 500 in terza posizione.
auto it = D.begin();
advance(it, 2);
D.insert(it, 500);
5 Esercizi
- Elimina tutti i valori inferiori a 50.
- Conta quante volte compare un certo numero.
- Dividi il deque in due: numeri pari e dispari.
- Simula una coda dove alcuni elementi possono entrare da entrambi i lati.