Când ar trebui să folosiți std::set și când…

std::set și std::unordered_set sunt utilizate pentru stocarea elementelor unice. Alegerea între ele depinde de priorități: ordonare sau performanță la acces, inserare și ștergere.

std::set se bazează pe un arbore binar de căutare echilibrat (de obicei un arbore roșu-negru).

Caracteristici ale std::set:

Elementele sunt stocate în ordine sortată.
Inserarea, ștergerea și căutarea elementelor durează în medie O(log N), unde N este numărul de elemente.
Este potrivit atunci când ordinea elementelor este importantă sau când este necesar să se obțină elemente într-un anumit interval.

std::unordered_set se bazează pe o tabelă hash.

Caracteristici ale std::unordered_set:

Elementele nu sunt stocate în ordine sortată.
Inserarea, ștergerea și căutarea elementelor durează în medie O(1), dar în cel mai rău caz (cu multe coliziuni în funcția hash) pot ajunge la O(N).
Necesită ca tipul elementului să aibă o funcție hash (std::hash) și operatorul de comparație pentru egalitate (operator==).
Este potrivit atunci când se dorește cea mai rapidă inserare, ștergere și căutare, iar ordinea elementelor nu contează.

Tabel sumar:

Criteriu	`std::set`	`std::unordered_set`
Structura internă	Arbore echilibrat	Tabel hash
Ordinea elementelor	Sortată	Nesortată
Timpul mediu de căutare/inserare/ștergere	O(log N)	O(1)
Timpul în cel mai rău caz	O(log N)	O(N)
Cerințe pentru tip	Operator `<`	`std::hash`, `operator==`

Exemplu de utilizare a std::set:

#include <iostream>
#include <set>

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

    // Elementele vor fi afișate în ordine: 2 5 8
    for (int val : set_ordonat) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Exemplu de utilizare a std::unordered_set:

#include <iostream>
#include <unordered_set>

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

    // Ordinea de afișare poate varia
    for (int val : set_neordonat) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Când ar trebui să folosiți std::set și când std::unordered_set în C++?