Множества и словари

Под set и map лежит сбалансированное двоичное дерево поиска. Отсюда всё их поведение: любая операция за $O(\log n)$, а элементы хранятся в порядке возрастания и обходятся в этом порядке.

Думать про них надо одинаково: map — это тот же set, только вместо элемента хранится пара «ключ и значение», а порядок и поиск идут по ключу.

Базовое

set<int> s;
s.insert(x);
s.erase(x);
bool has = s.count(x) > 0;              // или s.contains(x) с C++20
for (int value : s) ...                 // по возрастанию

Минимум и максимум достаются за константу:

int low = *s.begin();
int high = *s.rbegin();     // то же, что *prev(s.end())

Что возвращает insert

Не void. Возвращает пару: итератор на элемент и bool — вставилось ли.

Это позволяет сэкономить целое обращение к дереву. Наивно:

if (s.find(x) == s.end()) {    // логарифм
    s.insert(x);               // ещё логарифм
    ...
}

Правильно:

if (s.insert(x).second) {      // один логарифм
    ...                        // сюда попадём, только если элемента не было
}

На больших наборах это ровно вдвое меньше работы — и это как раз тот случай, когда решение перестаёт укладываться в лимит из-за лишнего обращения.

Что возвращает erase

Зависит от того, что передали.

• s.erase(x) — число удалённых элементов: 0 или 1 для set, сколько угодно для multiset.
• s.erase(it) — итератор на следующий элемент.

Второе удобнее, чем кажется. Удалить элемент и продолжить с того, что за ним:

auto it = s.find(x);
it = s.erase(it);            // it теперь смотрит на следующий
for (int i = 0; i < 5 && it != s.end(); i++) {
    cout << *it << " ";
    it = s.erase(it);        // вывели и удалили пять следующих
}

Без этого пришлось бы каждый раз искать заново — лишний логарифм на шаг.

Множество с повторами

multiset хранит дубликаты. Главная ловушка:

ms.erase(x);            // удалит ВСЕ элементы, равные x
ms.erase(ms.find(x));   // удалит ровно один

Первый вариант почти никогда не то, что нужно. Из {4, 4, 4, 9} он оставит {9}, второй — {4, 4, 9}.

Часто вместо multiset удобнее map<int, int> со счётчиками: та же логика, но явно видно, сколько чего.

Словарь и значение по умолчанию

Обращение к несуществующему ключу через [] создаёт его со значением по умолчанию — нулём для чисел, пустой строкой для строк.

map<char, int> cnt;
for (char c : text) cnt[c]++;     // работает: несуществующие начинаются с нуля

Заранее заполнять нулями не нужно — это лишний код, который иногда пишут по привычке из других языков.

Обратная сторона: проверка через [] создаёт элемент. if (cnt[x] > 0) на отсутствующем ключе вставит его со значением 0 и увеличит размер словаря. Для проверки нужен count или find.

Поиск границы

auto it = s.lower_bound(x);   // первый элемент >= x
auto jt = s.upper_bound(x);   // первый элемент > x

Вызывать надо методом контейнера, а не свободной функцией:

s.lower_bound(x);                      // логарифм
lower_bound(s.begin(), s.end(), x);    // линия!

Свободная функция умеет прыгать по индексам только там, где есть произвольный доступ. У дерева его нет, и она честно идёт по элементам подряд. Компилятор не предупредит, код скомпилируется и будет работать — просто в тысячу раз медленнее.

Неупорядоченные версии

unordered_set и unordered_map устроены на хеш-таблице: все операции за $O(1)$ в среднем, и на практике они действительно быстрее.

Платить приходится порядком. У них нет:

• обхода по возрастанию — элементы идут как попало;
• минимума и максимума через begin и rbegin;
• lower_bound и upper_bound.

Правило простое: нужен порядок — set, не нужен — unordered_set.

Отдельно стоит знать, что на олимпиадах unordered_map с целыми ключами уязвим: подобранный набор ключей заставляет все значения попасть в одну корзину, и работа становится квадратичной. Против этого добавляют к ключу случайную соль или просто берут map.

Своё сравнение

set<int, greater<int>> s;     // по убыванию

Компаратор здесь — часть типа, а не аргумент конструктора. Требование то же, что у sort: строгий порядок, для равных элементов false. Нарушение приводит к тому, что дерево ломается.