Библиотека Ranges для C++20 предлагает альтернативы для большинства алгоритмов. На этот раз я хочу показать вам десять немодифицирующих операций. Мы сравним их со «старой» стандартной версией и увидим их преимущества и ограничения.

Подробности — к старту нашего курса по разработке на C++.

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

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

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

Ниже приведены примеры, демонстрирующие как стандартный алгоритм, так и его альтернативную версию с диапазонами. Они иллюстрируют некоторые базовые концепции, в них заложено стремление не использовать расширенную композицию диапазонов или представления. Мы воспользуемся порядком, указанным в cppreference/algorithms, и рассмотрим в этой части «немодифицирующие операции с последовательностями».

1. all_of, any_of, none_of

Стандартный алгоритм:

#include <algorithm> #include <vector> #include <iostream> #include <ranges>  int main() {     const std::vector nums = {1, 2, 3, -4, 5, 6, 7, 8 };      auto is_positive = [](const auto& v) { return v > 0; };      // standard version:     auto res = std::all_of(begin(nums), end(nums), is_positive);     std::cout << "std::all_of: " << res << '\n';      res = std::any_of(begin(nums), end(nums), is_positive);     std::cout << "std::any_of: " << res << '\n'; }

И версия с диапазонами:

// ranges version: res = std::ranges::all_of(nums, is_positive); std::cout << "std::ranges::all_of: " << res << '\n';  res = std::ranges::any_of(nums, is_positive); std::cout << "std::ranges::any_of: " << res << '\n';

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

Можно написать пример сложнее, где сканируется контейнер пользовательских типов:

#include <algorithm> #include <vector> #include <iostream> #include <ranges>  struct Product {     std::string name_;     double value_ { 0.0 }; };  int main() {     const std::vector<Product> prods {         { "box", 10.0 }, {"tv", 100.0}, {"none", -1.0}     };      auto is_positive = [](const auto& v) { return v > 0; };     auto is_positive_val = [](const Product& p) {         return p.value_ > 0;     };      // standard version:     auto res = std::all_of(begin(prods), end(prods), is_positive_val);     std::cout << "std::all_of: " << res << '\n';      res = std::any_of(begin(prods), end(prods), is_positive_val);     std::cout << "std::any_of: " << res << '\n';      // ranges version:     res = std::ranges::all_of(prods, is_positive, &Product::value_);     std::cout << "std::ranges::all_of: " << res << '\n';      res = std::ranges::any_of(prods, is_positive, &Product::value_);     std::cout << "std::ranges::any_of: " << res << '\n'; }

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

В версии с диапазонами мы по-прежнему можем использовать общий предикат is_positive, но я использовал проекцию, которая только «берёт» Product::value_ и передаёт его в предикат. В стандартном случае пришлось бы написать пользовательскую лямбда-функцию с учётом типа Product.

2. for_each

Альтернатива хорошему диапазону на основе цикла for:

#include <algorithm> #include <vector> #include <iostream> #include <ranges>  struct Product {     std::string name_;     double value_ { 0.0 }; };  int main() {     const std::vector<Product> prods {         { "box", 10.0 }, {"tv", 100.0}, {"none", -1.0}     };      auto out = [](const auto& v) { std::cout << v << ", "; };      // standard version:     std::cout << "std::for_each: \n";     std::for_each(begin(prods), end(prods), [](const Product& p){         std::cout << p.name_  << ", " << p.value_ << '\n';     });      std::cout << "std::for_each only names reverse: \n";     std::for_each(rbegin(prods), rend(prods), [](const Product& p){         std::cout << p.name_  << '\n';     });      // ranges version:     std::cout << "std::ranges::for_each: \n";     std::ranges::for_each(prods, [](const Product& p) {         std::cout << p.name_  << ", " << p.value_ << '\n';     });      std::cout << "std::ranges::for_each only names in reverse: \n";     std::ranges::for_each(prods | std::views::reverse,                           out, &Product::name_); }

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

Самое интересное заключается в том, что для печати в обратном порядке в стандартной версии требуется итераторы rbegin/rend, а затем пользовательская унарная функцию для вывода точного члена данных из класса Product. В то время как с диапазонами можно применить views::reverse, использовать простую функцию вывода, а затем проекцию.

Чего не хватает, так это параллельной версии алгоритмов диапазонов:

// standard: std::for_each(std::execution::par, begin(prods), end(prods), /*...*/); // no ranges version... // std::ranges::for_each(std::execution::par, prods, /*... */); // doesn't compile...

Параллельные версии отсутствуют для алгоритмов всех диапазонов, а не только для for_each.

3. count_if

Ниже посчитаем товары, название которых начинается с «no»:

#include <algorithm> #include <vector> #include <iostream> #include <ranges>  struct Product {     std::string name_;     double value_ { 0.0 }; };  int main() {     const std::vector<Product> prods {         { "box", 10.0 }, {"tv", 100.0}, {"none", -1.0},         { "car", 1000.0 }, {"toy", 40.0}, {"none", 0.0}     };      // standard version:         auto res = std::count_if(begin(prods), end(prods), [](const Product& p){         return p.name_.starts_with("no");     });     std::cout << "std::count_if: " << res << '\n';      // ranges version:     res = std::ranges::count_if(prods, [](const Product& p) {         return p.name_.starts_with("no");     });     std::cout << "std::ranges::count_if: " << res << '\n';  // alternative version for "none":     res = std::ranges::count(prods, std::string{"none"}, &Product::name_);     std::cout << "std::ranges::count: " << res << '\n'; }

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

Выше показаны три подхода, последний использует проекцию проверки только члена данных Product::name_. При таком подходе мы ищем именно "none", это строже, чем starts_with.

4. find_if

До сих пор наши текстовые алгоритмы возвращали логические или целочисленные значения, но в случае с функциями find* поставляются итераторы (или поддиапазоны), которые показывают то же вхождение:

#include <algorithm> #include <vector> #include <iostream> #include <ranges>  struct Product {     std::string name_;     double value_ { 0.0 }; };  int main() {     const std::vector<Product> prods {         { "box", 10.0 }, {"tv", 100.0}, {"rocket", 10000.0},         { "car", 1000.0 }, {"toy", 40.0}, {"none", 0.0}     };      // standard version:         auto it = std::find_if(begin(prods), end(prods), [](const Product& p){         return p.name_.starts_with("ro");     });     if (it != end(prods))         std::cout << "std::find_if: " << it->name_ << '\n';      // ranges version:     auto res = std::ranges::find_if(prods, [](const Product& p) {         return p.name_.starts_with("ro");     });     if (res != end(prods))         std::cout << "std::ranges::find_if: " << res->name_ << '\n'; }

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

Как и во многих других алгоритмах, существует также «обычная» версия, в которой можно передать два итератора:

it = std::ranges::find_if(begin(prods), end(prods), [](const Product& p) {     return p.name_.starts_with("ro"); });

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

struct Product {     std::string name_;     double value_ { 0.0 }; };  std::vector<Product> GetProds() {     return {         { "box", 10.0 }, {"tv", 100.0}, {"rocket", 10000.0},         { "car", 1000.0 }, {"toy", 40.0}, {"none", 0.0}     }; }  int main() {     auto it = std::ranges::find_if(GetProds(), [](const Product& p) {         return p.name_.starts_with("ro");     });     std::cout << "std::ranges::find_if: " << it->name_ << '\n'; }

Это не скомпилируется, и вы увидите следующую ошибку:

error: base operand of '->' has non-pointer type 'std::ranges::dangling'    22 |     std::cout << "std::ranges::find_if: " << it->name_ << '\n';       |                                                ^~

Как видите, компилятор проверил, что GetProds() возвращает временное значение, и найденный нами итератор повиснет.

Смотрите код в @Compiler Explorer

5. find_first_of

Давайте взглянем на альтернативу find*, которая ищет несколько элементов одновременно.

#include <algorithm> #include <vector> #include <iostream> #include <ranges>  struct Product {     std::string name_;     double value_ { 0.0 };      friend bool operator==(const Product& a, const Product& b) {         return a.name_ == b.name_ && abs(a.value_ - b.value_) < 0.0001;     } };  int main() {     const std::vector<Product> prods {         { "box", 10.0 }, {"default", 0.0 }, {"tv", 100.0}, {"rocket", 10000.0},         { "car", 1000.0 }, {"toy", 40.0}, {"none", 0.0 }, { "ball", 40.0 }     };      const std::vector<Product> invalids {         {"default", 0.0 }, {"none", 0.0 }     };      // standard version:         auto it = std::find_first_of(begin(prods), end(prods), begin(invalids), end(invalids));     if (it != end(prods)) {         std::cout << "std::find_first_of: " << it->name_ << " at: "                   << std::distance(begin(prods), it) <<'\n';         auto it2 = std::find_first_of(std::next(it), end(prods), begin(invalids), end(invalids));         if (it2 != end(prods))             std::cout << "std::find_first_of: " << it2->name_ << " at: "                       << std::distance(begin(prods), it2) <<'\n';     }      // ranges version:     const std::array<std::string, 2> arrInvalids{"default", "none"};     auto res = std::ranges::find_first_of(prods, arrInvalids,                            std::ranges::equal_to{}, &Product::name_);     if (res != end(prods)) {         const auto pos = std::distance(begin(prods), res);         std::cout << "std::ranges::find_first_of: " << res->name_                   << " at: " << pos <<'\n';          auto res2 = std::ranges::find_first_of(prods | std::views::drop(pos+1), arrInvalids,                            std::ranges::equal_to{}, &Product::name_);         if (res2 != end(prods)) {             std::cout << "std::ranges::find_first_of: " << res2->name_                       << " at: " << std::distance(begin(prods), res2) <<'\n';                 }     } }

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

std::find_first_of принимает две пары итераторов. В этом примере я хотел найти «невалидные» товары в последовательности prod. Я сравниваю продукты, поэтому для структуры пришлось определить operator==. А вот другой подход: я могу предоставить бинарную операцию, а затем сравнить только имена:

auto cmpNames = [](const Product& a, const Product& b) {     return a.name_ == b.name_; };  auto it = std::find_first_of(begin(prods), end(prods),                      begin(invalids), end(invalids), cmpNames); if (it != end(prods)) {     // ... }

Чтобы добиться того же самого, в версии c диапазонами я могу использовать проекции и компаратор по умолчанию:

const std::array<std::string, 2> arrInvalids{"default", "none"}; auto res = std::ranges::find_first_of(prods, arrInvalids,                            std::ranges::equal_to{}, &Product::name_);

Далее интересно то, что для второго поиска можно воспользоваться drop, чтобы пропустить первые N элементов из диапазона:

auto res2 = std::ranges::find_first_of(prods | std::views::drop(pos+1),                arrInvalids, std::ranges::equal_to{}, &Product::name_);

Решить эту задачу можно и при помощи версии с двумя парами итераторов:

auto res2 = std::ranges::find_first_of(std::next(res), end(prods),                            begin(arrInvalids), end(arrInvalids),                            std::ranges::equal_to{}, &Product::name_);

6. mismatch

С помощью алгоритма mismatch можно найти первое место, где два диапазона различаются:

#include <algorithm> #include <vector> #include <iostream> #include <ranges> #include <iomanip> // quoted  int main() {     const std::string firstStr = "Hello Super World";     const std::string secondStr = "Hello Amazing World";      std::cout << "mismatch for " << std::quoted(firstStr)               << " and " << std::quoted(secondStr) << '\n';      // standard version:            auto [first, second] = std::mismatch(begin(firstStr), end(firstStr), begin(secondStr));     {         const auto pos = std::distance(begin(firstStr), first);         std::cout << "std::mismatch: at pos " << pos << '\n';     }      // ranges version:     auto res = std::ranges::mismatch(firstStr, secondStr);     {         const auto pos = std::distance(begin(firstStr), res.in1);         std::cout << "std::ranges::mismatch: at pos " << pos << '\n';             } }

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

Версия с диапазонами возвращает:

template<class I1, class I2> using mismatch_result = ranges::in_in_result<I1, I2>;

Это пара итераторов, но получить к ним доступ можно через .in1 и .in2.

А почему не простой диапазон? По ссылке cpp увидим такое предложение:

В отличие от std::pair и std::tuple, этот шаблон класса имеет элементы данных со значимыми именами.

Результат отлично работает со структурированной привязкой (структурированным биндингом), поэтому можно написать так:

auto [n1, n2] = std::ranges::mismatch(firstStr, secondStr); const auto pos = std::distance(begin(firstStr), n1); std::cout << "std::ranges::mismatch: at pos " << pos << '\n';    

Код почти такой же, как и в стандартной версии.

7. search

Поиск шаблонов в другом диапазоне/контейнере:

#include <algorithm> #include <vector> #include <iostream> #include <ranges> #include <functional> // searchers #include <iomanip>  int main() {     const std::string testString = "Hello Super World";     const std::string needle = "Super";      std::cout << "looking for " << std::quoted(needle)               << " in " << std::quoted(testString) << '\n';      // standard version:            auto it = std::search(testString.begin(), testString.end(),                  std::boyer_moore_searcher(needle.begin(), needle.end()));      if (it != testString.end()) {         const auto pos = std::distance(testString.begin(), it);         std::cout << "std::search: found at pos " << pos << '\n';     }      // ranges version:     auto res = std::ranges::search(testString, needle);     if (!res.empty()) {         const auto first = std::distance(testString.begin(), res.begin());         const auto last = std::distance(testString.begin(), res.end());         std::cout << "std::ranges::search: found between "                   << first << " and " << last << '\n';             } }

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

Стандартная версия возвращает итератор к первой строке к месту, где начинается вторая строка (или к end(), если там её нет). Версия диапазонов возвращает поддиапазон (или borrowed_subrange).

Воспользоваться проекциями можно и для проверки без учёта регистра:

// ranges version: const std::string testString2 = "hello abc world"; const std::string needle2 = "ABC"; std::cout << "looking for " << std::quoted(needle2) << " in "           << std::quoted(testString2) << '\n';  res = std::ranges::search(testString2, needle2,   std::ranges::equal_to{}, ::toupper, ::toupper); if (!res.empty()) { const auto first = std::distance(testString2.begin(), res.begin()); const auto last = std::distance(testString2.begin(), res.end()); std::cout << "std::ranges::search: found between "   << first << " and " << last << '\n';         }

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

Подробнее о поиске можно прочитать в этих двух моих статьях:

• Speeding up Pattern Searches with Boyer-Moore Algorithm from C++17 — C++ Stories
• Preprocessing Phase for C++17’s Searchers — C++ Stories

Другая функция ranges::search_n удобна для поиска n вхождений заданного значения во входном диапазоне:

#include <algorithm> #include <iostream> #include <ranges> #include <iomanip>  int main() {     const std::string sequence = "CTGCCCAGGGTTT";     const char letter = 'C';     const size_t count = 3;      std::cout << "looking for " << count << " "               << letter << "'s in " << std::quoted(sequence) << '\n';      // standard version:            auto it = std::search_n(begin(sequence), end(sequence), count, letter);      if (it != end(sequence))     {         const auto pos = std::distance(begin(sequence), it);         std::cout << "std::search_n: found at pos " << pos << '\n';     }      // ranges version:     auto res = std::ranges::search_n(sequence, count, letter);     if (!res.empty())     {         const auto first = std::distance(begin(sequence), res.begin());         const auto last = std::distance(begin(sequence), res.end());         std::cout << "std::ranges::search_n: found between "                   << first << " and " << last << '\n';             } }

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

В стандартной версии нет специальных поисковиков; вызвать поиск можно только с использованием параллельных алгоритмов.

Заключение

Мы рассмотрели семь различных «типов» алгоритмов в категории немодифицирующих операций: проверка некоторого предиката для всех/ни одного/некоторых элементов, поиск, нахождение, общая итерация. Всего более 10 примеров.

Алгоритмы диапазонов предлагают упрощённый способ передачи «целого» контейнера — всего один аргумент, а не как с итераторами. Они также допускают проекции, в них предусмотрен способ обнаружения итераторов во временном диапазоне. У них есть ограничения, такие как отсутствие расширенных поисковиков или режима параллельного выполнения.

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

• Профессия C++-разработчик
• Профессия Data Scientist (24 месяца)