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

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

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

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

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

• Алгоритмы диапазонов определяются в заголовке <algorithm>, а инфраструктура диапазонов и основные типы данных определяются в заголовочном файле <ranges>.
• Обычно существует как минимум две перегрузки алгоритмов диапазона: с парой итераторов и перегрузка с одним аргументом диапазона.
• Версия, которая возвращает поддиапазон (subrange) или итератор и принимает диапазон, возвращает заимствованный диапазон или заимствованный итератор. Это помогает обнаруживать итераторы для временных диапазонов.
• Версии диапазона имеют «проекции», что может дать больше гибкости; например, можно выполнить сортировку по некоторым выбранным элементам или выполнить дополнительные преобразования перед сравнением.
• См. мою отдельную статью об этой функции с мощным потенциалом: 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");
});

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

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-специалистом. Скидка до 45% по промокоду HABR.

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

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

Data Science и Machine Learning

• Профессия Data Scientist
• Профессия Data Analyst
• Курс «Математика для Data Science»
• Курс «Математика и Machine Learning для Data Science»
• Курс по Data Engineering
• Курс «Machine Learning и Deep Learning»
• Курс по Machine Learning

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

• Профессия Fullstack-разработчик на Python
• Курс «Python для веб-разработки»
• Профессия Frontend-разработчик
• Профессия Веб-разработчик

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

• Профессия iOS-разработчик
• Профессия Android-разработчик

Java и C#

• Профессия Java-разработчик
• Профессия QA-инженер на JAVA
• Профессия C#-разработчик
• Профессия Разработчик игр на Unity

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

• Курс «Алгоритмы и структуры данных»
• Профессия C++-разработчик
• Профессия «Белый хакер»

А также

• Курс по DevOps
• Все курсы