Занятие 17. Контейнеры и алгоритмы STL

Семинар складывает карту стандартной библиотеки. Полконтейнера мы уже построили руками: динамический массив и дек — занятие 8, vector изнутри — занятие 16; сегодня достраиваем остальное и, главное, вешаем на карту настоящие ценники: О-символика молчит о константах, а константы здесь отличаются в сотни раз. Замеры реальные (Apple M-серия, clang++ -O2).

Контейнеры и их цены

Карта

* — амортизированно (занятие 10) · † — O(log n) бинпоиском после сортировки (занятие 12) · ‡ — сама вставка O(1), но дойти до места — O(n). Устройство дерева и хеш-таблицы — второй семестр; сегодня это контракты с ценами.

Замер 1: миллион вставок в конец

insert vector:            1.1 мс
insert deque:             1.1 мс
insert list:             15.3 мс   # ×14
insert set:             291.6 мс   # ×265
insert unordered_set:   113.2 мс   # ×103

vector/deque кладут int в готовый буфер — почти бесплатно (амортизация работает). list платит аллокацией узла за каждую вставку — ×14. set — аллокация плюс спуск по дереву, где каждый уровень — кэш-промах (занятие 8), — ×265. unordered_set — хеш, корзина и периодический rehash — ×103. Одинаковые «O(1)» и «O(1)» на практике отличаются в сотню раз.

Замер 2: миллион проверок «есть ли x?»

# 10^6 элементов, 10^6 запросов
sorted vector + binary_search:  41.3 мс
set:                           449.4 мс   # ×11
unordered_set:                  30.2 мс   # чемпион

Оба «логарифма», а разница ×11: бинпоиск прыгает по непрерывной памяти, дерево — по узлам-указателям (занятия 8 и 12). unordered_set — в среднем один прыжок по хешу: быстрее всех, но без порядка и с худшим случаем O(n). Статичные данные + много запросов — отсортированный вектор бьёт дерево по скорости и памяти: приём «инвестиция» из занятия 15.

Кто держит порядок

1
2
3
4
5

std::set<int>           s = {50, 3, 17, 99, 8};
std::unordered_set<int> u = {50, 3, 17, 99, 8};

for (int x : s) std::cout << x << ' ';   // 3 8 17 50 99  — всегда отсортировано
for (int x : u) std::cout << x << ' ';   // 99 17 8 3 50  — как легло по корзинам

У set/map есть свои lower_bound/upper_bound — границы из занятия 12 за O(log n) на живом, меняющемся множестве. Ниша deque — очередь: O(1) с обоих концов без переезда. Ниша list — «почти никогда» (занятие 8: обход ×36 медленнее вектора); оправдан, когда итератор уже стоит на месте вставки и адреса обязаны быть стабильными.

Итераторы

Один интерфейс для всех контейнеров

1
2
3
4
5
6
7

std::set<int> s = {3, 1, 4};

for (auto it = s.begin(); it != s.end(); ++it)
    std::cout << *it;                     // как указатель: *, ++

auto pos = std::find(s.begin(), s.end(), 4);
if (pos != s.end()) { /* нашли */ }

Итератор — обобщённый указатель: у вектора это почти буквально указатель, у списка — обёртка над узлом, у дерева — позиция обхода. Диапазон — всегда полуинтервал [begin, end): конвенция занятий 12 и 15 оказалась конвенцией всей STL. end() — не последний элемент, а сентинель за краем: «не нашли» = end(), ровно как ±∞ в бинпоиске. Инвалидация из занятия 16 — общая тема: у вектора при переезде рвётся всё, у list/set/map — только итератор удалённого элемента.

Категории: что итератор умеет

Категория — это контракт: алгоритм объявляет минимальные требования. std::sort требует random access — ему нужны прыжки к середине. Занятие 12 говорило «бинпоиск за O(log n) — только на random access»: категория определяет не только «скомпилируется ли», но и цену.

Читаем отказ: sort не берёт list

1
2

std::list<int> l = {3, 1, 2};
std::sort(l.begin(), l.end());   // ошибка!

.../make_heap.h:35: error: invalid operands to binary expression
  ('std::__list_iterator<int, void *>' and 'std::__list_iterator<int, void *>')

Ошибка прилетает из недр библиотеки (make_heap.h!), не из вашей строки: sort попытался вычесть list-итераторы, а такой операции нет. Навык чтения простыни ошибок: найти свою строку и первый «invalid operands». Лечение — собственный l.sort(): сортировка слиянием по узлам. Коварнее случаи, которые компилируются: std::distance и std::advance на списке работают — но за O(n). Категория решает цену молча.

Алгоритмы

Рабочая дюжина

Все берут полуинтервал, многие — предикат-лямбду из занятия 14. Сырой цикл, заменимый одной строкой отсюда, почти всегда стоит заменить: меньше мест для ошибки на единицу.

Ловушка 1: тип аккумулятора задаёт init

1
2
3
4

std::vector<int> v(3'000'000, 1000);        // честная сумма: 3·10⁹ > INT_MAX

std::accumulate(v.begin(), v.end(), 0);     // аккумулятор — int, как у нуля!
std::accumulate(v.begin(), v.end(), 0LL);   // аккумулятор — long long

accumulate(..., 0):   -1294967296   # переполнение
accumulate(..., 0LL): 3000000000    # верно

Тип суммы accumulate выводит из третьего аргумента, а не из элементов. Одна буква LL отделяет верный ответ от занятия 3 с минусом. Дисциплина та же, что у префиксных сумм занятия 15: суммы живут в long long. Общий урок обобщённого кода: типы выводятся из аргументов — проверяйте, из каких.

Ловушка 2: sort не обещает порядок равных

Сортируем студентов (оценка, номер в журнале) только по оценке:

sort:        порядок равных ПЕРЕМЕШАН   → оценка 3, номера: 39 3 27 9 12 15 ...
stable_sort: порядок равных сохранён    → оценка 3, номера: 0 3 6 9 12 15 ...

sort 10^7:        177 мс
stable_sort 10^7: 167 мс

Стабильность — сохранение исходного порядка элементов с равными ключами. sort её не обещает — и уже на 40 элементах перемешал. Когда важна: каскадная сортировка «по главному ключу, внутри — по второстепенному» (сортируем по второстепенному, затем stable по главному). Цена на наших данных около нуля — но stable_sort может требовать O(n) дополнительной памяти. И осторожно: на маленьких массивах sort часто «случайно стабилен» — гарантия есть только у stable_sort.

Ловушка 3: remove ничего не удаляет

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

std::vector<int> v = {1, 0, 2, 0, 3};

std::remove(v.begin(), v.end(), 0);
// v = {1, 2, 3, ?, ?}  — size() всё ещё 5!

v.erase(std::remove(v.begin(), v.end(), 0), v.end());   // идиома erase–remove
// v = {1, 2, 3}

std::erase(v, 0);                                       // C++20: одной строкой
std::erase_if(v, [](int x){ return x < 0; });

Алгоритм видит только итераторы — он не знает, в каком контейнере живёт диапазон, и не может менять его размер. Поэтому remove лишь переупаковывает нужное в начало и возвращает границу «нового конца», а отрезает хвост сам контейнер. Забытый erase — прежний размер и мусор в хвосте: классика код-ревью. C++20 закрыл вопрос парой std::erase / std::erase_if.

Компараторы

1
2
3
4
5
6
7

struct Student { std::string name; int height; };

// по имени; при равенстве — по росту:
std::sort(v.begin(), v.end(),
    [](const Student& a, const Student& b) {
        return std::tie(a.name, a.height) < std::tie(b.name, b.height);
    });

Компаратор — третий аргумент: функтор из занятия 16 или лямбда из занятия 14. std::tie даёт каскад ключей одной строкой — лексикографическое сравнение ссылок на поля. Для «естественного» порядка типа лучше operator<=> со = default (занятие 16); для ситуативного — лямбда на месте.

Задачи семинара

1. Топ-3 слова. Дан текст — найти три самых частых слова. unordered_map<string,int> для счёта → перекладка в вектор пар → sort с компаратором по убыванию счёта. Почему на счёте unordered, а не map?

   Разбор

   Порядок при подсчёте не нужен — нужен только быстрый доступ по ключу, а это средний O(1) хеш-таблицы против O(log n) дерева с кэш-промахами (наш замер: ×11 на поиске). Сортировка нужна лишь в конце и по значению, а не по ключу — её всё равно делать отдельно: std::partial_sort на топ-3 или полный sort вектора пар с лямбдой [](auto& a, auto& b){ return a.second > b.second; }.

2. Пересечение массивов по 10⁶ — тремя способами: sort + два указателя (занятие 12), set, unordered_set. До запуска предскажите порядок скоростей по замерам занятия.

   Разбор

   Ожидание из замеров: unordered_set (строим за ~113 мс, 10⁶ count по ~30 нс) ≈ sort+два указателя (две сортировки по ~20 мс на 10⁶ + линейное слияние, всё в непрерывной памяти) — оба сильно впереди set (вставка ×265, поиск ×11). Точный победитель между первыми двумя зависит от данных: сортировка выигрывает на повторных запросах (инвестиция), хеш — на разовой операции. Ключевой навык — предсказать порядок и объяснить его памятью, а не угадать миллисекунды.

3. Дубликаты, но порядок. Удалить дубликаты, сохранив порядок первых вхождений: {3, 1, 3, 2, 1} → {3, 1, 2}.

   Разбор

   std::unique не подходит: он сжимает только подряд идущие дубликаты, а сортировка убьёт порядок. Решение — множество «уже видел» плюс erase_if:

   1 2	std::unordered_set<int> seen; std::erase_if(v, [&seen](int x) { return !seen.insert(x).second; });

   insert возвращает пару (итератор, «вставилось ли»): второе вхождение не вставляется — предикат истинен — элемент удаляется. Порядок остальных сохранён: erase_if стабилен.

Домашнее задание (сдача через Git)

1. Частотный анализ: топ-10 слов текстового файла (unordered_map + sort с компаратором; при равной частоте — алфавитный порядок через std::tie).
2. Пересечение и разность двух массивов тремя способами + таблица замеров своей машины по методике занятия 16.
3. Каскадная сортировка: журнал (фамилия, группа, оценка) — по группе, внутри по убыванию оценки, внутри по фамилии: одним компаратором с tie и последовательностью stable_sort; докажите совпадение результатов.
4. Чистка циклов: найдите в своих прошлых ДЗ три сырых цикла и перепишите на count_if / min_element / accumulate; приложите ссылки на коммиты до/после.
5. * Хеш для пары: положите pair<int,int> в unordered_set — напишите свою хеш-функцию и объясните, чем плоха h = x ^ y (подсказка: что будет на парах (a, a)?).

Следующее занятие — тёмная сторона: reinterpret_cast, union, неопределённое поведение и выравнивание данных. Посмотрим, что лежит под типами, — и почему компилятор вправе удалить ваш код целиком.