La libreria <forward_list> fornisce il contenitore std::forward_list,
una lista collegata *singolarmente* (singly linked list).
È più leggera e veloce di std::list perché ogni nodo contiene:
- un valore
- un solo puntatore al nodo successivo
Tuttavia offre solo l iterazione in avanti (no iteratore al nodo precedente).
1️⃣ Quando usare forward_list?
È ideale quando:
- si fanno molte inserzioni/rimozioni all inizio
- si vuole usare pochissima memoria
- non serve accedere all elemento precedente
2️⃣ Inclusione della libreria
#include <forward_list>
using namespace std;
3️⃣ Dichiarazione e inizializzazione
forward_list L = {1, 2, 3, 4};
forward_list nomi = {"Anna", "Luca", "Marco"};
forward_list vuota; // lista vuota
4️⃣ Metodi principali di forward_list
| Metodo | Descrizione |
|---|---|
push_front(x) | Aggiunge un elemento all inizio |
pop_front() | Rimuove il primo elemento |
insert_after(it, x) | Inserisce dopo una posizione |
erase_after(it) | Rimuove dopo una posizione |
remove(x) | Rimuove tutte le occorrenze di x |
remove_if(pred) | Rimuove elementi che soddisfano il predicato |
sort() | Ordina la lista |
merge() | Fonde due liste ordinate |
unique() | Rimuove duplicati adiacenti |
reverse() | Inverte la lista |
front() | Restituisce il primo elemento |
empty() | Verifica se è vuota |
5️⃣ Inserimento dopo un iteratore
Poiché non esiste push_back né insert, tutto si fa dopo l iteratore.
forward_list L = {1, 2, 3};
auto it = L.begin();
L.insert_after(it, 10); // 1 10 2 3
6️⃣ Rimozione dopo l iteratore
L.erase_after(it); // rimuove il nodo dopo it
7️⃣ remove e remove_if
L.remove(3); // rimuove tutte le occorrenze di 3
L.remove_if([](int x){ return x % 2 == 0; });
8️⃣ merge – unione di liste ordinate
forward_list A = {1,3,5};
forward_list B = {2,4,6};
A.merge(B); // A = {1,2,3,4,5,6}
9️⃣ unique – rimozione duplicati consecutivi
forward_list L = {1,1,2,2,2,3};
L.unique(); // {1,2,3}
🔟 reverse – invertire la lista
L.reverse();
1️⃣1️⃣ Esempio completo
forward_list L = {7, 3, 9, 1};
L.push_front(10);
L.remove(3);
L.sort();
for(int x : L)
cout << x << " ";
LABORATORIO
Uso del Contenitore forward_list
In questo laboratorio imparerai a usare std::forward_list,
eseguendo inserimenti, cancellazioni, ordinamenti e rimozioni condizionali.
Concentrati sull uso di insert_after ed erase_after.
- Libreria
<forward_list> - Iteratore e funzioni insert_after / erase_after
- Metodi sort, unique, merge
1 Creazione lista
Crea una lista riempiendola con numeri casuali (10 elementi).
forward_list L;
for(int i = 0; i < 10; i++)
L.push_front(1 + rand() % 100); // inserimento veloce
2 Inserimento dopo un iteratore
Inserisci il valore 999 dopo il secondo elemento.
auto it = L.begin();
advance(it, 2);
L.insert_after(it, 999);
3 Rimozione condizionale
Rimuovi tutti i numeri inferiori a 30.
L.remove_if([](int x){ return x < 30; });
4 Ordinamento crescente
L.sort();
5 Esercizi
- Dividi la lista in due liste: numeri pari e numeri dispari.
- Conta quante volte compare un numero specifico.
- Usa
unique()per rimuovere duplicati consecutivi. - Fondi due liste ordinate usando
merge().