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 に変換可能でない場合、プログラムは ill-formed となる:

• 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つしかない場合、合計はその要素の値です。
• それ以外の場合、以下の操作を順番に実行します：

1. グループから任意の2つの要素 elem1 と elem2 を取得します。
2. binary_op ( elem1, elem2 ) を計算し、結果をグループに戻します。
3. ステップ1と2をグループ内に要素が1つだけになるまで繰り返します。

計算量

与えられた \(\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() << " ms\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 ms
std::reduce (seq, double)   合計: 10,000,000.7	時間: 140.1 ms
std::reduce (par, double)   合計: 10,000,000.7	時間: 140.1 ms
std::accumulate (long)      合計: 100,000,007	時間: 46.0 ms
std::reduce (seq, long)     合計: 100,000,007	時間: 67.3 ms
std::reduce (par, long)     合計: 100,000,007	時間: 63.3 ms
// POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3 -DPARALLEL; ./a.out
std::accumulate (double)    合計: 10,000,000.7	時間: 353.4 ms
std::reduce (seq, double)   合計: 10,000,000.7	時間: 140.7 ms
std::reduce (par, double)   合計: 10,000,000.7	時間: 24.7 ms
std::accumulate (long)      合計: 100,000,007	時間: 42.4 ms
std::reduce (seq, long)     合計: 100,000,007	時間: 52.0 ms
std::reduce (par, long)     合計: 100,000,007	時間: 23.1 ms

関連項目