std::transform_reduce

ヘッダー `<numeric>` で定義
template< class InputIt1, class InputIt2, class T > T transform_reduce( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init );	(1)	(C++17以降) (C++20 以降 constexpr)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T > T transform_reduce( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, T init );	(2)	(C++17以降)
template< class InputIt1, class InputIt2, class T, class BinaryOp1, class BinaryOp2 > T transform_reduce( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init, BinaryOp1 reduce, BinaryOp2 transform );	(3)	(C++17以降) (C++20 以降 constexpr)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T, class BinaryOp1, class BinaryOp2 > T transform_reduce( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, T init, BinaryOp1 reduce, BinaryOp2 transform );	(4)	(C++17以降)
template< class InputIt, class T, class BinaryOp, class UnaryOp > T transform_reduce( InputIt first, InputIt last, T init, BinaryOp reduce, UnaryOp transform );	(5)	(C++17以降) (C++20 以降 constexpr)
template< class ExecutionPolicy, class ForwardIt, class T, class BinaryOp, class UnaryOp > T transform_reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init, BinaryOp reduce, UnaryOp transform );	(6)	(C++17以降)

1) transform_reduce(first1, last1, first2, init,
std::plus<>(), std::multiplies<>()) と同等であり、`std::inner_product` の並列化されたバージョンです。

3) `transform` を、範囲 `[first1, last1)` と `first2` から始まる `std::distance(first1, last1)` 個の要素からなる範囲の要素の各ペアに適用し、その結果を初期値 `init` と共に `reduce` で（順序が入れ替わったり集約されたりする可能性のある方法で）削減します。

`reduce` が結合律または可換律を満たさない場合（例: 浮動小数点数の加算）、結果は非決定的になります。

以下のいずれかの値が `T` に変換できない場合、プログラムは ill-formed です。

reduce(init, init)
reduce(init, transform(*first1, *first2))
reduce(transform(*first1, *first2), init)
reduce(transform(*first1, *first2), transform(*first1, *first2))

`last2` を `first2` の `std::distance(first1, last1)` 番目の次のイテレータとした場合、以下のいずれかの条件が満たされると、動作は未定義となります。

T は MoveConstructible ではない。
transform または reduce が `[first1, last1)` または `[first2, last2)` のいずれかの要素を変更する。
transform または reduce が `[first1, last1]` または `[first2, last2]` のいずれかのイテレータまたはサブ範囲を無効にする。

5) `transform` を入力範囲 `[first, last)` の各要素に適用し、その結果を初期値 `init` と共に `reduce` で（順序が入れ替わったり集約されたりする可能性のある方法で）削減します。

`reduce` が結合律または可換律を満たさない場合（例: 浮動小数点数の加算）、結果は非決定的になります。

以下のいずれかの値が `T` に変換できない場合、プログラムは ill-formed です。

reduce(init, init)
reduce(init, transform(*first))
reduce(transform(*first), init)
reduce(transform(*first), transform(*first))

以下のいずれかの条件が満たされている場合、動作は未定義です。

T は MoveConstructible ではない。
transform または reduce が `[first, last)` のいずれかの要素を変更する。
transform または reduce が `[first, last]` のいずれかのイテレータまたはサブ範囲を無効にする。

2,4,6) (1,3,5) と同じですが、policy に従って実行されます。

これらのオーバーロードは、以下のすべての条件が満たされた場合にのみオーバーロード解決に参加する。

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> は true です。	(C++20まで)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> は true です。	(C++20以降)

first1, last1	-	`transform` の左オペランドとして使用される要素の範囲を定義するイテレータのペア。
first2	-	`transform` の右オペランドとして使用される要素の範囲の開始。
first, last	-	`transform` のオペランドとして使用される要素の範囲を定義するイテレータのペア。
init	-	一般化された合計の初期値
policy	-	使用する実行ポリシー
reduce	-	`transform` の結果、その他の `reduce` の結果、および `init` に、未指定の順序で適用される二項述語オブジェクト。
transform	-	入力範囲（複数可）の各要素に適用される単項または二項述語オブジェクト。戻り値の型は `reduce` の入力として受け入れ可能でなければなりません。
型要件
- `InputIt1, InputIt2, InputIt` は、`LegacyInputIterator` の要件を満たしている必要があります。
- `ForwardIt1, ForwardIt2, ForwardIt` は、`LegacyForwardIterator` の要件を満たしている必要があります。

[edit] Return value

1,2) `init` と `values` の、`std::plus<>` による一般化された合計。ここで `values` は `std::multiplies<>` によって変換された値であり、各値は2つの入力範囲からの要素のペアから変換されます。

3,4) `init` と `values` の、`reduce` による一般化された合計。ここで `values` は `transform` によって変換された値であり、各値は2つの入力範囲からの要素のペアから変換されます。

5,6) `init` と `values` の、`reduce` による一般化された合計。ここで `values` は `transform` によって変換された値であり、各値は入力範囲の要素から変換されます。

二項演算子 `binary_op` による要素群の「一般化された合計」は、次のように定義されます。

グループに要素が1つしかない場合、合計はその要素の値です。
そうでない場合、次の操作を順に実行します。

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

[edit] Complexity

オーバーロード (5,6) については `std::distance(first1, last1)`（または `std::distance(first, last)`）による `N` が与えられます。

1,2) `std::plus<>` および `std::multiplies<>` の `O(N)` 回の適用。

3-6) `reduce` および `transform` の `O(N)` 回の適用。

[edit] Exceptions

ExecutionPolicy というテンプレートパラメータを持つオーバーロードは、次のようにエラーを報告します。

アルゴリズムの一部として呼び出された関数の実行が例外をスローし、ExecutionPolicy が標準ポリシーのいずれかである場合、std::terminate が呼び出されます。その他の ExecutionPolicy の場合、動作は実装定義です。
アルゴリズムがメモリの割り当てに失敗した場合、std::bad_alloc がスローされます。

[edit] Notes

`transform` は `init` には適用されません。

もし `first == last` または `first1 == last1` であれば、`init` が変更されずに返されます。

[edit] Example

`transform_reduce` は `std::inner_product` を並列化するために使用できます。一部のシステムでは、並列実行の利点を得るために追加のサポートが必要になる場合があります。例えば、GNU/Linux では、Intel TBB をインストールし、gcc/clang コンパイラに `-ltbb` オプションを提供する必要があります。

このコードを実行

#if PARALLEL
#include <execution>
#define PAR std::execution::par,
#else
#define PAR
#endif
 
#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <locale>
#include <numeric>
#include <vector>
 
// to parallelize non-associate accumulative operation, you'd better choose
// transform_reduce instead of reduce; e.g., a + b * b != b + a * a
void print_sum_squared(long const num)
{
    std::cout.imbue(std::locale{"en_US.UTF8"});
    std::cout << "num = " << num << '\n';
 
    // create an immutable vector filled with pattern: 1,2,3,4, 1,2,3,4 ...
    const std::vector<long> v{[n = num * 4] {
        std::vector<long> v;
        v.reserve(n);
        std::generate_n(std::back_inserter(v), n,
            [i = 0]() mutable { return 1 + i++ % 4; });
        return v;
    }()};
 
    auto squared_sum = [](auto sum, auto val) { return sum + val * val; };
 
    auto sum1 = std::accumulate(v.cbegin(), v.cend(), 0L, squared_sum);
    std::cout << "accumulate(): " << sum1 << '\n';
 
    auto sum2 = std::reduce(PAR v.cbegin(), v.cend(), 0L, squared_sum);
    std::cout << "reduce(): " << sum2 << '\n';
 
    auto sum3 = std::transform_reduce(PAR v.cbegin(), v.cend(), 0L, std::plus{},
                                      [](auto val) { return val * val; });
    std::cout << "transform_reduce(): " << sum3 << "\n\n";
}
 
int main()
{
    print_sum_squared(1);
    print_sum_squared(1'000);
    print_sum_squared(1'000'000);
}

実行結果の例

num = 1
accumulate(): 30
reduce(): 30
transform_reduce(): 30
 
num = 1,000
accumulate(): 30,000
reduce(): -7,025,681,278,312,630,348
transform_reduce(): 30,000
 
num = 1,000,000
accumulate(): 30,000,000
reduce(): -5,314,886,882,370,003,032
transform_reduce(): 30,000,000
 
// Compile-options for parallel execution on POSIX:
// g++ -O2 -std=c++17 -Wall -Wextra -pedantic -DPARALLEL ./example.cpp -ltbb -o tr; ./tr

[edit] See also

accumulate	範囲の要素を合計または畳み込む (関数テンプレート) [編集]
transform	範囲内の要素に関数を適用し、結果を結果範囲に格納する (関数テンプレート) [編集]
reduce (C++17)	std::accumulate に似ているが、順序不同 (関数テンプレート) [編集]

コンパイラサポート
フリースタンディングとホスト
言語
標準ライブラリ
標準ライブラリヘッダー
名前付き要件
機能テストマクロ (C++20)
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
メモリ管理ライブラリ
メタプログラミングライブラリ (C++11)
汎用ユーティリティライブラリ
コンテナライブラリ
イテレータライブラリ
Rangesライブラリ (C++20)
アルゴリズムライブラリ
文字列ライブラリ
テキスト処理ライブラリ
数値ライブラリ
日付と時刻ライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
並行サポートライブラリ (C++11)
実行制御ライブラリ (C++26)
Technical specifications (技術仕様)
シンボルインデックス
外部ライブラリ

cppreference.com

名前空間

変種

表示

操作