map или unordered_map
Вопрос
Сравните std::map и std::unordered_map: устройство, сложность, требования к ключу, когда что выбирать.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
map: красно-чёрное дерево, O(log n), упорядоченный обход, lower_bound
unordered_map: хеш-таблица с корзинами, O(1) в среднем и O(n) в худшем, перехеширование
Требования к ключу: operator< против хеша и ==
Память и локальность: узел на элемент в обоих, плюс массив корзин
Выбор: нужен порядок или диапазоны берём map, иначе unordered_map
Альтернатива: отсортированный vector или flat_map для частого чтения
Что могут спросить следом
- Как сделать ключом std::pair в unordered_map?
- Что такое атака на хеш-таблицу коллизиями?
Разбор
std::map это сбалансированное дерево поиска, на практике красно-чёрное: поиск, вставка и удаление за O(log n), элементы обходятся в порядке ключей, есть lower_bound и upper_bound для диапазонных запросов. Ключу нужен строгий порядок через operator< или компаратор. std::unordered_map хеш-таблица: массив корзин и цепочки узлов, средняя сложность O(1), худшая O(n), если хеш плохой или данные подобраны злоумышленником. Ключу нужны хеш и ==, для std::pair хеш придётся написать. При росте таблица перехеширует элементы, итераторы инвалидируются. У обоих узел на элемент и плохая локальность. Выбираю так: если нужен порядок, минимальный ключ или диапазоны, беру map, если только поиск по ключу, unordered_map с reserve. А если данные почти не меняются и часто читаются, быстрее всего отсортированный vector с бинарным поиском или std::flat_map из C++23.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.