namespace std {
template <class InputIterator1, class InputIterator2, class T>
T transform_reduce(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
T init); // (1) C++17
template <class InputIterator1, class InputIterator2, class T>
constexpr T
transform_reduce(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
T init); // (1) C++20
template <class InputIterator1, class InputIterator2, class T,
class BinaryOperation1, class BinaryOperation2>
T transform_reduce(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
T init,
BinaryOperation1 binary_op1,
BinaryOperation2 binary_op2); // (2) C++17
template <class InputIterator1, class InputIterator2, class T,
class BinaryOperation1, class BinaryOperation2>
constexpr T
transform_reduce(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
T init,
BinaryOperation1 binary_op1,
BinaryOperation2 binary_op2); // (2) C++20
template <class InputIterator, class T,
class BinaryOperation, class UnaryOperation>
T transform_reduce(InputIterator first,
InputIterator last,
T init,
BinaryOperation binary_op,
UnaryOperation unary_op); // (3) C++17
template <class InputIterator, class T,
class BinaryOperation, class UnaryOperation>
constexpr T
transform_reduce(InputIterator first,
InputIterator last,
T init,
BinaryOperation binary_op,
UnaryOperation unary_op); // (3) C++20
template <class ExecutionPolicy,
class ForwardIterator1, class ForwardIterator2, class T>
T transform_reduce(ExecutionPolicy&& exec,
ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
T init); // (4) C++17
template <class ExecutionPolicy,
class ForwardIterator1, class ForwardIterator2, class T,
class BinaryOperation1, class BinaryOperation2>
T transform_reduce(ExecutionPolicy&& exec,
ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
T init,
BinaryOperation1 binary_op1,
BinaryOperation2 binary_op2); // (5) C++17
template <class ExecutionPolicy,
class ForwardIterator, class T,
class BinaryOperation, class UnaryOperation>
T transform_reduce(ExecutionPolicy&& exec,
ForwardIterator first,
ForwardIterator last,
T init,
BinaryOperation binary_op,
UnaryOperation unary_op); // (6) C++17
}
概要
transform_reduce()
は、イテレータ範囲の要素を変換しながら集計する関数である。
(1)、(2)、(4)、(5)は、イテレータ範囲[first1, last1)
の各要素をx
、イテレータ範囲[first2, first2+(last1 - first1))
の各要素をy
として、初期値(init
)とbinary_op2(x, y)
した各要素を合算したリストの任意の組み合わせに、順不同でbinary_op1(binary_op1(a, b), binary_op1(c, d))
のように適用していき、集計値を計算する。
(3)と(6)は、初期値(init
)と、イテレータ範囲[first, last)
の各要素に関数オブジェクトunary_op
を適用して合算したリストの任意の組み合わせに、順不同でbinary_op(binary_op(a, b), binary_op(c, d))
のように適用していき、集計値を計算する。
- (1) : リスト集計の二項演算に
operator+
を使用し、2つの範囲の要素を掛け合わせる二項演算にoperator*
を使用する - (2) : リスト集計の二項演算に
binary_op1
を使用し、2つの範囲の要素を掛け合わせる二項演算にbinary_op2
を使用する - (3) : リスト集計の二項演算に
operator+
を使用し、各要素の変換にunary_op
を使用する - (4) : (1)の並列アルゴリズム版。第1パラメータとして実行ポリシーをとる
- (5) : (2)の並列アルゴリズム版。第1パラメータとして実行ポリシーをとる
- (6) : (3)の並列アルゴリズム版。第1パラメータとして実行ポリシーをとる
要件
- (1), (2), (4), (5) : 関数オブジェクト
binary_op1
とbinary_op2
の呼び出しは、イテレータ範囲[first1, last1]
と[first2, first2 + (last1 - first1)]
の要素変更およびイテレータの無効化をしてはならない - (3), (6) : 関数オブジェクト
unary_op
とbinary_op
の呼び出しは、イテレータ範囲[first, last]
の要素変更およびイテレータの無効化をしてはならない
テンプレートパラメータ制約
- (1), (2), (3), (4), (5), (6) : 型
T
がstd::move_constructible
要件を満たすこと - (1), (2), (4), (5) : 以下の全ての演算結果の型が、型
T
に変換可能であることbinary_op1(init, init)
binary_op1(init, binary_op2(*first1, *first2))
binary_op1(binary_op2(*first1, *first2), init)
binary_op1(binary_op2(*first1, *first2), binary_op2(*first1, *first2))
- (3), (6) : 以下の全ての演算結果の型が、型
T
に変換可能であることbinary_op(init, init)
binary_op(init, unary_op(*first))
binary_op(unary_op(*first), init)
binary_op(unary_op(*first), unary_op(*first))
効果
-
(1) : 以下と等価
return transform_reduce(first1, last1, first2, init, plus<>(), multiplies<>);
-
(2), (5) : イテレータ範囲
[first1, last1)
と[first2, first2+(last1 - first1))
について、リスト[init, binary_op2(*first1, *first2), binary_op2(*(first1 + 1), *(first2 + 1)), binary_op2(*(first1 + 2), *(first2 + 2)), ...]
を任意の部分リストへ分割し、各部分リストの要素を順不同にbinary_op1(a, b)
を実行していき、それを実行していった結果同士も順不同にbinary_op1(sum1, sum2)
のように集計して返す -
(3), (6) : イテレータ範囲
[first, last)
について、リスト[init, unary_op(*first), unary_op(*(first + 1)), unary_op(*(first + 2)), ... unary_op(*(first + (last - first - 1)))]
を任意の部分リストへ分割し、各部分リストの要素を順不同にbinary_op(a, b)
を実行していき、それを実行していった結果同士も順不同にbinary_op(sum1, sum2)
のように集計して返す -
(4) : 以下と等価
return transform_reduce(std::forward<ExecutionPolicy>(exec), first1, last1, first2, init, plus<>(), multiplies<>());
計算量
- (1), (2), (4), (5) : 関数オブジェクト
binary_op1
とbinary_op2
を、O(last1 - first1
)回だけ適用する - (3), (6) : 関数オブジェクト
unary_op
とbinary_op
をO(last - first
)回だけ適用する
備考
- (3), (6) : 関数オブジェクト
unary_op
は初期値init
に対しては適用しない
例
#include <iostream>
#include <vector>
#include <numeric>
int main()
{
const std::vector<int> v1 = {1, 2, 3, 4, 5};
const std::vector<int> v2 = {2, 3, 4, 5, 6};
// (1) : 2つのリストを集計する
// sum1 = 1*2 + 2*3 + 3*4 + 4*5, 5*6
int sum1 = std::transform_reduce(v1.begin(), v1.end(), v2.begin(), 0);
std::cout << "sum1 : " << sum1 << std::endl;
// (2) : 2つのリストを集計する。
// リストを集計する2項演算と、2つのリストの要素を掛け合わせる2項演算を指定する
int sum2 = std::transform_reduce(v1.begin(), v1.end(), v2.begin(), 0,
[](int a, int b) { return a + b; }, // 集計関数
[](int a, int b) { return a * b; }); // 2つの要素を合成する関数
std::cout << "sum2 : " << sum2 << std::endl;
// (3) : リストの各要素を変換しながら集計する
// 1*2 + 2*2 + 3*2 + 4*2 + 5*2
int sum3 = std::transform_reduce(v1.begin(), v1.end(), 0,
[](int acc, int i) { return acc + i; }, // 集計関数
[](int x) { return x * 2; }); // 変換関数
std::cout << "sum3 : " << sum3 << std::endl;
}
出力
sum1 : 70
sum2 : 70
sum3 : 30
バージョン
言語
- C++17
処理系
- Clang: 5.0.0 ✅
- GCC:
- Visual C++: ??
参照
- P0024R2 The Parallelism TS Should be Standardized
- P0452R1 Unifying
<numeric>
Parallel Algorithms - P0467R2 Iterator Concerns for Parallel Algorithms
- P0574R1: Algorithm Complexity Constraints and Parallel Overloads
- P0623R0 Final C++17 Parallel Algorithms Fixes
- P1645R1
constexpr
for<numeric>
algorithms- C++20で、並列バージョン以外の数値計算アルゴリズムが
constexpr
対応した
- C++20で、並列バージョン以外の数値計算アルゴリズムが