De ce contează?
Un bodyguard stă la ușa clubului cu o listă de invitați. Când vine cineva, nu
citește lista de la cap la coadă: numele tău începe cu „M”, deci sare direct la
sertarul „M” și verifică doar acolo. Răspunde aproape instant cu „ești pe listă”
sau „nu ești” — dar nu-ți poate spune cine e primul pe listă în ordine
alfabetică, fiindcă nu ține lista sortată, ci împărțită pe sertare. Exact așa
lucrează unordered_set.
Ce este
std::unordered_set este o mulțime de elemente unice — fiecare valoare apare
o singură dată — construită pe o tabelă de dispersie (hash). La fel ca set,
îți răspunde la întrebarea „valoarea asta există în mulțime?”. Diferența e cum
o face: în loc să țină elementele sortate într-un arbore, le împrăștie în „găleți”
după valoarea lor hash, ca bodyguardul cu sertarele.
De aici vine marele avantaj: insert, find și count rulează în O(1) mediu
— practic instant, indiferent câte elemente ai. La set, aceleași operații costă
O(log n), pentru că trebuie să coboare prin arbore. Prețul plătit pentru viteză
este lipsa oricărei ordini: parcurgerea unui unordered_set îți dă elementele
într-o ordine impredictibilă, nu crescător.
Regula de aur: unordered_set = viteză fără ordine (O(1) mediu), set =
ordine cu preț (O(log n), mereu sortat). Dacă tot ce vrei e „l-am mai văzut?”
și ordinea nu contează, alegi unordered_set. Dacă ai nevoie de elemente sortate
sau de cel mai mic/mare, alegi set.