Лекции

Разбираем ассоциативные контейнеры C++: чем отличается упорядоченный std::map (дерево и O(log N)) от std::unordered_map (хеш‑таблица и среднее O(1)), когда важен порядок ключей, как безопасно читать через find/ contains, почему operator [] может «незаметно» создавать элементы, и какие типичные ошибки встречаются на практике (на примере индекса id → Task для мини‑проекта TaskBook).

Разбираем контейнеры множеств в C++: чем отличается std::set<T> (упорядочивает элементы) от std::unordered_set<T> (хеш-таблица), как пользоваться базовыми операциями insert, contains/ find, erase, как быстро убирать дубликаты из std::vector, и почему элементы set нельзя менять «на месте». В конце — практический мини-кейс (теги в TaskBox) и типичные ошибки.

Разбираем «контракт ключа» для ассоциативных контейнеров C++: почему std::map/ std::set живут в мире строгого порядка (компаратор и operator<), а std::unordered_map/ std::unordered_set — в мире хеша и равенства ( std::hash + ==). Увидим, как контейнер решает «одинаковые ключи или нет», почему компаратор нельзя писать через <=, и что ломается, если изменить равенство и забыть согласовать хеш.

Разбираем, как сделать составной ключ для std::unordered_map: проектируем struct-ключ по нужным полям, пишем корректный operator==, соблюдаем контракт std::hash (если a == b, то и хеши обязаны совпасть), смешиваем хеши полей и подключаем хешер либо третьим шаблонным параметром контейнера, либо через специализацию std::hash<Key>.

Разбираем, как ускорять типичные запросы к данным с помощью индексов: первичный индекс id → объект на базе std::unordered_map, и вторичный индекс tag → набор id на базе std::unordered_map + std::unordered_set. Показываем дисциплину «один источник правды», согласованные операции добавления/удаления/обновления, запросы по id и тегу, а также простую валидацию инвариантов, которая помогает ловить рассинхронизацию.