De ce contează?
Faci lista de invitați la o petrecere. De fiecare dată când îți vine în minte un
nume, îl scrii pe o foaie. Dar mulți prieteni îți vin în minte de mai multe ori,
așa că lista se umple de dubluri. Ar fi mult mai comod un caiet magic: scrii un
nume, iar dacă el există deja, caietul pur și simplu îl ignoră — și, în plus,
ține toate numele aranjate alfabetic, fără să le sortezi tu. Exact asta este un
std::set.
Ce este
Un std::set este o colecție de elemente unice, păstrate mereu sortat
crescător. „Unice" înseamnă că, dacă încerci să inserezi o valoare care există
deja, setul o ignoră în liniște — nu apare a doua oară. „Sortat" înseamnă că,
atunci când îl parcurgi, primești elementele în ordine crescătoare, oricare ar fi
fost ordinea în care le-ai adăugat.
Nu tu menții ordinea și nu tu elimini dublurile. Le face setul, pentru că în
spate este un arbore binar de căutare echilibrat. De aceea operațiile de bază
— „adaugă", „există?", „șterge" — costă fiecare O(log n), nu O(n).
Două proprietăți merg împreună și definesc setul: unicitate (fără duplicate)
și ordine (mereu crescător). Le obții gratuit — arborele echilibrat din spate
le garantează la fiecare insert, în timp O(log n).