unordered_set — mulțime rapidă pe hash

De ce contează?

Gândește-te la un vestiar cu dulapuri numerotate. Când vrei dulapul 417, mergi direct la el — nu cauți rând cu rând. Numărul îți spune instant unde să te uiți. Dar dacă te plimbi prin vestiar, dulapurile nu apar într-o ordine anume: le vezi cum sunt aranjate fizic, nu sortate. Exact așa lucrează unordered_set: te duce instant la element, dar nu îți dă nicio ordine.

Ce este un unordered_set și de ce e rapid?

Un unordered_set este o mulțime de elemente unice (fără duplicate), construită pe un tabel hash. Ideea de bază: o funcție hash transformă valoarea ta într-un număr, iar acel număr îți spune în ce „găleată” (bucket) stă elementul. Așa nu cauți prin tot — sari direct la găleata potrivită.

De aceea insert, find și erase sunt O(1) în medie: hash-ul te duce aproape instant la locul corect. Prețul plătit: structura nu păstrează nicio ordine. Spre deosebire de set (care e un arbore echilibrat, mereu sortat), aici parcurgerea iese într-o ordine arbitrară.

Exemplu pas cu pas

Pornim cu un unordered_set gol și inserăm: 42, 7, 42, 15.

insert 42 → hash(42) alege o găleată → {42}
insert 7 → hash(7) alege altă găleată → {42, 7}
insert 42 → deja există → ignorat, rămâne {42, 7}
insert 15 → {42, 7, 15}

Acum find(7) calculează hash(7), merge fix la găleata lui și verifică: e acolo, deci găsit, fără să atingă restul. Dacă parcurgi mulțimea, poți primi 15 7 42 sau orice altă ordine — nu te baza pe ea.

Implementare C++

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

int main() {
    unordered_set<int> s;

    s.insert(42);
    s.insert(7);
    s.insert(42);   // duplicat, ignorat
    s.insert(15);

    cout << s.size() << "\n";          // 3 (42 numarat o singura data)
    cout << s.count(7) << "\n";        // 1 (exista)
    cout << s.count(100) << "\n";      // 0 (nu exista)

    // cautare cu find: returneaza iterator, end() daca lipseste
    if (s.find(15) != s.end()) {
        cout << "15 e in multime\n";
    }

    s.erase(7);                        // stergem 7
    cout << s.count(7) << "\n";        // 0

    // parcurgere: ORDINE ARBITRARA, nu sortata
    for (int x : s) {
        cout << x << " ";              // ex: 15 42  (sau alta ordine)
    }
    cout << "\n";

    return 0;
}

Complexitate

Operație	În medie	Cel mai rău caz
insert	O(1)	O(n)
find / count	O(1)	O(n)
erase	O(1)	O(n)
parcurgere completă	O(n)	O(n)

Cazul cel mai rău (O(n)) apare la coliziuni: când multe valori cad în aceeași găleată, găleata devine o listă lungă pe care trebuie să o străbați. În practică, pe date „normale”, e mai rapid decât set. Reține însă: nu există nicio ordine și deci nici lower_bound / upper_bound.

Observația-cheie

Diferența cheie față de set: set e mereu sortat și are O(log n) garantat, plus lower_bound. unordered_set e mai rapid în medie (O(1)), dar pierde ordinea complet. Alegi în funcție de ce ai nevoie: viteză brută vs. ordine.

Găleți și hash, vizual

Fiecare element ajunge într-o găleată calculată din valoarea sa. Indicii de jos sunt numere de găleată, nu poziții ordonate:

galeti	42	—	15	—	—	7
	0	1	2	3	4	5

Fiecare valoare cade in galeata data de hash. Galetile goale (—) si ordinea lor nu spun nimic despre marimea valorilor.

Greșeli frecvente

Greșeli frecvente de concurs:

Te bazezi pe ordine: parcurgerea unui unordered_set NU e sortată și se poate schimba între rulări. Dacă vrei ordine, folosește set.
Cauți lower_bound: unordered_set nu are lower_bound / upper_bound. Pentru interogări pe interval sau vecini, ai nevoie de set.
Presupui O(1) garantat: cu multe coliziuni o operație poate degenera la O(n). În cazuri adverse (date alese de problemă), set cu O(log n) garantat e mai sigur.
Tipuri custom fără hash: pe int, string etc. merge direct, dar pe o structură proprie (struct/pair brut) NU compilează fără să definești o funcție de hash. set nu cere asta — îi ajunge un operator <.

Recapitulare

unordered_set = mulțime de elemente unice pe tabel hash: insert / find / erase sunt O(1) în medie, O(n) în cel mai rău caz.
NU păstrează ordinea și nu are lower_bound — parcurgerea iese arbitrar.
Alege unordered_set pentru viteză când nu îți pasă de ordine; alege set când ai nevoie de elemente sortate, vecini sau garanție O(log n).