#вопросы_с_собеседований
Какая разница между std::map и std::unordered_map?

std::map — это ассоциативный контейнер на основе красно-черного дерева. Элементы хранятся в отсортированном порядке по ключу. Сложность операций O(log N).

std::unordered_map реализован как хеш-таблица. Элементы хранятся в произвольном порядке. В среднем сложность операций O(1).

Основные различия между std::map и std::unordered_map:

— Поиск, вставка и удаление в std::map за O(log N) в худшем случае. В std::unordered_map за O(1) в среднем.
— Итераторы std::map позволяют перебирать элементы в отсортированном порядке. Порядок элементов std::unordered_map произвольный.
— Map поддерживает бинарный поиск lower_bound(), upper_bound(), а unordered_map — нет.
— В unordered_map нельзя использовать указатели в качестве ключей в хеш-таблице. В map можно.