Выбор ответа Junior Контейнеры STL изнутри спрашивают часто обновлено
Как устроен std::map
Вопрос
Как обычно реализован std::map и какова сложность поиска?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Красно-чёрное дерево, O(log n). Стандарт требует логарифмических операций и упорядоченного обхода, и все основные реализации используют красно-чёрное дерево с узлами в куче. - Хеш-таблица это std::unorderedmap. - Отсортированный массив это std::flatmap из C++23 (и…
Варианты ответа
- Красно-чёрное дерево, O(log n)правильный ответ
- Хеш-таблица, O(1) в среднем
- Отсортированный массив, O(log n)
- Двусвязный список, O(n)
Разбор
Стандарт требует логарифмических операций и упорядоченного обхода, и все основные реализации используют красно-чёрное дерево с узлами в куче.
- Хеш-таблица это
std::unordered_map. - Отсортированный массив это
std::flat_mapиз C++23 (иboost::container::flat_map), у него O(n) на вставку. - Список не обеспечил бы требуемую сложность.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.