Mediumконтейнеры
Чем std::set/std::multiset отличаются от unordered версий?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
std::set — упорядоченное множество уникальных элементов (красно-чёрное дерево): O(log n), итерация в отсортированном порядке, lower_bound/upper_bound. std::unordered_set — hash table: O(1) average, без упорядочения.
std::set<int> s{3, 1, 2}; // {1, 2, 3} — отсортирован
std::multiset<int> ms{1, 1, 2}; // разрешает дубликаты
std::unordered_set<int> us{3, 1}; // порядок не гарантирован
auto it = s.lower_bound(2); // O(log n) — есть только у set- set/multiset — когда важен порядок, диапазонные запросы, или элемент нельзя хешировать (только
<); - unordered — для простого членства и быстрого доступа;
- set — overhead 3 указателя на узел; unordered — overhead на buckets.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.