La libreria <set> fornisce il contenitore std::set,
una struttura ordinata che memorizza elementi unici in ordine crescente.
Internamente è implementato come un albero bilanciato (Red-Black Tree). Per questo motivo:
- gli elementi sono sempre ordinati
- non ci sono duplicati
- ricerca, inserimento e cancellazione sono O(log n)
1️⃣ Inclusione della libreria
#include <set>
using namespace std;
2️⃣ Dichiarazione e inizializzazione
set S = {3, 1, 4, 1, 5, 9};
// Il 1 duplicato viene eliminato
3️⃣ Caratteristiche principali di set
| Caratteristica | Descrizione |
|---|---|
| Ordine | ✔️ Crescente |
| Duplicati | ❌ Non ammessi |
| Tipo struttura | Albero Red-Black |
| Complessità operazioni | O(log n) |
| Iterazione | Ordinata |
4️⃣ Metodi principali di std::set
| Metodo | Descrizione |
|---|---|
insert(x) | Inserisce l elemento (se non esiste) |
erase(x) | Rimuove un elemento |
find(x) | Restituisce iteratore all elemento |
count(x) | Ritorna 0 o 1 (esistenza) |
size() | Numero elementi |
empty() | Set vuoto? |
clear() | Svuota il set |
lower_bound(x) | Primo elemento ≥ x |
upper_bound(x) | Primo elemento > x |
5️⃣ Inserimento e iterazione
set S;
S.insert(5);
S.insert(1);
S.insert(3);
S.insert(3); // ignorato
for(int x : S)
cout << x << " "; // 1 3 5
6️⃣ Ricerca e cancellazione
if(S.find(3) != S.end())
cout << "Trovato!";
S.erase(3);
7️⃣ lower_bound e upper_bound
auto it = S.lower_bound(4); // primo ≥ 4
cout << *it; // esempio: 5
8️⃣ Esempio completo
set nomi = {"Luca", "Anna", "Marco"};
nomi.insert("Paolo");
nomi.erase("Anna");
for(auto& n : nomi)
cout << n << endl;
LABORATORIO
Uso del Contenitore set
In questo laboratorio imparerai a utilizzare std::set
per memorizzare valori unici, eliminare duplicati, ordinare i dati
e cercare elementi in modo efficiente.
Strumenti:
- Libreria
<set> - Metodi insert, erase, find, lower_bound
- Iterazione ordinata
1 Rimuovere duplicati
Chiedi 10 numeri all utente e memorizzali in un set per eliminare automaticamente i duplicati.
set S;
int x;
for(int i=0; i<10; i++){
cin >> x;
S.insert(x);
}
2 Ricerca veloce
Controlla se un numero inserito dall utente è presente nel set.
cout << "Cerca: ";
cin >> x;
if(S.count(x))
cout << "Presente!";
else
cout << "Assente!";
3 Trovare il primo numero ≥ X
cout << "Inserisci un valore: ";
cin >> x;
auto it = S.lower_bound(x);
if(it != S.end())
cout << "Primo ≥ x: " << *it;
else
cout << "Nessun valore ≥ x";
4 Esercizi
- Memorizza nomi e rimuovi quelli duplicati.
- Conta quanti numeri diversi sono stati inseriti.
- Unisci due set eliminando automaticamente i duplicati.
- Trova minimo, massimo e mediana usando il set.