set in C++: elementi unici e ordinati con std::set

Un sacchetto di valori unici e ordinati

Hai visto come unordered_map memorizza coppie chiave-valore con una ricerca veloce basata su hash. Un std::set è il cugino più semplice: memorizza solo valori, senza dati associati, e applica automaticamente due regole. Ogni elemento è unico (i duplicati vengono scartati senza avvisare) e gli elementi sono sempre mantenuti in ordine.

Questo rende set la scelta naturale per domande come "l'ho già visto?" o "dammi gli elementi distinti in ordine". Inserisci senza preoccuparti dei duplicati e iteri senza dover prima ordinare.

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);   // duplicato: ignorato

    for (int x : s) cout << x << " ";   // 10 30 40 (ordinati, senza ripetizioni)
}

Nota che abbiamo inserito 10 due volte e fuori ordine, eppure l'output è ordinato e 10 compare una volta sola. Il set ha tenuto i conti al posto tuo.

Inserire e rimuovere

insert aggiunge un valore se non è già presente. Restituisce una pair il cui .second è un bool che ti dice se l'inserimento è avvenuto davvero, comodo quando vuoi sapere se un valore era nuovo:

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main() {
    set<string> seen;

    for (string word : {"go", "rust", "go", "cpp"}) {
        auto [it, inserted] = seen.insert(word);
        if (inserted)
            cout << "First time seeing: " << word << "\n";
        else
            cout << "Already saw: " << word << "\n";
    }
}

Per rimuovere un valore, chiama erase con il valore stesso: restituisce il numero di elementi rimossi (0 o 1 per un set). Cancellare qualcosa che non c'è è innocuo, non è un errore:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {1, 2, 3, 4};

    s.erase(3);          // rimuove 3
    s.erase(99);         // non fa nulla, restituisce 0

    for (int x : s) cout << x << " ";   // 1 2 4
}

Verificare la presenza

Lo scopo di un set è proprio rispondere in fretta a "questo c'è?". Il modo più chiaro è count, che restituisce 1 o 0:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> primes = {2, 3, 5, 7, 11};

    if (primes.count(7))
        cout << "7 is prime\n";

    if (!primes.count(9))
        cout << "9 is not in the set\n";
}

Da C++20 c'è un'opzione ancora più leggibile, contains, che restituisce direttamente un bool:

if (primes.contains(7)) { /* ... */ }   // C++20

Un errore comune è usare operator[] come faresti con una map. Un set non ha operator[]: non c'è alcun valore da recuperare, solo una presenza da verificare. Usa count o contains, non s[7].

Se ti serve la posizione effettiva (per cancellarla o per guardare gli elementi vicini), usa find, che restituisce un iteratore o end():

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {10, 20, 30};

    auto it = s.find(20);
    if (it != s.end()) {
        cout << "found " << *it << "\n";
        s.erase(it);   // cancella tramite iteratore: nessuna seconda ricerca
    }
    cout << "size now " << s.size() << "\n";
}

Iterazione ordinata e query su intervalli

Poiché un set è ordinato, l'iterazione restituisce sempre gli elementi dal più piccolo al più grande, e ottieni gratis i trucchi dei container ordinati. lower_bound(x) dà il primo elemento non minore di x, e upper_bound(x) il primo elemento strettamente maggiore di x: insieme ti permettono di scorrere un intervallo numerico senza controllare ogni elemento:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {5, 12, 18, 23, 31, 47};

    // stampa tutto ciò che sta in [12, 31]
    auto begin = s.lower_bound(12);
    auto end = s.upper_bound(31);
    for (auto it = begin; it != end; ++it)
        cout << *it << " ";   // 12 18 23 31
}

Una regola sottile ma importante: gli elementi di un set sono immutabili. L'iteratore ti dà un riferimento const, quindi non puoi cambiare un elemento sul posto: farlo potrebbe rompere l'ordinamento su cui si basa il container. Per "cambiare" un valore, cancella quello vecchio e inserisci quello nuovo.

Per default l'ordinamento è crescente (std::less). Per l'ordine decrescente, fornisci un comparatore diverso come secondo argomento del template:

#include <iostream>
#include <functional>
#include <set>
using namespace std;

int main() {
    set<int, greater<int>> s = {5, 12, 18, 23};

    for (int x : s) cout << x << " ";   // 23 18 12 5
}

set vs multiset vs unordered_set

std::set è uno di tre parenti stretti, e scegliere quello giusto conta:

set<int>            // valori unici, ordinati, O(log n)
multiset<int>       // ammette duplicati, ordinati, O(log n)
unordered_set<int>  // valori unici, NESSUN ordine, O(1) in media

Usa unordered_set quando ti servono solo verifiche di presenza e l'ordine non ti interessa: le sue ricerche basate su hash sono in media più veloci dell'O(log n) basato su albero del set. Scegli set quando ti servono elementi in ordine, query su intervalli con lower_bound/upper_bound o un comportamento stabile degli iteratori. Usa multiset solo quando i duplicati hanno un significato (per esempio un istogramma di valori ripetuti): in un multiset, count(x) può restituire più di 1, ed erase(x) rimuove tutte le copie, a meno che tu non cancelli tramite un singolo iteratore.

Un uso classico di set: eliminare i duplicati da un vector e ordinarlo in un colpo solo.

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    vector<int> data = {4, 1, 4, 2, 1, 3};
    set<int> unique(data.begin(), data.end());

    for (int x : unique) cout << x << " ";   // 1 2 3 4
}

Costruire il set dagli iteratori del vector scarta ogni duplicato e ordina il resto: niente ciclo manuale, niente ordinamento esplicito seguito da std::unique.

Prossimo passo: pair e tuple

Hai già visto .first e .second comparire sulla pair restituita da insert, e le structured binding abbinate alla parola chiave auto (auto [it, inserted]) la spacchettano in modo pulito. Questi tipi leggeri per "riunire qualche valore" sono ovunque nella STL. Nella prossima pagina vedremo direttamente pair e tuple: come costruirle, spacchettarle e restituire più valori da una funzione senza definire un'intera struct.