Aká je zložitosť práce s kontajnermi map a unordered_map v C++?

std::map (Červená-čierna strom)

• Vkladanie, odstránenie, vyhľadávanie: O(log N) v priemere a v najhoršom prípade. N je počet prvkov.
• Prístup ku kľúču pomocou operator[] alebo metódy at(): O(log N).
• Získanie iterátora na začiatok/koniec: O(1).
• Iterácia cez všetky prvky: O(N).
• Pamäť: O(N).

std::unordered_map (Hash tabuľka)

• Vkladanie, odstránenie, vyhľadávanie: O(1) v priemere. O(N) v najhoršom prípade (pri silných kolíziách hash). N je počet prvkov.
• Prístup ku kľúču pomocou operator[] alebo metódy at(): O(1) v priemere. O(N) v najhoršom prípade.
• Získanie iterátora na začiatok/koniec: O(1).
• Iterácia cez všetky prvky: O(N) v priemere. Poradie iterácie nie je garantované.
• Pamäť: O(N). Závisí od koeficientu zaťaženia a implementácie hash tabuľky.

Porovnanie:

Operácia	std::map (O)	std::unordered_map (O)
Vkladanie, odstránenie	log N	1 (priemer), N (najhoršie)
Vyhľadávanie	log N	1 (priemer), N (najhoršie)
Prístup ku kľúču	log N	1 (priemer), N (najhoršie)
Iterácia cez všetky prvky	N	N (priemer)

std::unordered_map je všeobecne rýchlejšie pre jednotlivé operácie (vkladanie, vyhľadávanie, mazanie) vďaka O(1) priemeru, ale vyžaduje dobrú hashovaciu funkciu a je citlivé na kolízie. std::map garantuje logaritmickú zložitosť bez ohľadu na dáta, udržiava prvky v zoradenom poradí a nevyžaduje hashovaciu funkciu pre typ kľúča.