Quando usare std::set e quando std::unordered_set in…

std::set e std::unordered_set vengono utilizzati per memorizzare elementi unici. La scelta tra loro dipende dalle priorità: ordinamento o prestazioni di accesso/inserimento/eliminazione.

std::set si basa su un albero binario di ricerca bilanciato (solitamente un albero rosso-nero).

Caratteristiche di std::set:

Gli elementi sono memorizzati in ordine ordinato.
Inserimento, eliminazione e ricerca di elementi richiedono in media O(log N), dove N è il numero di elementi.
È adatto quando l'ordine degli elementi è importante o quando si necessita di ottenere elementi in un intervallo specifico.

std::unordered_set si basa su una tabella hash.

Caratteristiche di std::unordered_set:

Gli elementi non sono memorizzati in ordine ordinato.
Inserimento, eliminazione e ricerca di elementi in media richiedono O(1), ma nel caso peggiore (con molte collisioni nella funzione hash) possono arrivare a O(N).
Richiede che il tipo di elemento abbia una funzione hash (std::hash) e un operatore di confronto di uguaglianza (operator==).
È adatto quando si desidera la massima velocità di inserimento, eliminazione e ricerca, e l'ordine degli elementi non è importante.

Tabella riepilogativa:

Criterio	`std::set`	`std::unordered_set`
Struttura interna	Albero bilanciato	Tabella hash
Ordine degli elementi	Ordinato	Non ordinato
Tempo di ricerca/inserimento/eliminazione (media)	O(log N)	O(1)
Tempo di ricerca/inserimento/eliminazione (peggiore caso)	O(log N)	O(N)
Requisiti del tipo	Operatore `<`	`std::hash`, `operator==`

Esempio di utilizzo di std::set:

#include <iostream>
#include <set>

int main() {
    std::set<int> ordered_set;
    ordered_set.insert(5);
    ordered_set.insert(2);
    ordered_set.insert(8);

    // Gli elementi verranno stampati in ordine: 2 5 8
    for (int val : ordered_set) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Esempio di utilizzo di std::unordered_set:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> unordered_set;
    unordered_set.insert(5);
    unordered_set.insert(2);
    unordered_set.insert(8);

    // L'ordine di output può variare
    for (int val : unordered_set) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Quando usare std::set e quando std::unordered_set in C++?