Koja je složenost rada sa kontejnerima map i unordered_map u C++?

std::map (Црвено-црни дрва)

• Уметање, брисање, претрага: O(log N) у просеку и у најгорем случају. N — број елемената.
• Приступ по кључу помоћу operator[] или методе at(): O(log N).
• Добијање итератора на почетак/крај: O(1).
• Итерација преко свих елемената: O(N).
• Памћење: O(N).

std::unordered_map (Хеш табела)

• Уметање, брисање, претрага: O(1) у просеку. O(N) у најгорем случају (када постоје јаки колизиони хеша). N — број елемената.
• Приступ по кључу помоћу operator[] или методе at(): O(1) у просеку. O(N) у најгорем случају.
• Добијање итератора на почетак/крај: O(1).
• Итерација преко свих елемената: O(N) у просеку. Редослед итерације није загарантован.
• Памћење: O(N). Зависи од коефицијента оптерећења и имплементације хеш табеле.

Поређење:

Операција	std::map (O)	std::unordered_map (O)
Уметање, брисање	log N	1 (просек), N (најгоре)
Претрага	log N	1 (просек), N (најгоре)
Приступ по кључу	log N	1 (просек), N (најгоре)
Итерација преко свих елемената	N	N (просек)

std::unordered_map је генерално бржи за појединачне операције (уметнуће, претрагу, брисање) захваљујући O(1) у просеку, али захтева добру хеш функцију и осетљив је на колизије. std::map гарантује логаритамску сложеност независно од података, одржава елементе у сортираном реду и не захтева хеш функцију за тип кључа.