# Глава 8.2. Модифицирующие алгоритмы В этой главе вы научитесь сортировать, копировать и удалять элементы диапазонов. ## Сортировка Функция [std::is_sorted()](https://en.cppreference.com/w/cpp/algorithm/is_sorted) проверяет, отсортирован ли диапазон. А [std::sort()](https://en.cppreference.com/w/cpp/algorithm/sort) сортирует его. Обе функции работают с сортировкой по возрастанию. Для строк это называется [лексикографическим порядком.](https://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D0%BA%D1%81%D0%B8%D0%BA%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D0%BA) Для сортировки по возрастанию используется сравнение оператором `<`. ```cpp {.example_for_playground .example_for_playground_009} std::deque<double> d = {3.1, 8.0, 56.5}; std::println("{}", std::is_sorted(d.begin(), d.end())); d.push_front(100.0); std::println("{}", std::is_sorted(d.begin(), d.end())); std::sort(d.begin(), d.end()); std::println("{}", d); ``` ``` true false [3.1, 8, 56.5, 100] ``` Что нужно сделать, чтобы сортировать по другому условию, вы узнаете чуть позже. Напишите функцию `contains_duplicate()`. Она принимает вектор целых чисел и возвращает `true`, если в нем есть дубликаты. {.task_text} Например, для вектора `[3, 2, 3, 1]` функция вернет `true`, а для `[9, 2]` — `false`. {.task_text} Функция должна отработать _быстрее,_ чем за квадратичное время `O(N^2)`. Исходный массив можно изменять. {.task_text} ```cpp {.task_source #cpp_chapter_0082_task_0060} bool contains_duplicate(std::vector<int> v) { } ``` Сначала отсортируйте вектор. Сложность сортировки — `O(N * log(N))` Затем пройдитесь по вектору, чтобы сравнить соседние элементы за `O(N)`. {.task_hint} ```cpp {.task_answer} bool contains_duplicate(std::vector<int> v) { if (v.empty()) return false; std::sort(v.begin(), v.end()); for (std::size_t i = 0; i < v.size() - 1; ++i) { if (v[i] == v[i + 1]) return true; } return false; } ``` ### Как реализована сортировка До C++11 для реализации `std::sort()` подходил алгоритм быстрой сортировки [quicksort](https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0). Но начиная с C++11 стандарт гарантирует для этой функции алгоритмическую сложность `O(N * log(N))`. А Quicksort в худшем случае имеет квадратичную сложность `O(N^2)` и не удовлетворяет этому ограничению. Так какой же алгоритм заложен в `std::sort()`? Зависит от реализации. В некоторых реализациях [используется](https://github.com/gcc-mirror/gcc/blob/releases/gcc-15/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1874) интроспективная сортировка [introsort](https://en.wikipedia.org/wiki/Introsort). Это гибрид из трех способов сортировки. Вначале запускается quicksort. Если глубина рекурсии превышает некий порог, алгоритм переключается на пирамидальную сортировку [heapsort](https://ru.wikipedia.org/wiki/%D0%9F%D0%B8%D1%80%D0%B0%D0%BC%D0%B8%D0%B4%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0). Ближе к концу, когда остаются небольшие интервалы, в игру вступает сортировка вставками [insertion sort](https://en.wikipedia.org/wiki/Insertion_sort). Другие реализации `std::sort()` еще [более сложные](https://danlark.org/2022/04/20/changing-stdsort-at-googles-scale-and-beyond/). Они [включают](https://github.com/llvm-mirror/libcxx/blob/master/include/algorithm#L3899) эвристики и оптимизации в зависимости от длины интервалов и особенностей типа элементов. ### Компараторы Итак, по умолчанию алгоритм сортировки использует оператор `<` для сравнения элементов. Поэтому элементы сортируются по возрастанию. Для сортировки по другому условию у алгоритмов есть перегрузки, принимающие компаратор. **Компаратор** — это функция-предикат от двух параметров. Она возвращает `true`, если первый параметр меньше, чем второй. Чтобы сортировать по убыванию, а не по возрастанию, достаточно передать [std::greater<T>()](https://en.cppreference.com/w/cpp/utility/functional/greater), где `T` — тип элементов диапазона. ```cpp bool is_sorted = std::is_sorted(days.begin(), days.end(), std::greater<DayOfWeek>()); ``` В стандартной библиотеке также реализована функция [std::less<T>()](https://en.cppreference.com/w/cpp/utility/functional/less). ### Требования к компараторам Чтобы сортировать данные по более сложным правилам, приходится писать свой компаратор. Для этого важно помнить требования к компараторам. Они общие для любого языка программирования. Если компаратор нарушает хотя бы одно из требований, то в работе использующего его алгоритма произойдет ошибка. Например, зацикливание, аварийное завершение или получение некорректного результата. Допустим, наш компаратор называется `is_less()`. Для него должны выполняться условия: - [Строгий частичный порядок](https://ru.wikipedia.org/wiki/%D0%9E%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B0#%D0%9E%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F). - `!is_less(x, x)`. Антирефлексивность: значение `x` не может быть меньше самого себя. - Если `is_less(x, y) && is_less(y, z)`, то `is_less(x, z)`. Транзитивность: если `x` меньше `y`, а `y` меньше `z`, то `x` меньше `z`. - Если `is_less(x, y)`, то `!is_less(y, x)`. Антисимметричность. Она следует из двух предыдущих аксиом. - Транзитивность эквивалентности. - Если `!is_less(x, y) && !is_less(y, x)`, то `x` и `y` эквивалентны: с точки зрения компаратора между ними нет разницы. Транзитивность эквивалентности означает, что если `x` эквивалентен `y`, а `y` эквивалентен `z`, то `x` эквивалентен `z`. Если компаратор удовлетворяет строгому частичному порядку и транзитивности эквивалентности, то говорят, что он реализует строгий слабый порядок (strict weak ordering). Стандарт C++ требует, чтобы все передаваемые в алгоритмы компараторы поддерживали строгий слабый порядок. Если это не так, вы получите [UB.](/courses/cpp/chapters/cpp_chapter_0060/#block-ub) При написании собственных компараторов наиболее частая ошибка — это нарушение антисимметричности. Она допущена и в коде предиката `has_higher_priority()`. Он нужен для сортировки товаров в первую очередь по убыванию популярности и во вторую — по убыванию рейтинга. {.task_text} Найдите ошибку в компараторе и исправьте ее. Чтобы посмотреть, как `has_higher_priority()` применяется в коде, откройте эту задачу в плэйграунде. {.task_text} ```cpp {.task_source #cpp_chapter_0082_task_0050} struct Product { int id = 0; int popularity = 0; int rating = 0; }; bool has_higher_priority(Product a, Product b) { if (a.popularity > b.popularity) return true; if (a.rating > b.rating) return true; return false; } ``` Допустим, в функцию переданы два объекта `Product` с полями `popularity=1000, rating=4` и `popularity=100, rating=5`. В зависимости от того, в каком порядке они попадут в функцию, `has_higher_priority()` вернет разный результат! Это означает нарушение аксиомы антисимметричности. Чтобы исправить это, нужно добавить дополнительную проверку для сравнений поля `rating`. Условие `a.rating > b.rating` нужно дополнить: `a.popularity == b.popularity && a.rating > b.rating`. {.task_hint} ```cpp {.task_answer} struct Product { int id = 0; int popularity = 0; int rating = 0; }; bool has_higher_priority(Product a, Product b) { if (a.popularity > b.popularity) return true; if (a.popularity == b.popularity && a.rating > b.rating) return true; return false; } ``` ## Копирование Добавить элементы одного контейнера в конец другого не так просто, как хотелось бы. Например, вектор, в отличие от строк, не поддерживает конкатенацию через оператор `+=`: ```cpp std::string s1 = "prefix"; std::string s2 = " suffix"; s1 += s2; std::println("{}", s1); ``` ``` prefix suffix ``` Вместо простой конкатенации для векторов используется алгоритм [std::copy](https://en.cppreference.com/w/cpp/algorithm/copy). Он принимает итераторы на входной диапазон и итератор на начало выходного диапазона: ```cpp template<class InputIt, class OutputIt> OutputIt copy(InputIt first, InputIt last, OutputIt d_first) { /* Реализация */ } ``` Функция возвращает итератор _за_ последний элемент выходного диапазона. На примере `std::copy()` скажем про важную, но неочевидную особенность работы с алгоритмами. Если алгоритм не предназначен для модификации входного диапазона, но технически это допускает, будьте осторожны. Функция не должна изменять значения внутри входного диапазона или инвалидировать итераторы. Это приведет к UB. В случае с `std::copy()` это происходит, если входной и выходной диапазоны пересекаются: ```cpp std::vector<int> source = {6, 8, 2}; auto it = source.begin() + 1; std::copy(source.begin(), source.end(), it); // UB ``` Поэтому при возникновении сомнений всегда сверяйтесь с документацией алгоритма на [cppreference.](https://en.cppreference.com/w/cpp/algorithm.html) Будьте внимательны: для использования `std::copy()` в выходном диапазоне должно быть не меньшее количество элементов, чем во входном диапазоне. Копирование в диапазон меньшего размера приведет к выходу за его границу. А значит, к [UB.](/courses/cpp/chapters/cpp_chapter_0060/#block-ub) Например, UB есть в этом коде. Мы копируем 3 элемента из `source` по итератору _за_ последний элемент `destination`: ```cpp {.example_for_playground .example_for_playground_010} std::vector<int> source = {6, 8, 2}; std::vector<int> destination = {1, 1, 1}; std::copy(source.begin(), source.end(), destination.end()); // UB ``` Чтобы избавиться от UB, заранее обеспечьте выходной диапазон необходимого размера. Сделаем это с помощью метода вектора [resize()](https://en.cppreference.com/w/cpp/container/vector/resize): ```cpp {.example_for_playground .example_for_playground_011} std::vector<int> source = {6, 8, 2}; std::vector<int> destination = {1, 1, 1}; destination.resize(destination.size() + source.size()); std::copy(source.begin(), source.end(), destination.end() - source.size()); std::println("{}", destination); ``` ``` [1, 1, 1, 6, 8, 2] ``` Удобен ли такой способ? Он способствует ошибкам при определении длин диапазонов. Из-за них вы получите UB либо лишние элементы в конце выходного диапазона. ### Итераторы-адаптеры Если производительность при копировании не критична, вместо связки `resize()` и `std::copy()` применяется альтернативный подход. В `std::copy()` вместо итератора на выходной диапазон передается специальная функция, которая возвращает итератор-адаптер. **Итератор-адаптер** — это не настоящий итератор, а класс, ведущий себя как итератор. Так, [std::back_insert_iterator](https://en.cppreference.com/w/cpp/iterator/back_insert_iterator) умеет только добавлять элементы в конец контейнера. Он вызывает метод контейнера `push_back()`, когда к элементу, на который указывает итератор-адаптер, присваивается значение оператором `=`. Чтобы получить этот итератор-адаптер для контейнера, предусмотрена функция [std::back_inserter](https://en.cppreference.com/w/cpp/iterator/back_inserter). Она принимает контейнер и возвращает `std::back_insert_iterator`. ```cpp {.example_for_playground .example_for_playground_012} std::vector<int> source = {6, 8, 2}; std::vector<int> destination = {1, 1, 1}; std::copy(source.begin(), source.end(), std::back_inserter(destination)); std::println("{}", destination); ``` ``` [1, 1, 1, 6, 8, 2] ``` Для вставки в начало контейнера есть итератор-адаптер [std::front_insert_iterator](https://en.cppreference.com/w/cpp/iterator/front_insert_iterator). Под капотом он вызывает метод `push_front()` контейнера. Чтобы получить этот итератор-адаптер, есть функция [std::front_inserter](https://en.cppreference.com/w/cpp/iterator/front_inserter). ```cpp {.example_for_playground .example_for_playground_013} std::list<int> source = {6, 8, 2}; std::list<int> destination = {1, 1, 1}; std::copy(source.begin(), source.end(), std::front_inserter(destination)); std::println("{}", destination); ``` ``` [2, 8, 6, 1, 1, 1] ``` Для вставки на произвольную позицию используется итератор-адаптер [std::insert_iterator](https://en.cppreference.com/w/cpp/iterator/insert_iterator), вызывающий метод контейнера `insert()`. Чтобы получить его для контейнера, нужно вызвать функцию [std::inserter](https://en.cppreference.com/w/cpp/iterator/inserter). Ознакомьтесь с ее документацией и потренируйтесь использовать ее в задаче. Необходимо реализовать функцию `insert_ad()`. Она принимает аудиопоток `stream`, метку для вставки рекламы `tag` и аудиопоток рекламы `ad` (advertisement). Функция возвращает аудиопоток со вставленной рекламой. {.task_text} В аудиопотоке нужно найти все парные метки, то есть последовательность `tag`, идущую два раза подряд. Рекламу нужно вставить между этими метками. Удалять их из потока не надо. Считаем, что аудиопоток корректный: если он содержит метки, то они обязательно парные. {.task_text} Пример: {.task_text} - Аудиопоток: `[0x2a, 0x17, 0x14, 0x17, 0x01, 0x01, 0x01, 0x01, 0x55, 0x7c, 0x20]`. - Метка: `[0x01, 0x01]`. - Реклама: `[0x0b, 0x0a, 0x0d]`. - Результат после вставки рекламы: `[0x2a, 0x17, 0x14, 0x17, 0x01, 0x01, 0x0b, 0x0a, 0x0d, 0x01, 0x01, 0x55, 0x7c, 0x20]`. ```cpp {.task_source #cpp_chapter_0082_task_0070} std::vector<char> insert_ad( std::vector<char> stream, // аудиопоток std::vector<char> tag, // метка для вставки рекламы std::vector<char> ad) // реклама { } ``` Для поиска последовательности внутри другой последовательности воспользуйтесь [std::search()](https://en.cppreference.com/w/cpp/algorithm/search). Для определения смещения при последующем поиске пригодится [std::distance()](https://en.cppreference.com/w/cpp/iterator/distance). Для копирования будет нужна связка [std::copy()](https://en.cppreference.com/w/cpp/algorithm/copy) и [std::inserter()](https://en.cppreference.com/w/cpp/iterator/inserter). {.task_hint} ```cpp {.task_answer} std::vector<char> insert_ad( std::vector<char> stream, // аудиопоток std::vector<char> tag, // метка для вставки рекламы std::vector<char> ad) // реклама { std::size_t offset = 0; while(true) { auto it = std::search(stream.begin() + offset, stream.end(), tag.begin(), tag.end()); if (it == stream.end()) break; it += tag.size(); offset += std::distance(stream.begin(), it); std::copy(ad.begin(), ad.end(), std::inserter(stream, it)); offset += ad.size() + tag.size(); } return stream; } ``` ## Удаление Для удаления элементов из диапазона предназначены алгоритмы [std::remove и std::remove_if](https://en.cppreference.com/w/cpp/algorithm/remove). Но будьте бдительны: они ничего не удаляют. ```cpp {.example_for_playground .example_for_playground_014} std::vector<int> v = {1, 2, 3, 3, 2, 1}; std::println("vector={}", v); auto it = std::remove(v.begin(), v.end(), 2); std::println("range without removed elements ends at {}'th element from 0:\n{}", std::distance(v.begin(), it - 1), v); ``` ``` vector=[1, 2, 3, 3, 2, 1] range without removed elements ends at 3'th element from 0: [1, 3, 3, 1, 2, 1] ``` Эти функции лишь _сдвигают_ в начало диапазона все элементы, которые не нужно удалять. И возвращают итератор на конец получившегося диапазона. Практически всегда следующий за этим итератором хвост из ненужных элементов требуется стереть. Он может содержать любой мусор. Для этого вызывается метод контейнера `erase()` либо функция стандартной библиотеки [std::erase()](https://en.cppreference.com/w/cpp/container/vector/erase2), появившаяся в C++20. Как считаете, почему функция `std::remove()` не удаляет элементы по-настоящему? Она, как и любой алгоритм стандартной библиотеки, работает с итераторами, а не с контейнером напрямую. Итератор — это объект, который указывает на конкретный элемент контейнера. Ему известно расположение элемента в памяти и его тип. Поэтому единственное, что можно сделать с элементом через итератор — это изменить значение элемента. Чтобы передвинуть элемент или поменять элементы местами, нужны два итератора: изменение порядка элементов достигается за счет обмена значениями пары итераторов. А вот для _удаления_ элемента требуется доступ непосредственно к контейнеру. Поэтому алгоритм технически не может удалить что-то из контейнера. ### Идиома erase-remove Использование `std::remove()` и `erase()` в связке известно как [идиома erase-remove.](https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom) ```cpp {.example_for_playground .example_for_playground_015} std::vector<int> v = {1, 2, 3, 3, 2, 1}; auto it = std::remove(v.begin(), v.end(), 2); v.erase(it, v.end()); std::println("vector={}", v); ``` ``` vector=[1, 3, 3, 1] ``` Чаще всего вызовы `std::remove()` и `erase()` записываются в одну строку: ```cpp std::vector<int> v = {1, 2, 3, 3, 2, 1}; v.erase(std::remove(v.begin(), v.end(), 2), v.end()); std::println("vector={}", v); ``` ``` vector=[1, 3, 3, 1] ``` ## Когда использовать алгоритмы, а когда — методы класса? Если вы проходите этот курс достаточно внимательно, то наверняка обратили внимание на интересную деталь. У классов ассоциативных контейнеров есть метод `find()`. Зачем он нужен, если в стандартной библиотеке существует алгоритм с таким же названием? Функции стандартной библиотеки ничего не знают об устройстве контейнеров. Они реализуют обобщенные алгоритмы, работающие с итераторами. А методы класса, напротив, обладают полной информацией о его организации. За счет этого они эффективнее: ```cpp {.example_for_playground .example_for_playground_017} std::unordered_map<int, std::string> warning_codes = { {52, "API is deprecated"}, {103, "API key is not provided"}, // ... }; // Метод применяет хеш-функцию к ключу и // сразу получает элемент хеш-таблицы. // Это O(1) в среднем и O(N) в худшем случае. auto it_m = warning_codes.find(52); // Функция просто перебирает все элементы // от begin() до end() не включительно. // Это O(N). auto it_f = std::find(warning_codes.begin(), warning_codes.end(), 52); ``` Метод `find()` ассоциативного контейнера отработает быстрее, чем алгоритм `std::find()`. Второй пример пересекающейся функциональности у алгоритма и метода — это удаление элементов. У списка `std::list` есть методы [remove() и remove_if()](https://en.cppreference.com/w/cpp/container/list/remove). Алгоритмы стандартной библиотеки с этими названиями применительно к спискам неэффективны. А методы класса имеют возможность _действительно_ удалить элементы списка, причем быстро. Когда выбирать алгоритмы, а когда — методы класса? - Если в приоритете скорость, то используйте методы. - А если вы пишете обобщенный код, который должен работать с произвольными контейнерами, выбирайте функции стандартной библиотеки. ## Оптимальны ли алгоритмы и контейнеры Классы и функции стандартной библиотеки разрабатываются с упором на три плохо совместимых качества: - Универсальность. - Эффективность. - Обратная совместимость. Это значит, что _в общем случае_ они показывают хорошие результаты. И уж точно превосходят простые самописные решения. Но [внимание к обратной совместимости](/courses/cpp/chapters/cpp_chapter_0010/#block-backward-compatibility) бьет по эффективности. То есть даже для усредненного сценария возможна более удачная реализация многих контейнеров и алгоритмов. Возникает вопрос: в каких случаях стоит подбирать им замену? Как всегда, руководствуйтесь здравым смыслом и фактами. По умолчанию выбирайте стандартную библиотеку. Это не требует от вас лишних действий. И даже при появлении проблем со скоростью или потреблением памяти не спешите мигрировать на стороннюю библиотеку. Принимайте решение, опираясь на профилирование производительности, бенчмарки и анализ потребления памяти. _В большинстве случаев_ стандартная библиотека оказывается ни при чем, а проблемы лежат в совершенно другой плоскости. Например, упираются в неудачную архитектуру или синхронную обработку данных там, где нужна асинхронность. Если же контейнер или алгоритм действительно стал бутылочным горлышком проекта, поэкспериментируйте с альтернативами: [Abseil от Google](https://github.com/abseil/abseil-cpp), [Folly от Meta](https://github.com/facebook/folly), уже [знакомым](/courses/cpp/chapters/cpp_chapter_0010/#block-boost) вам [Boost](https://www.boost.org/) и другими библиотеками с открытым исходным кодом. ## Домашнее задание Самостоятельно разберитесь, в чем разница между алгоритмами [std::for_each()](https://en.cppreference.com/w/cpp/algorithm/for_each) и [std::transform()](https://en.cppreference.com/w/cpp/algorithm/transform). ---------- ## Резюме - У некоторых контейнеров есть методы с такими же названиями, как у алгоритмов стандартной библиотеки. Они более эффективны. - Для использования в некоторых алгоритмах пригодятся итераторы-адаптеры и возвращающие их функции. - Идиома erase-remove заключается в применении алгоритма `std::remove()` или `std::remove_if()` с последующим вызовом метода `erase()` контейнера. - В алгоритмах сортировки используются компараторы. Компаратор — это функция-предикат от двух параметров, возвращающая `true`, если первый параметр меньше, чем второй.