std:: transform_reduce

From cppreference.net

ヘッダー `<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) 範囲

first1

last1

と std:: distance ( first1, last1 ) 個の要素からなる first2 から始まる範囲の各要素ペアに transform を適用し、その結果（順序変更や集約が行われる可能性あり）を初期値 init と共に reduce で縮約します。

結果は非決定的になります、もし reduce が結合的または可換的でない場合（浮動小数点加算など）。

以下のいずれかの値を

に変換できない場合、プログラムは不適格となる：

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

last2 が std:: distance ( first1, last1 ) 番目の first2 の次イテレータとして与えられたとき、以下のいずれかの条件が満たされる場合、動作は未定義です：

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

5) 範囲

first

last

内の各要素に transform を適用し、その結果（順序変更や集約が行われている可能性がある未規定の方法で）を初期値 init と共に reduce で縮約する。

結果は非決定的になります、もし reduce が結合的でも可換的でもない場合（浮動小数点加算など）。

以下のいずれかの値を

に変換できない場合、プログラムは不適格となる：

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	-	二項 FunctionObject 。 transform の結果、他の reduce の結果、および init に対して未指定の順序で適用される。
transform	-	単項または二項 FunctionObject 。入力範囲の各要素に適用される。戻り値の型は reduce への入力として受け入れ可能でなければならない。
型要件
- `InputIt1, InputIt2, InputIt` は LegacyInputIterator の要件を満たさなければならない。
- `ForwardIt1, ForwardIt2, ForwardIt` は LegacyForwardIterator の要件を満たさなければならない。

戻り値

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と2を、グループ内に要素が1つだけになるまで繰り返す。

計算量

$\scriptsize N$ $N$ を std:: distance ( first1, last1 ) として与えられる（またはオーバーロード (5,6) については std:: distance ( first, last ) ）:

1,2)

O(N)

回の std:: plus <> ( ) および std:: multiplies <> ( ) の適用。

3-6)

O(N)

回の reduce および transform の適用。

例外

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

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

注記

transform は init に適用されることはありません。

first == last または first1 == last1 の場合、 init は変更されずに返されます。

例

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
// POSIXでの並列実行のためのコンパイルオプション:
// g++ -O2 -std=c++17 -Wall -Wextra -pedantic -DPARALLEL ./example.cpp -ltbb -o tr; ./tr

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

accumulate	要素の範囲を合計または畳み込む (function template)
transform	要素の範囲に関数を適用し、結果を宛先範囲に格納する (function template)
reduce (C++17)	std::accumulate と類似しているが、順序不同で実行される (function template)

cppreference.net

Namespaces

Variants

std:: transform_reduce

目次

パラメータ

戻り値

計算量

例外

注記

例

関連項目