Лекции

Разбираем, как ускорять поиск данных с помощью индексов и при этом не сломать согласованность: почему нужен один «источник правды», что такое инварианты, как строить схему id → позиция и вторичные индексы ( email, tag), чем опасны указатели/итераторы на элементы std::vector, как правильно делать удаление через swap-erase, когда выгодно rebuild индекса, и почему assert помогает ловить рассинхронизацию раньше, чем её увидит пользователь.

Разбираем сортировку в C++ как операцию над диапазоном и сравниваем std::sort и std::stable_sort: что означает стабильность, почему «равные» элементы могут «прыгать», как задаётся порядок через компаратор comp (функция bool), и как применять стабильную сортировку в практических сценариях — UX-списки задач и многошаговая сортировка по нескольким ключам.

Разбираем компаратор как контракт порядка: как читать comp(a, b), почему нельзя писать <=/ >=, что такое strict weak ordering (в терминах C++ — concept strict_weak_order), как устроена эквивалентность ! comp(a, b) && ! comp(b, a), зачем нужен tie-breaker, и почему один и тот же компаратор должен переиспользоваться в std::sort и std::lower_bound/ std::binary_search.

Разбираем семейство алгоритмов бинарного поиска в C++: как быстро проверять наличие ключа через std::binary_search, как получать позицию вставки и «кандидата на совпадение» через std::lower_bound, и как находить правую границу дубликатов через std::upper_bound. Отдельно фиксируем главное предусловие: диапазон обязан быть отсортирован тем же порядком (тот же operator< или тот же компаратор), иначе результат не гарантируется. Закрепляем всё на примере поиска по struct Task и поддержания отсортированности в мини-приложении TaskBox.

Разбираем «агрегации диапазона» в C++ (STL): как безопасно сворачивать контейнер в одно значение через std::accumulate (и почему тип результата задаётся параметром init), как находить экстремумы через std::min_element/ std::max_element и за один проход получать обе границы с std::minmax_element. Все примеры привязаны к мини‑приложению TaskBoard на std::vector и сопровождаются разбором типичных ошибок.