De ce contează?
Un meșter bun nu are o singură unealtă, are o trusă. Înainte să atingă o șurubelniță întreabă: ce fel de șurub, cap drept sau cruce, cât de strâns? La fel cu structurile STL: înainte să scrii o linie de cod, întreabă ce cere problema — ordine, duplicate, viteză sau acces direct — și unealta se alege singură.
Întrebarea care decide
Toate structurile din capitol stochează date. Diferă cât costă fiecare operație și ce garanții îți dau. Pune-ți, pe rând, patru întrebări:
- Am nevoie de elemente în ordine (parcurgere sortată,
lower_bound)? → arbore:set/map - Vreau doar viteză și nu-mi pasă de ordine? → hash:
unordered_set/unordered_map - Pot avea chei duplicate? →
multiset/multimap - Îmi trebuie mereu cel mai prioritar element? →
priority_queue - Am nevoie de acces direct la al i-lea element? →
vector
Tabel de complexități STL
| Structura | Acces | Inserare | Căutare | Ordonat? |
|---|---|---|---|---|
vector | O(1) la index | O(1) amortizat la coadă | O(n) | nu |
list | O(n) | O(1) la pointer dat | O(n) | nu |
deque | O(1) la index | O(1) la ambele capete | O(n) | nu |
set / multiset | — | O(log n) | O(log n) | da (crescător) |
unordered_set | — | O(1) mediu, O(n) rău | O(1) mediu, O(n) rău | nu |
map / multimap | O(log n) după cheie | O(log n) | O(log n) | da (după cheie) |
unordered_map | O(1) mediu după cheie | O(1) mediu, O(n) rău | O(1) mediu, O(n) rău | nu |
priority_queue | O(1) doar vârful | O(log n) | — | parțial (doar maximul/minimul) |
bitset | O(1) la bit | O(1) la bit | O(n/64) operații pe blocuri | nu |
Reguli de decizie + cum recunoști în enunț
- „elementele distincte în ordine crescătoare”, „cel mai mic element ≥ x”,
„
lower_bound” → set / map (arbore ordonat). - „doar verific dacă există / numărul de apariții, foarte rapid, ordinea nu contează” → unordered_set / unordered_map.
- „pot apărea valori egale și le vreau pe toate” → multiset / multimap.
- „scot mereu maximul / minimul rămas”, „următorul task după prioritate”, „Dijkstra” → priority_queue.
- „accesez al i-lea element”, „șir de frecvențe pe indici mici” → vector.
- „adaug și scot la ambele capete” (deque monoton, sliding window) → deque.
„O(1)” la unordered_* este mediu, nu garantat. La coliziuni multe (sau cu
chei alese advers, ca în unele teste) o operație poate degenera la O(n), iar
întregul algoritm la O(n²). Când îți trebuie o garanție pe cel mai rău caz,
set / map cu O(log n) sigur sunt alegerea mai sigură.
map și set au O(log n), dar cu factor constant mare: fiecare nod e alocat
separat în memorie, deci ai sărituri (cache miss) și alocări dese. Pentru n mic
sau valori într-un interval restrâns, un vector simplu (chiar și pentru
frecvențe) bate de departe arborele, deși „pe hârtie” arborele pare la fel de bun.
Greșeli de alegere
Greșeli frecvente de concurs:
unordered_*când ai nevoie de ordine: vrei să parcurgi crescător sau foloseștilower_bound, dar hash-ul nu păstrează nicio ordine — răspuns greșit, nu doar lent.mapcând nu ai nevoie de sortare: plătești log(n) și factor constant mare degeaba; dacă ordinea nu contează,unordered_mape clar mai rapid.- Te bazezi pe O(1) garantat la hash: pe teste ostile coliziunile te duc la O(n) pe operație și depășești timpul; nu presupune niciodată hash perfect.
setpentru numărat când ajunge un vector de frecvență: dacă valorile sunt mici (ex. 0..10⁶),freq[x]++într-unvectore O(1) real, fără logaritm și fără alocări —set/mapaici e risipă.
Recapitulare
- Întreabă întâi: ordine? duplicate? viteză? acces direct? — răspunsul îți alege structura.
- Ordine +
lower_bound→set/map; doar viteză →unordered_*; duplicate →multi*; prioritate →priority_queue; index →vector. - O(1) la hash e doar mediu; arborii sunt O(log n) garantat dar cu factor constant mare — alege după garanția de care ai nevoie.