# Майлстоун. Вы познакомились с STL Поздравляем, вы добрались до второго майлстоуна! Он поможет закрепить теорию и проверить, насколько хорошо вы разобрались с итераторами, контейнерами и алгоритмами. В подсказке для каждой задачи помимо ценных советов приведены ссылки на разделы глав с теорией. Поехали! ## Разогрев Считается ли строка `std::string` контейнером? `Y/N`. {.task_text} ```consoleoutput {.task_source #cpp_chapter_0083_task_0010} ``` Строку называют псевдо-контейнером из-за ограничений на типы данных, которые она позволяет хранить. **Темы, затронутые в задаче:** [какие бывают контейнеры.](/courses/cpp/chapters/cpp_chapter_0071/#block-string) {.task_hint} ```cpp {.task_answer} N ``` Какая алгоритмическая сложность у вставки, удаления и поиска элемента в `std::map`? Введите ответ в O-нотации, например `O(N^2)`. {.task_text} ```consoleoutput {.task_source #cpp_chapter_0083_task_0020} ``` Элементы упорядоченных ассоциативных контейнеров всегда отсортированы. **Темы, затронутые в задаче:** [классификация контейнеров,](/courses/cpp/chapters/cpp_chapter_0071/#block-classification) [алгоритмическая сложность работы с упорядоченными ассоциативными контейнерами.](/courses/cpp/chapters/cpp_chapter_0073/#block-algo) {.task_hint} ```cpp {.task_answer} O(log(N)) ``` На каких строках кода допущены ошибки? Перечислите их через пробел. Интересующие строки отмечены пронумерованными комментариями. {.task_text} ```cpp {.example_for_playground .example_for_playground_001} std::deque<std::size_t> session_ids = {57, 89, 22}; const auto it = session_ids.begin(); ++it; // 1 *it = 0; // 2 auto cit = session_ids.cbegin(); ++cit; // 3 *cit = 0; // 4 ``` ```consoleoutput {.task_source #cpp_chapter_0083_task_0030} ``` Итератор, объявленный с квалификатором `const` — это константа. Как и любую константу, такую переменную нельзя менять. Зато можно менять значение объекта, на который он указывает. Метод контейнера `cbegin()` возвращает итератор типа `const_iterator`. И с ним ситуация обратная. **Темы, затронутые в задаче:** [константные итераторы,](/courses/cpp/chapters/cpp_chapter_0062/#block-const) [ключевое слово auto](/courses/cpp/chapters/cpp_chapter_0062/#block-auto). {.task_hint} ```cpp {.task_answer} 1 4 ``` ## Пони из бездны Что выведет этот код? {.task_text} ```cpp {.example_for_playground .example_for_playground_002} std::map<int, std::string> ponies; ponies[5] = "Rumble"; ponies[9] = "Braeburn"; if (ponies[2] == "Snails") ponies[8] = "Starlight Glimmer"; std::print("{}", ponies.size()); ``` ```consoleoutput {.task_source #cpp_chapter_0083_task_0040} ``` Обращение к элементу ассоциативного контейнера через `[]` создаёт ключ, если он отсутствует. К нему привязывается значение по умолчанию. **Темы, затронутые в задаче:** [доступ к элементу ассоциативного контейнера](/courses/cpp/chapters/cpp_chapter_0073/#block-key-creation). {.task_hint} ```cpp {.task_answer} 3 ``` В словарях `std::map` и `std::unordered_map` обращение к элементу через `[]` не является read-only операцией! Если ключ не найден, он добавляется вместе со значением по умолчанию. Поэтому к константному словарю не получится применить `[]`: ```cpp {.example_for_playground .example_for_playground_003} const std::map<int, std::string> ponies = { {5, "Rumble"}, {9, "Braeburn"}, }; if (ponies[2] == "Snails") // Ошибка компиляции std::print("Found!"); ``` ``` main.cpp:13:11: error: no viable overloaded operator[] for type 'const std::map<int, std::string>' (aka 'const map<int, basic_string<char>>') 13 | if (ponies[2] == "Snails") ``` Вывод: если нужен read-only доступ, вместо `[]` вызывайте методы [find()](https://en.cppreference.com/w/cpp/container/map/find.html) и [contains()](https://en.cppreference.com/w/cpp/container/map/contains.html). И второй вывод: используйте `[]`, чтобы писать лаконичный код без лишних проверок: ```cpp {.example_for_playground .example_for_playground_004} std::string text = "3 + 3 = 6"; // Строим частотный словарь символов std::unordered_map<char, std::size_t> char_count; // Нам не надо проверять, содержится ли ключ в словаре // Если его нет, то по нему создаётся значение по умолчанию 0, // которое сразу же инкрементируется for (char c: text) ++char_count[c]; std::println("{}", char_count); ``` ``` {'6': 1, '+': 1, ' ': 4, '=': 1, '3': 2} ``` ## Джун фильтрует вектор Что выведет этот код? В случае ошибки компиляции напишите `err`, а в случае неопределённого поведения — `ub`. {.task_text} Считайте, что класс `Session` и функция `get_sessions()` реализованы в проекте. В вектор `sessions` попадает 5 сессий, 3 из которых активны. {.task_text} ```cpp {.example_for_playground .example_for_playground_005} std::vector<Session> sessions = get_sessions(); for (auto it = sessions.begin(); it != sessions.end(); ++it) { if (!it->is_active()) sessions.erase(it); } std::println("{}", sessions.size()); ``` ```consoleoutput {.task_source #cpp_chapter_0083_task_0050} ``` После первого же вызова метода `erase()` все последующие итераторы становятся невалидными, так как элементы в памяти сдвигаются. Обращение к элементу, на который указывает невалидный итератор, является неопределённым поведением. **Темы, затронутые в задаче:** [инвалидация итераторов.](/courses/cpp/chapters/cpp_chapter_0062/#block-invalidation) {.task_hint} ```cpp {.task_answer} ub ``` Многие новички в C++ пытаются фильтровать контейнер, организовав цикл с итераторами и вызывая для них метод `erase()`. Это приводит к тому, что элемент, на который указывает итератор, удаляется. А все последующие за ним элементы — смещаются. На выходе имеем [невалидный итератор,](/courses/cpp/chapters/cpp_chapter_0062/#block-invalidation) обращение по которому приведет к UB. Интересует, конечно, не только факт наличия UB в коде, но и то, как такой код исправить. Миддл написал бы так: ```cpp {.example_for_playground .example_for_playground_006} for (auto it = sessions.begin(); it != sessions.end(); ) { if (it->is_active()) // Инкрементируем it, ++it; // только если ничего не удаляли else it = sessions.erase(it); // Обновляем it } ``` В этом коде инкремент итератора происходит, если на текущем шаге цикла элемент не удалён. При удалении же итератор обновляется значением, которое [возвращает](https://en.cppreference.com/w/cpp/container/vector/erase) метод `erase()`. Синьор скорее всего предпочёл бы циклу алгоритм стандартной библиотеки: ```cpp {.example_for_playground .example_for_playground_007} // Принимает ссылку на контейнер и предикат std::erase_if(sessions, needs_removal); ``` Функция [std::erase_if()](https://en.cppreference.com/w/cpp/container/vector/erase2) удаляет элементы контейнера, для которых [предикат](/courses/cpp/chapters/cpp_chapter_0056/#block-predicate) вернёт `true`. Предикат `needs_removal()` мог бы выглядеть так: ```cpp bool needs_removal(Session s) { return !s.is_active(); } ``` ## У меня std::remove() сломался Что выведет этот код? {.task_text} ```cpp {.example_for_playground .example_for_playground_008} std::string args = "-j2 -g"; auto it = std::remove(args.begin(), args.end(), '-'); std::println("{}", std::distance(it, args.end())); ``` ```consoleoutput {.task_source #cpp_chapter_0083_task_0060} ``` Алгоритм [std::remove()](https://en.cppreference.com/w/cpp/algorithm/remove.html) перегруппировывает элементы в диапазоне, сохраняя их относительный порядок. Но он их не удаляет! **Темы, затронутые в задаче:** [алгоритмы для удаления элементов,](/courses/cpp/chapters/cpp_chapter_0082/#block-removal) [алгоритм std::distance().](/courses/cpp/chapters/cpp_chapter_0061/#block-distance) {.task_hint} ```cpp {.task_answer} 2 ``` Алгоритм [std::remove()](https://en.cppreference.com/w/cpp/algorithm/remove.html) проходит по диапазону и сдвигает элементы, которые не надо удалять, в начало. Их относительный порядок сохраняется. Этот алгоритм возвращает итератор на получившийся диапазон. Элементы за его концом остаются в корректном состоянии, но их значения не определены. Размер контейнера при этом не меняется. Поэтому расстояние от итератора `it` до конца строки равно 2: именно 2 символа `'-'` было сдвинуто в конец. Чтобы удалить элементы по-настоящему, нужно вспомнить про [идиому erase-remove:](/courses/cpp/chapters/cpp_chapter_0082/#block-erase-remove) ```cpp {.example_for_playground .example_for_playground_009} std::string args = "-j2 -g"; args.erase(std::remove(args.begin(), args.end(), '-'), args.end()); std::println("{}", args); ``` ``` j2 g ``` ## Да кому нужны эти ваши требования к компараторам Что выведет этот код? В случае ошибки компиляции напишите `err`, а в случае неопределённого поведения — `ub`. {.task_text} ```cpp {.example_for_playground} import std; bool f(int a, int b) { return a >= b; } int main() { std::vector<int> diffs = {8, 1, 8, 3, 8}; std::sort(diffs.begin(), diffs.end(), f); for (int val : diffs) std::println("{} ", val); } ``` ```consoleoutput {.task_source #cpp_chapter_0083_task_0070} ``` В функции `f()` нарушен строгий частичный порядок. **Темы, затронутые в задаче:** [требования к компараторам.](/courses/cpp/chapters/cpp_chapter_0082/#block-comparator-requirements) {.task_hint} ```cpp {.task_answer} ub ``` В этом коде предпринята попытка сортировать числа с проверкой пар на «больше или равно» в надежде получить отсортированный вектор: `8, 8, 8, 3, 1`. Но эта нестрогая проверка нарушает [аксиому антисимметричности.](/courses/cpp/chapters/cpp_chapter_0082/#block-comparator-requirements) Для нашего компаратора `f()` она выглядит так: если `f(x, y)`, то `!f(y, x)`. А функция `f()` для одинаковых чисел `a` и `b` всегда вернёт `true` вне зависимости от того, в каком порядке они переданы. Нарушение этой аксиомы в компараторе, переданном алгоритму стандартной библиотеки — это UB. Чтобы исправить это, достаточно заменить проверку внутри компаратора на более строгую: `a > b`. ## ...Но есть нюанс Какой способ получения итератора на элемент эффективнее — через функцию `std::lower_bound()` или одноимённый метод? Введите соответственно `1` или `2`. Либо `3`, если считаете, что способы примерно одинаковы. {.task_text} ```cpp {.example_for_playground .example_for_playground_010} std::set<int> numbers; for (int i = 0; i <= 10000001; ++i) numbers.insert(i); const int x = 10000000; auto it_f = std::lower_bound(numbers.begin(), numbers.end(), x); // 1 auto it_m = numbers.lower_bound(x); // 2 ``` ```consoleoutput {.task_source #cpp_chapter_0083_task_0080} ``` Вспомните, почему у многих контейнеров есть методы, имена которых совпадают с именами алгоритмов стандартной библиотеки. **Темы, затронутые в задаче:** [класс std::set;](/courses/cpp/chapters/cpp_chapter_0073/#block-set) [алгоритмы для поиска в упорядоченном диапазоне;](/courses/cpp/chapters/cpp_chapter_0081/#block-bounds) [когда использовать алгоритмы, а когда — методы класса.](/courses/cpp/chapters/cpp_chapter_0082/#block-algo) {.task_hint} ```cpp {.task_answer} 2 ``` Контейнер `std::set` хранит _упорядоченное_ множество уникальных ключей. А `lower_bound()` как раз нужен для поиска в отсортированном диапазоне: он возвращает итератор на первое значение, _не меньшее_ `x`. Для решения этой задачи отлично подходит алгоритм бинарного поиска. На каждой его итерации рассматриваемый диапазон сокращается в 2 раза: поиск работает за `O(log(N))`. Однако алгоритм `std::lower_bound()` справится гораздо медленнее: за `O(N)`. Почему? В него передаются только итераторы на диапазон. Итераторы по `std::set` относятся к [категории](/courses/cpp/chapters/cpp_chapter_0061/#block-iterator-categories) двунаправленных (bidirectional): с их помощью можно перемещаться по контейнеру в любом направлении. Но они не являются итераторами произвольного доступа (random access): через них нельзя переместиться на произвольный элемент, как в случае с итераторами на `std::vector`. А для бинарного поиска это необходимо. Поэтому функции `std::lower_bound()` не остается ничего другого, кроме как последовательно перебирать элементы за `O(N)`. Зато метод `lower_bound()` имеет полное представление о внутреннем устройстве контейнера, и решает задачу за `O(log(N))`. Для любопытных: откройте эту задачу в песочнице по кнопке с зонтиком и сравните время работы метода и функции. ## Момент истины Проверим, насколько хорошо вы разобрались в контейнерах. Запомнить их названия и ключевые отличия — не самоцель. Самое важное — уметь подбирать контейнер под конкретную задачу. Вы делаете систему для обработки заказов. Заказы приходят часто, а их обработка устроена по принципу «первым пришёл — первым ушёл». Количество накапливаемых заказов заранее неизвестно. После обработки заказ удаляется. {.task_text} Какой контейнер или адаптер лучше всего подойдёт для этой задачи? Если выберете адаптер, то через пробел укажите, поверх какого контейнера. ```consoleoutput {.task_source #cpp_chapter_0083_task_0090} ``` «Первым пришёл — первым ушёл» (FIFO) наталкивает на мысль об очереди, а значит, подойдёт соответствующий адаптер. Осталось подобрать, поверх какого контейнера его организовать. Нужен контейнер, в котором эффективно реализованы вставка и удаление с обоих концов. **Темы, затронутые в задаче:** [класс std::deque;](/courses/cpp/chapters/cpp_chapter_0072/#block-deque) [адаптер std::queue;](/courses/cpp/chapters/cpp_chapter_0075/#block-queue) [алгоритмическая сложность работы с контейнерами и адаптерами.](/courses/cpp/chapters/cpp_chapter_0075/#block-algo) {.task_hint} ```cpp {.task_answer} std::queue std::deque ``` В целом алгоритм выбора контейнера под задачу можно описать так: 1. Определите, какие операции (вставка, поиск, удаление) будут выполняться чаще других. Есть ли особые требования? Например, быстрый поиск, обязательная упорядоченность или уникальность элементов. Уже на этом шаге вы значительно сузите выбор. 2. Если после первого шага выбор остаётся между несколькими контейнерами, предпочитайте тот, интерфейс которого чётче выражает намерение. Например, в задаче выше мы могли бы остановиться на `std::deque`. Но интерфейс `std::queue` более ограничен, а значит, подчеркивает намерение работать только с началом и концом очереди и не обращаться к элементам посередине. 3. Если специфичных требований к контейнеру нет, используйте `std::vector`. Он дружелюбен к кешу процессора и поддерживает большое количество операций. Он заслуженно считается выбором по умолчанию. ---------- ## Что дальше В стандартной библиотеке [собраны](https://cppreference.com/w/cpp/algorithm.html) десятки алгоритмов на все случаи жизни. Постоянно практикуйтесь в них. Это сделает ваш код более выразительным и эффективным. А замотивирует вас доклад Михаила Матросова [«Повседневный С++»,](https://www.youtube.com/watch?v=LuaNbkRPGRo) в котором наглядно показано, что правильный выбор алгоритмов кратно сокращает объём кода. Докладу почти 10 лет, но он по-прежнему насущный. Практикуйтесь! Решайте задачи на [LeetCode,](https://leetcode.com/) [HackerRank,](https://www.hackerrank.com/) [Codewars,](https://www.codewars.com/) [Codeforces](https://codeforces.com/) и других площадках с интересными алгоритмическими заданиями. Это лучший способ набить руку в использовании итераторов, контейнеров и алгоритмов.