Лекции

Разбираем, почему одинаковая асимптотика ( O(N)) ещё не гарантирует одинаковую скорость: как CPU-кэш и линии кэша «любят» подряд лежащие элементы, почему std::vector с непрерывной памятью часто выигрывает у std::list (узлы и прыжки по памяти), где находится компромисс std::deque, и как почувствовать локальность на практике (печать адресов, линейные проходы, аккуратный стиль итерации). В конце — типичные ошибки оптимизации: слепая вера в O(1), выводы по одному эксперименту и игнорирование правил инвалидирования ссылок у vector.

Разбираем, почему компаратор в std::set и std::map — это часть корректности контейнера, а не «опция сортировки»: как определяется эквивалентность ключей через comp, что такое strict weak ordering, почему нельзя писать <= вместо <, зачем нужен tie-breaker, и почему компаратор должен быть «чистым» (без внешнего изменяемого состояния и побочных эффектов).

Разбираем, как устроены хеш-контейнеры C++: путь поиска key → hash → bucket → проверка равенства через ==, что такое bucket_count() и load_factor(), почему плотность влияет на скорость и как рост вызывает rehash с инвалидированием итераторов. Показываем инженерные приёмы: reserve(), max_load_factor(), мини-диагностика и практический индекс по id на базе std::unordered_map.

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

Разбираем инженерный выбор контейнера в C++: когда стоит оставаться на std::vector (включая вариант «сортированный вектор» + бинарный поиск), а когда выгоднее взять std::map. На учебном кейсе «справочник контактов» сравниваем поиск по ключу, вставку/удаление, порядок обхода, влияние кэш-локальности и накладные расходы по памяти, а также формулируем практические вопросы, которые помогают выбрать контейнер под требования.