Каква е сложността при работа с контейнерите map и unordered_map в 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 гарантира логаритмична сложност независимо от данните, запазва елементите в сортиран ред и не изисква хеш функция за типа ключ.