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