namespace std {
template <class InputIterator>
typename iterator_traits<InputIterator>::value_type
reduce(InputIterator first, InputIterator last); // (1) C++17
template <class InputIterator>
constexpr typename iterator_traits<InputIterator>::value_type
reduce(InputIterator first, InputIterator last); // (1) C++20
template <class InputIterator, class T>
T reduce(InputIterator first, InputIterator last, T init); // (2) C++17
template <class InputIterator, class T>
constexpr T
reduce(InputIterator first, InputIterator last, T init); // (2) C++20
template <class InputIterator, class T, class BinaryOperation>
T reduce(InputIterator first, InputIterator last, T init,
BinaryOperation binary_op); // (3) C++17
template <class InputIterator, class T, class BinaryOperation>
constexpr T
reduce(InputIterator first, InputIterator last, T init,
BinaryOperation binary_op); // (3) C++20
template <class ExecutionPolicy, class ForwardIterator>
typename iterator_traits<ForwardIterator>::value_type
reduce(ExecutionPolicy&& exec,
ForwardIterator first,
ForwardIterator last); // (4) C++17
template <class ExecutionPolicy, class ForwardIterator, class T>
T reduce(ExecutionPolicy&& exec,
ForwardIterator first,
ForwardIterator last,
T init); // (5) C++17
template <class ExecutionPolicy, class ForwardIterator, class T, class BinaryOperation>
T reduce(ExecutionPolicy&& exec,
ForwardIterator first,
ForwardIterator last,
T init,
BinaryOperation binary_op); // (6) C++17
}
概要
reduce()
は、イテレータ範囲[first, last)
を集計する関数である。accumulate()
関数は範囲の先頭から順に要素を集計するが、この関数は並列計算のために集計順を規定しない。
初期値(init
)とイテレータ範囲[first, last)
を合算したリストの任意の組み合わせに、順不同でbinary_op(binary_op(a, b), binary_op(c, d))
のように適用していき、集計値を計算する。
- (1) : 集計の初期値をイテレータ範囲の要素型の値初期化値 (算術型なら
0
) とし、二項演算にoperator+
を使用する。それによって、このオーバーロードは、範囲の合計値を求める処理となる - (2) : 初期値をパラメータ
init
として受け取り、二項演算はoperator+
を使用する - (3) : 初期値をパラメータ
init
として受け取り、任意の二項演算binary_op
を使用して集計を行う - (4) : (1)の並列アルゴリズム版。第1パラメータとして実行ポリシーをとる
- (5) : (2)の並列アルゴリズム版。第1パラメータとして実行ポリシーをとる
- (6) : (3)の並列アルゴリズム版。第1パラメータとして実行ポリシーをとる
要件
- (3), (6) : 関数オブジェクト
binary_op
の呼び出しは、イテレータ範囲[first, last]
の要素変更およびイテレータの無効化をしてはならない
テンプレートパラメータ制約
- (2), (3), (5), (6) : 型
T
がstd::move_constructible
要件を満たすこと - (3), (6) : 以下の全ての演算結果の型が、型
T
に変換可能であることbinary_op(init, *first)
binary_op(*first, init)
binary_op(init, init)
binary_op(*first, *first)
効果
-
(1) : 以下と等価
return reduce(first, last, typename iterator_traits<InputIterator>::value_type{});
-
(2) : 以下と等価
return reduce(first, last, init, plus<>());
-
(3), (6) : イテレータ範囲
[first, last)
について、リスト[init, *first, *(first + 1), *(first + 2), ... *(first + (last - first - 1))]
を任意の部分リストへ分割し、各部分リストの要素を順不同にbinary_op(a, b)
を実行していき、それを実行していった結果同士も順不同にbinary_op(sum1, sum2)
のように集計して返す -
(4) : 以下と等価
return reduce(std::forward<ExecutionPolicy>(exec), first, last, typename iterator_traits<ForwardIterator>::value_type{});
-
(5) : 以下と等価
return reduce(std::forward<ExecutionPolicy>(exec), first, last, init, plus<>());
計算量
関数オブジェクトbinary_op
をO(last - first
)回だけ適用する
例
#include <iostream>
#include <vector>
#include <numeric>
int main()
{
const std::vector<int> v = {1, 2, 3, 4, 5};
// (1) : 合計値を求める
// イテレータの要素型で集計される
int sum = std::reduce(v.begin(), v.end());
std::cout << "sum : " << sum << std::endl;
// (2) : 合計値をlong long型として求める
// reduceの第3引数がlong long型のゼロを表す0LLになっていることに注意
// reduceの戻り値型は、第3引数の型となるため、変数sum_llの型はlong long
auto sum_ll = std::reduce(v.begin(), v.end(), 0LL);
std::cout << "sum_ll : " << sum_ll << std::endl;
// (3) : 任意の二項演算を行う
// ここでは、初期値を1として、全ての要素を掛け合わせている
int product = std::reduce(v.begin(), v.end(), 1, [](int acc, int i) {
return acc * i;
});
std::cout << "product : " << product << std::endl;
}
xxxxxxxxxx
#include <iostream>
#include <vector>
#include <numeric>
int main()
{
const std::vector<int> v = {1, 2, 3, 4, 5};
// (1) : 合計値を求める
// イテレータの要素型で集計される
int sum = std::reduce(v.begin(), v.end());
std::cout << "sum : " << sum << std::endl;
// (2) : 合計値をlong long型として求める
// reduceの第3引数がlong long型のゼロを表す0LLになっていることに注意
// reduceの戻り値型は、第3引数の型となるため、変数sum_llの型はlong long
auto sum_ll = std::reduce(v.begin(), v.end(), 0LL);
std::cout << "sum_ll : " << sum_ll << std::endl;
// (3) : 任意の二項演算を行う
// ここでは、初期値を1として、全ての要素を掛け合わせている
int product = std::reduce(v.begin(), v.end(), 1, [](int acc, int i) {
return acc * i;
});
std::cout << "product : " << product << std::endl;
}
出力
sum : 15
sum_ll : 15
product : 120
バージョン
言語
- C++17
処理系
- Clang: 5.0.0 ✅
- GCC:
- Visual C++: ??