Jaká je složitost práce s kontejnery map a unordered_map v C++?

std::map (Červená-černé strom)

• Vložení, odstranění, hledání: O(log N) v průměru a v nejhorším případě. N je počet prvků.
• Přístup ke klíči pomocí operator[] nebo metody at(): O(log N).
• Získání iterátoru na začátek/konec: O(1).
• Iterace přes všechny prvky: O(N).
• Paměť: O(N).

std::unordered_map (Hash tabulka)

• Vložení, odstranění, hledání: O(1) v průměru. O(N) v nejhorším případě (při silných kolizích hash). N je počet prvků.
• Přístup ke klíči pomocí operator[] nebo metody at(): O(1) v průměru. O(N) v nejhorším případě.
• Získání iterátoru na začátek/konec: O(1).
• Iterace přes všechny prvky: O(N) v průměru. Pořadí iterace není garantováno.
• Paměť: O(N). Závisí na koeficientu zatížení a implementaci hash tabulky.

Porovnání:

Operace	std::map (O)	std::unordered_map (O)
Vložení, odstranění	log N	1 (průměr), N (nejhorší)
Vyhledávání	log N	1 (průměr), N (nejhorší)
Přístup ke klíči	log N	1 (průměr), N (nejhorší)
Iterace přes všechny prvky	N	N (průměr)

std::unordered_map je obecně rychlejší pro jednotlivé operace (vložení, hledání, mazání) díky O(1) v průměru, ale vyžaduje dobrou hashovací funkci a je citlivý na kolize. std::map garantuje logaritmickou složitost bez ohledu na data, udržuje prvky seřazené a nevyžaduje hashovací funkci pro typ klíče.