Алгоритмы диапазонов C++20 — сортировка, множества, обновления C++23 и прочее

Эта статья — третья и последняя в мини-серии об алгоритмах диапазонов. Мы рассмотрим некоторые алгоритмы сортировки, поиска и другие, а также познакомимся с готовящимися крутыми улучшениями этих алгоритмов в версии C++23. Поехали! Подробности — к старту курса по разработке на С++.

Прежде чем мы начнём

Ключевые наблюдения для алгоритмов std::ranges:

Алгоритмы диапазонов определяются в заголовке <algorithm>, а инфраструктура диапазонов и основные типы определяются в заголовке <ranges>.
Существует как минимум две перегрузки алгоритмов диапазона: с парой итераторов и перегрузка с одним аргументом диапазона.
Версия, которая возвращает поддиапазон или итератор и принимает диапазон, возвращает заимствованный диапазон или заимствованный итератор. Это помогает обнаруживать итераторы для временных диапазонов.
Версии диапазона имеют проекции, что обеспечивает большую гибкость; например, вы можете выполнить сортировку по некоторым выбранным элементам или выполнить дополнительные преобразования перед сравнением.
В версии с диапазонами нет опции параллельного выполнения (вы не можете передать политику std::execution).
Алгоритмы диапазонов, как и стандартные алгоритмы C++20, также являются constexpr.
Начиная с версии C++20, не существует алгоритмов числовых диапазонов, соответствующих заголовку <numeric>.

Ниже вы можете найти примеры, демонстрирующие стандартный алгоритм и альтернативную версию с диапазонами. В них мы иллюстрируем некоторые основные концепции, стараясь не использовать расширенную композицию диапазонов или представления. Мы пойдём в порядке, указанном в cppreference/algorithms.

В этой части рассмотрим алгоритмы сортировки, разбиения на разделы, бинарный поиск и некоторые другие функции.

Это третья статья об алгоритмах диапазонов. Смотрите также:

первая статья: «Алгоритмы диапазонов C++20 — 7 немодифицирующих операций»;

вторая статья: «Алгоритмы диапазонов C++20 — 11 модифицирующих операций»;

Разбиение на разделы и сортировка

`sort` и `is_sorted`

Алгоритм сортировки часто используют для объявления диапазонов. Если у вас есть контейнер, то благодаря диапазонам вы можете написать:

std::ranges::sort(myContainer);

Вот пример для лучшего понимания:

#include <iostream> #include <algorithm> #include <ranges> #include <vector>  struct Product {     std::string name;     double value { 0.0 }; };  void print(std::string_view intro, const std::vector<Product>& container) {     std::cout << intro << '\n';     for (const auto &elem : container)         std::cout << elem.name << ", " << elem.value << '\n'; }  int main() {     const std::vector<Product> prods {         { "box", 10.0 }, {"tv", 100.0}, {"ball", 30.0},         { "car", 1000.0 }, {"toy", 40.0}, {"cake", 15.0},         { "book", 45.0}, {"pc game", 35.0}, {"wine", 25}     };      print("input", prods);      // the standard version:     std::vector<Product> copy = prods;        std::sort(begin(copy), end(copy), [](const Product& a, const Product& b)         { return a.name < b.name; }     );      print("after sorting by name", copy);      // the ranges version:     copy = prods;        std::ranges::sort(copy, {}, &Product::name);         print("after sorting by name", copy);                std::ranges::sort(copy, {}, &Product::value);         print("after sorting by value", copy);          auto sorted = std::ranges::is_sorted(copy, {}, &Product::value);     std::cout << "is sorted by value: " << sorted << '\n'; }

Запустить @Compiler Explorer

Во многих реализациях используется интросортировка (см. Википедию). Это гибридное решение, обычно с быстрой сортировкой/сортировкой кучей, а затем сортировкой вставками для небольших (под)диапазонов.

Другие версии алгоритмов сортировки:

partial_sort — сортирует первые N элементов диапазона.
stable_sort — порядок эквивалентных элементов гарантированно сохраняется.

Как видите, в версии с диапазонами легко передать проекцию и отсортировать по заданной части элемента. В обычной версии нужно отдельное лямбда-выражение…

Подробнее: ranges::sort @Cppreference.

`partition`

Разбиение — неотъемлемая часть быстрой сортировки. Для данного предиката операция перемещает элементы, соответствующие предикату, в первую часть контейнера, а не соответствующие — во вторую. Иногда можно разделить контейнер, а не выполнять полную операцию сортировки:

#include <iostream> #include <algorithm> #include <ranges> #include <vector>  void print(std::string_view intro, const std::vector<auto>& container) {     std::cout << intro << '\n';     for (const auto &elem : container)         std::cout << elem << ", ";     std::cout << '\n'; }  int main() {     const std::vector vec { 11, 2, 3, 9, 5, 4, 3, 8, 4, 1, 11, 12, 10, 4};      print("input", vec);      // the standard version:     auto copy = vec;        auto it = std::partition(begin(copy), end(copy), [](int a)         { return a < 7; }     );      print("partition till 7", copy);     std::cout << "pivot at " << std::distance(begin(copy), it) << '\n';      // ranges version:     copy = vec;        auto sub = std::ranges::partition(copy, [](int a)         { return a < 7; }     );      print("partition till 7", copy);     std::cout << "pivot at " << std::distance(begin(copy), sub.begin()) << '\n'; }

Запустить @Compiler Explorer

Вывод:

input 11, 2, 3, 9, 5, 4, 3, 8, 4, 1, 11, 12, 10, 4, partition till 7 4, 2, 3, 1, 5, 4, 3, 4, 8, 9, 11, 12, 10, 11, pivot at 8 partition till 7 4, 2, 3, 1, 5, 4, 3, 4, 8, 9, 11, 12, 10, 11, pivot at 8

Как видите, мы легко можем разделить контейнер на две группы: первая часть содержит элементы меньше 7, а вторая часть — элементы >= 7. Относительный порядок между элементами может быть изменен (для сохранения этого порядка нужно использовать stable_partition).

Интерфейс для partition относительно прост. Версия алгоритма дополнительно принимает проекцию, но в примере она не использовалась. Отличие состоит в том, что ranges::partition возвращает поддиапазон, а не итератор (как в версии std::).

Подробнее об алгоритмах: ranges::is_partitioned и ranges::partition @C++Reference.

Операции бинарного поиска

Если контейнер уже отсортирован, можно выполнять операции логарифмического бинарного поиска.

`binary_search`

#include <iostream> #include <algorithm> #include <ranges> #include <vector> #include <numeric>  void print(std::string_view intro, const auto& container) {     std::cout << intro << '\n';     for (const auto &elem : container)         std::cout << elem << ", ";     std::cout << '\n'; }  int main() {     std::vector<int> vec(100, 0);     std::iota(begin(vec), end(vec), 0);      print("first ten elements of input", vec | std::views::take(10));      // the standard version:     auto copy = vec;        auto found = std::binary_search(begin(copy), end(copy), 13);     std::cout << "found 13: " << found << '\n';      // ranges version:     copy = vec;        found = std::ranges::binary_search(copy, 13);     std::cout << "found 13: " << found << '\n'; }

Запустить @Compiler Explorer

Читать подробнее:ranges::binary_search @C++Reference.

Кроме того, можно использовать связанные алгоритмы:

std::ranges::lower_bound — cppreference.com возвращает итератор к первому элементу не меньше заданного значения;
std::ranges::upper_bound — cppreference.com — возвращает итератор к первому элементу больше заданного значения;

Операции с множествами

В библиотеке есть много функций, связанных с множествами, вот некоторые из них:

ranges::merge — объединяет два отсортированных диапазона
ranges::inplace_merge — объединяет два упорядоченных диапазона in-place
ranges::includes — возвращает true, если одна отсортированная последовательность является подпоследовательностью другой отсортированной последовательности
ranges::set_difference — вычисляет разницу между двумя множествами
ranges::set_intersection — вычисляет пересечение двух множеств
ranges::set_symmetric_difference — вычисляет симметричную разность двух множеств
ranges::set_union — вычисляет объединение двух множеств

Рассмотрим один пример с includes:

`includes`

Возвращает true, если отсортированный диапазон является подпоследовательностью другого отсортированного диапазона.

#include <iostream> #include <algorithm> #include <ranges> #include <vector> #include <string>  struct Product {     std::string name;     double value { 0.0 }; };  void print(std::string_view intro, const std::vector<Product>& container) {     std::cout << intro << '\n';     for (const auto &elem : container)         std::cout << elem.name << ", " << elem.value << '\n'; }  int main() {     std::vector<Product> prods {         { "box", 10.0 }, {"tv", 100.0}, {"ball", 30.0},         { "car", 1000.0 }, {"toy", 40.0}, {"cake", 15.0},         { "book", 45.0}, {"pc game", 35.0}, {"wine", 25}     };     std::vector<Product> vecToCheck {         {"ball", 30.0}, { "box", 10.0 }, {"wine", 25}     };     std::ranges::sort(prods, {}, &Product::name);     std::vector<std::string> namesToCheck {"ball", "box", "wine"};      print("input", prods);      // the standard version:           auto ret = std::includes(begin(prods), end(prods),                             begin(vecToCheck), end(vecToCheck),                             [](const Product& a, const Product& b)         { return a.name < b.name; }     );     std::cout << "contains the name set: " << ret << '\n';      // the ranges version:     ret = std::ranges::includes(prods, namesToCheck, {}, &Product::name);     std::cout << "contains the name set: " << ret << '\n'; }

Запустить @Compiler Explorer

Версия с диапазонами проще и предлагает способ проверки различных контейнеров. При подходе std:: итератор необходимо разыменовать, а затем неявно преобразовать в оба типа элементов входного контейнера.

Дополнительную информацию см.: std::includes @cppreference.com.

Прочее

`max_element`

Поиск наибольшего элемента в контейнере (без сортировки):

#include <iostream> #include <random> #include <iterator> #include <algorithm> #include <ranges>  struct Product {     std::string name_;     double value_ { 0.0 }; };  int main() {     const std::vector<Product> prods {         { "box", 10.0 }, {"tv", 100.0}, {"ball", 30.0},         { "car", 1000.0 }, {"toy", 40.0}, {"cake", 15.0},         { "book", 45.0}, {"PC game", 35.0}, {"wine", 25}     };      // the standard version:        auto res = std::max_element(begin(prods), end(prods),                 [](const Product& a, const Product& b) {                     return a.value_ < b.value_;                 });      if (res != end(prods)) {         const auto pos = std::distance(begin(prods), res);         std::cout << "std::max_element at pos " << pos                   << ", val " << res->value_ << '\n';     }      // the ranges version:     auto it = std::ranges::max_element(prods, {}, &Product::value_);     if (it != end(prods)) {         const auto pos = std::distance(begin(prods), it);         std::cout << "std::max_element at pos " << pos                   << ", val " << res->value_ << '\n';     } }

Запустить @Compiler Explorer

`equal`

#include <iostream> #include <random> #include <iterator> #include <algorithm> #include <ranges>  struct Product {     std::string name;     double value { 0.0 }; };  int main() {     const std::vector<Product> prods {         { "box", 10.0 }, {"tv", 100.0}, {"ball", 30.0},         { "car", 1000.0 }, {"toy", 40.0}, {"cake", 15.0},     };      const std::vector<Product> moreProds {         { "box", 11.0 }, {"tv", 120.0}, {"ball", 30.0},         { "car", 10.0 }, {"toy", 39.0}, {"cake", 15.0}     };      // the standard version:        auto res = std::equal(begin(prods), end(prods),                           begin(moreProds), end(moreProds),                 [](const Product& a, const Product& b) {                     return a.name == b.name;                 });      std::cout << "equal: " << res << '\n';      // the ranges version:     res = std::ranges::equal(prods, moreProds, {}, &Product::name, &Product::name);     std::cout << "equal: " << res << '\n'; }

Запустить @Compiler Explorer

Подробнее см.: ranges::equal @C++Reference.

Еще больше

Мой список алгоритмов не полон. Почти у всех стандартных алгоритмов есть альтернатива std::ranges::. Взгляните на следующие интересные, не упомянутые мной алгоритмы:

Операции с кучей:

ranges::is_heap
ranges::is_heap_until
ranges::make_heap
ranges::push_heap
ranges::pop_heap
ranges::sort_heap

Перестановки:

ranges::is_permutation
ranges::next_permutation
ranges::prev_permutation

Алгоритмы неинициализированной памяти:

ranges::uninitialized_copy
ranges::uninitialized_copy_n
ranges::uninitialized_fill
ranges::uninitialized_fill_n
ranges::uninitialized_move
ranges::uninitialized_move_n
ranges::uninitialized_default_construct
ranges::uninitialized_default_construct_n
ranges::uninitialized_value_construct
ranges::uninitialized_value_construct_n
ranges::destroy
ranges::destroy_n
ranges::destroy_at
ranges::construct_at

Numeric

С версии C++20 у нас есть большинство соответствующих алгоритмов диапазонов из заголовка <algorithm>, но отсутствует заголовок <numeric>.

Скоро в C++23

Спецификация C++23 почти закончена и находится в режиме feature-freeze. На момент написания статьи мне известны следующие алгоритмы, которые появятся в новой версии C++:

ranges::starts_with и ranges::ends_with (по состоянию на июнь 2022 г. доступно в компиляторе MSVC)
ranges::contains (P2302)
ranges::shift_left и ranges::shift_right,
ranges::iota
ranges::fold в качестве альтернативы std::accumulate

Заключение

Эта статья завершает наше путешествие по алгоритмам C++, доступным в стандартной библиотеке (кроме числовых). У большинства алгоритмов есть аналоги ranges::, а в C++23 появится ещё больше дополнений.

А мы научим вас аккуратно работать с данными, чтобы вы прокачали карьеру и стали востребованным IT-специалистом.

Краткий каталог курсов

Data Science и Machine Learning

Python, веб-разработка

Мобильная разработка

Java и C#

От основ — в глубину

А также

ссылка на оригинал статьи https://habr.com/ru/company/skillfactory/blog/707946/

Алгоритмы диапазонов C++20 — сортировка, множества, обновления C++23 и прочее

Прежде чем мы начнём

Разбиение на разделы и сортировка

`sort` и `is_sorted`

`partition`

Операции бинарного поиска

`binary_search`

Операции с множествами

`includes`

Прочее

`max_element`

`equal`

Еще больше

Numeric

Скоро в C++23

Заключение

Комментарии

Добавить комментарий Отменить ответ

Алгоритмы диапазонов C++20 — сортировка, множества, обновления C++23 и прочее

Прежде чем мы начнём

Разбиение на разделы и сортировка

sort и is_sorted

partition

Операции бинарного поиска

binary_search

Операции с множествами

includes

Прочее

max_element

equal

Еще больше

Numeric

Скоро в C++23

Заключение

Комментарии

Добавить комментарий Отменить ответ

`sort` и `is_sorted`

`partition`

`binary_search`

`includes`

`max_element`

`equal`