std::reduce

template< class InputIt >
typename std::iterator_traits<InputIt>::value_type
    reduce( InputIt first, InputIt last );

template< class ExecutionPolicy, class ForwardIt >
typename std::iterator_traits<ForwardIt>::value_type
    reduce( ExecutionPolicy&& policy,
            ForwardIt first, ForwardIt last );

template< class InputIt, class T >
T reduce( InputIt first, InputIt last, T init );

template< class ExecutionPolicy, class ForwardIt, class T >
T reduce( ExecutionPolicy&& policy,
          ForwardIt first, ForwardIt last, T init );

template< class InputIt, class T, class BinaryOp >
T reduce( InputIt first, InputIt last, T init, BinaryOp op );

template< class ExecutionPolicy,
          class ForwardIt, class T, class BinaryOp >
T reduce( ExecutionPolicy&& policy,
          ForwardIt first, ForwardIt last, T init, BinaryOp op );

Пусть binary_op является фактической бинарной операцией:

• Результат недетерминирован, если binary_op не ассоциативна или не коммутативна (например, сложение с плавающей точкой).

• Если какое-либо из следующих значений не преобразуется в T, программа считается некорректной:

• binary_op(init, *first)
• binary_op(*first, init)
• binary_op(init, init)
• binary_op(*first, *first)

• Если выполняется любое из следующих условий, поведение неопределено:

• T не является MoveConstructible.
• binary_op изменяет любой элемент [first, last).
• binary_op делает недействительным любой итератор или поддиапазон [first, last].

Параметры

Возвращаемое значение

Обобщённая сумма группы элементов над бинарной операцией binary_op определяется следующим образом:

• Если группа содержит только один элемент, сумма равна значению этого элемента.
• В противном случае выполняет следующие операции в указанном порядке:

1. Берёт любые два элемента elem1 и elem2 из группы.
2. Вычисляет binary_op ( elem1, elem2 ) и возвращает результат обратно в группу.
3. Повторяет шаги 1 и 2 до тех пор, пока в группе не останется только один элемент.

Сложность

Дано \(\scriptsize N\) N как std:: distance ( first, last ) :

Исключения

Перегрузки с параметром шаблона с именем ExecutionPolicy сообщают об ошибках следующим образом:

• Если выполнение функции, вызванной как часть алгоритма, выбрасывает исключение и ExecutionPolicy является одним из стандартных политик , std::terminate вызывается. Для любой другой ExecutionPolicy поведение определяется реализацией.
• Если алгоритму не удается выделить память, std::bad_alloc выбрасывается.

Примечания

std::reduce ведёт себя как std::accumulate за исключением того, что элементы диапазона могут быть сгруппированы и переупорядочены произвольным образом.

Пример

#if PARALLEL
#include <execution>
#define SEQ std::execution::seq,
#define PAR std::execution::par,
#else
#define SEQ
#define PAR
#endif
#include <chrono>
#include <iomanip>
#include <iostream>
#include <locale>
#include <numeric>
#include <utility>
#include <vector>
int main()
{
    std::cout.imbue(std::locale("en_US.UTF-8"));
    std::cout << std::fixed << std::setprecision(1);
    auto eval = [](auto fun)
    {
        const auto t1 = std::chrono::high_resolution_clock::now();
        const auto [name, result] = fun();
        const auto t2 = std::chrono::high_resolution_clock::now();
        const std::chrono::duration<double, std::milli> ms = t2 - t1;
        std::cout << std::setw(28) << std::left << name << "сумма: "
                  << result << '\t' << "время: " << ms.count() << " мс\n";
    };
    {
        const std::vector<double> v(100'000'007, 0.1);
        eval([&v]{ return std::pair{"std::accumulate (double)",
            std::accumulate(v.cbegin(), v.cend(), 0.0)}; });
        eval([&v]{ return std::pair{"std::reduce (seq, double)",
            std::reduce(SEQ v.cbegin(), v.cend())}; });
        eval([&v]{ return std::pair{"std::reduce (par, double)",
            std::reduce(PAR v.cbegin(), v.cend())}; });
    }
    {
        const std::vector<long> v(100'000'007, 1);
        eval([&v]{ return std::pair{"std::accumulate (long)",
            std::accumulate(v.cbegin(), v.cend(), 0l)}; });
        eval([&v]{ return std::pair{"std::reduce (seq, long)",
            std::reduce(SEQ v.cbegin(), v.cend())}; });
        eval([&v]{ return std::pair{"std::reduce (par, long)",
            std::reduce(PAR v.cbegin(), v.cend())}; });
    }
}

// POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3; ./a.out
std::accumulate (double)    сумма: 10,000,000.7	время: 356.9 мс
std::reduce (seq, double)   сумма: 10,000,000.7	время: 140.1 мс
std::reduce (par, double)   сумма: 10,000,000.7	время: 140.1 мс
std::accumulate (long)      сумма: 100,000,007	время: 46.0 мс
std::reduce (seq, long)     сумма: 100,000,007	время: 67.3 мс
std::reduce (par, long)     сумма: 100,000,007	время: 63.3 мс
// POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3 -DPARALLEL; ./a.out
std::accumulate (double)    сумма: 10,000,000.7	время: 353.4 мс
std::reduce (seq, double)   сумма: 10,000,000.7	время: 140.7 мс
std::reduce (par, double)   сумма: 10,000,000.7	время: 24.7 мс
std::accumulate (long)      сумма: 100,000,007	время: 42.4 мс
std::reduce (seq, long)     сумма: 100,000,007	время: 52.0 мс
std::reduce (par, long)     сумма: 100,000,007	время: 23.1 мс

Смотри также