Mediumконтейнеры
Чем map отличается от unordered_map?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
std::map — красно-чёрное дерево: O(log n), упорядочен по ключу, итерация в отсортированном порядке. std::unordered_map — hash table: O(1) average (O(n) worst при rehash), без упорядочения.
std::map<std::string, int> m; // отсортирован по ключу
std::unordered_map<std::string, int> um; // hash, быстрее в среднем
m["apple"] = 1;
um["apple"] = 1;
// map поддерживает lower_bound/upper_bound, unordered — нет- map — если важен порядок, поиск по диапазону ключей, или key нехешируем;
- unordered_map — для простого key-value без упорядочения, обычно быстрее;
- Для пользовательских типов в unordered_map нужно специализировать
std::hash.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.