Jaka jest złożoność pracy z kontenerami map i unordered_map w C++?

std::map (Czerwonoczarny drzewo)

• Wstawianie, usuwanie, wyszukiwanie: O(log N) średnio i w najgorszym przypadku. N — liczba elementów.
• Dostęp po kluczu za pomocą operator[] lub metody at(): O(log N).
• Uzyskanie iteratora na początek/koniec: O(1).
• Iteracja po wszystkich elementach: O(N).
• Pamięć: O(N).

std::unordered_map (Tablica haszująca)

• Wstawianie, usuwanie, wyszukiwanie: O(1) średnio. O(N) w najgorszym przypadku (przy silnych kolizjach hasza). N — liczba elementów.
• Dostęp po kluczu za pomocą operator[] lub metody at(): O(1) średnio. O(N) w najgorszym przypadku.
• Uzyskanie iteratora na początek/koniec: O(1).
• Iteracja po wszystkich elementach: O(N) średnio. Kolejność iteracji nie jest gwarantowana.
• Pamięć: O(N). Zależy od współczynnika załadowania i implementacji tablicy haszującej.

Porównanie:

Operacja	std::map (O)	std::unordered_map (O)
Wstawianie, usuwanie	log N	1 (średnio), N (najgorzej)
Wyszukiwanie	log N	1 (średnio), N (najgorzej)
Dostęp po kluczu	log N	1 (średnio), N (najgorzej)
Iteracja po wszystkich	N	N (średnio)

std::unordered_map jest zwykle szybszy dla pojedynczych operacji (wstawianie, wyszukiwanie, usuwanie) dzięki O(1) w średnim przypadku, ale wymaga dobrej funkcji hashującej i jest wrażliwy na kolizje. std::map gwarantuje złożoność logarytmiczną niezależnie od danych, przechowuje elementy w posortowanej kolejności i nie wymaga funkcji hashującej dla typu klucza.