Множества и словари: set и map
set и map: быстрые проверки принадлежности, подсчёт различных и частот за O(log n).
Проверять «встречалось ли уже это число» перебором массива — O(n) на каждую проверку. Структуры set и map делают это за O(log n), потому что внутри хранят элементы в сбалансированном дереве.
• std::set — множество уникальных элементов: insert, count, erase. Хранит элементы отсортированными.
• std::map — словарь «ключ → значение»: count[x]++ само создаёт ключ с нулём при первом обращении.
Есть и хеш-версии unordered_set / unordered_map со средним O(1) — быстрее, но без сортированности.
Классика: найти первый повторившийся элемент потока.
Первый повтор. Введите: 6, затем 3 1 4 1 5 9
map незаменим для частотного анализа: за один проход считаем, сколько раз встретилось каждое слово. Проход по map выдаёт ключи в отсортированном порядке — часто это бонус, а не случайность, которой нужно пользоваться.
Частоты слов. Введите: 5, затем: apple banana apple cherry banana
Ориентиры выбора:
• нужна сортированность или «ближайший элемент» — set/map;
• нужна только скорость — unordered-версии;
• нужны повторы — multiset.
Задание: даны n чисел; выведите те, которые встретились ровно один раз, в порядке возрастания (map решает это в шесть строк).
Отметьте урок пройденным и переходите к рекурсии.