Care este complexitatea lucrului cu containerele map și unordered_map în C++?

std::map (Arbore roșu-negru)

• Inserare, ștergere, căutare: O(log N) în medie și în cel mai rău caz. N — numărul de elemente.
• Acces după cheie cu operator[] sau metoda at(): O(log N).
• Obținerea iteratorului la început/sfârșit: O(1).
• Iterarea peste toate elementele: O(N).
• Memorie: O(N).

std::unordered_map (Tabel hash)

• Inserare, ștergere, căutare: O(1) în medie. O(N) în cel mai rău caz (când există coliziuni puternice de hash). N — numărul de elemente.
• Acces după cheie cu operator[] sau metoda at(): O(1) în medie. O(N) în cel mai rău caz.
• Obținerea iteratorului la început/sfârșit: O(1).
• Iterarea peste toate elementele: O(N) în medie. Ordinea de iterare nu este garantată.
• Memorie: O(N). Depinde de coeficientul de încărcare și de implementarea tabelului hash.

Comparare:

Operație	std::map (O)	std::unordered_map (O)
Inserare, ștergere	log N	1 (medie), N (cel mai rău)
Căutare	log N	1 (medie), N (cel mai rău)
Acces după cheie	log N	1 (medie), N (cel mai rău)
Iterare peste toate	N	N (medie)

std::unordered_map este de obicei mai rapid pentru operații individuale (inserare, căutare, ștergere) datorită O(1) în medie, dar necesită o funcție hash bună și este sensibil la coliziuni. std::map garantează o complexitate logaritmică independent de date, păstrează elementele în ordine sortată și nu necesită o funcție hash pentru tipul cheii.