set — mulțime ordonată fără duplicate

De ce contează?

Imaginează-ți lista de invitați la o petrecere. Vrei două lucruri: să nu apară nimeni de două ori și, când o citești, numele să fie deja în ordine alfabetică. Dacă încerci să adaugi un invitat care e deja pe listă, pur și simplu nu se schimbă nimic. Exact așa se comportă un set: o mulțime ordonată de elemente unice.

Ce este un set și de ce îl folosești

Un set este o colecție de valori unice, ținute mereu în ordine crescătoare. În spate, STL îl implementează ca un arbore binar de căutare echilibrat, de aceea adăugarea, ștergerea și căutarea costă toate O(log n).

Îl alegi când ai nevoie simultan de două garanții:

fără duplicate — orice valoare apare cel mult o dată;
ordonat — îl parcurgi sortat, fără să apelezi vreodată un sort.

Dacă ție nu îți pasă de ordine și vrei doar viteză maximă, există unordered_set (tabel de dispersie, O(1) mediu). Diferența e exact aceasta: set e ordonat, unordered_set nu. Plătești log n pentru a primi elementele sortate.

Cum funcționează, pas cu pas

Pornim cu un set gol și inserăm, în această ordine: 7, 3, 9, 3, 1.

insert 7 → {7}
insert 3 → {3, 7} (s-a așezat înaintea lui 7, fiindcă setul ține ordinea)
insert 9 → {3, 7, 9}
insert 3 → {3, 7, 9} (3 există deja → ignorat, nimic nu se schimbă)
insert 1 → {1, 3, 7, 9}

Observă două lucruri: al doilea 3 n-a făcut nimic, iar valorile au rămas sortate fără efort din partea ta. O parcurgere de la begin() la end() îți dă 1 3 7 9.

Observația-cheie

Setul nu reține ordinea inserării și nici nu permite acces pe poziție (s[2] nu există). Singura ordine pe care o vezi e cea crescătoare a valorilor. Dacă ai nevoie de duplicate, folosești multiset; dacă ai nevoie de perechi cheie-valoare, folosești map.

Implementare C++

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

int main() {
    set<int> s;

    s.insert(7);
    s.insert(3);
    s.insert(9);
    s.insert(3);   // duplicat: ignorat silentios
    s.insert(1);

    // parcurgere automat sortata: 1 3 7 9
    for (int x : s) {
        cout << x << " ";
    }
    cout << "\n";

    cout << s.size() << "\n";        // 4 (nu 5: duplicatul nu a contat)
    cout << s.count(3) << "\n";      // 1 (exista)
    cout << s.count(5) << "\n";      // 0 (nu exista)

    if (s.find(9) != s.end()) {      // find returneaza iterator, nu bool
        cout << "9 este in set\n";
    }

    s.erase(3);                      // sterge valoarea 3
    cout << s.size() << "\n";        // 3

    // lower_bound: primul element >= 4  -> 7
    // upper_bound: primul element  > 7  -> 9
    cout << *s.lower_bound(4) << "\n";   // 7
    cout << *s.upper_bound(7) << "\n";   // 9

    return 0;
}

insert întoarce de fapt o pereche (iterator, bool): al doilea câmp e true dacă elementul chiar a fost adăugat și false dacă exista deja. E modul corect de a afla dacă un element era nou.

Complexitate

Operație	Timp
`insert`	O(log n)
`find` / `count`	O(log n)
`erase`	O(log n)
`lower_bound` / `upper_bound`	O(log n)
parcurgere completă (sortată)	O(n)

Observația-cheie

Toate operațiile de bază sunt O(log n) fiindcă arborele rămâne echilibrat. Pentru n elemente, construirea unui set prin n inserări costă O(n log n) — adesea mai ieftin decât să sortezi separat și să elimini duplicatele manual.

Greșeli frecvente

Greșeli frecvente cu set:

Te aștepți la duplicate. Al doilea insert(3) e ignorat silențios — fără eroare, fără mesaj. Dacă chiar vrei duplicate, ai nevoie de multiset.
Tratezi count ca pe un contor real. La set, count întoarce doar 0 sau 1, niciodată mai mult, fiindcă valorile sunt unice.
Folosești set unde unordered_set e mai potrivit. Dacă nu îți trebuie ordinea, unordered_set e mai rapid (O(1) mediu). Nu plăti log n degeaba.
Folosești iteratorul după erase. Ștergerea invalidează iteratorul către elementul șters; nu-l mai dereferenția. Reține valoarea returnată de erase (în C++11+) sau caută din nou.

Diagramă: mulțime ordonată

set	1	3	7	9
		lower_bound(4)→7

Valorile stau mereu sortate. lower_bound(4) sare la primul element ≥ 4.

Recapitulare

set ține valori unice și ordonate crescător; insert pe un duplicat nu schimbă nimic.
insert, find, count, erase sunt toate O(log n); parcurgerea îți dă elementele deja sortate.
Alegi set când vrei ordine; alegi unordered_set când vrei doar viteză și nu îți pasă de ordine.