std::reduce
提供: cppreference.com
ヘッダ <numeric> で定義 | ||
template<class InputIt> typenamestd::iterator_traits<InputIt>::value_type reduce( | (1) | (C++17およびそれ以降) |
template<class ExecutionPolicy, class ForwardIt> typenamestd::iterator_traits<ForwardIt>::value_type reduce( | (2) | (C++17およびそれ以降) |
template<class InputIt, class T> T reduce(InputIt first, InputIt last, T init); | (3) | (C++17およびそれ以降) |
template<class ExecutionPolicy, class ForwardIt, class T> T reduce(ExecutionPolicy&& policy, | (4) | (C++17およびそれ以降) |
template<class InputIt, class T, class BinaryOp> T reduce(InputIt first, InputIt last, T init, BinaryOp binary_op); | (5) | (C++17およびそれ以降) |
template<class ExecutionPolicy, class ForwardIt, class T, class BinaryOp> T reduce(ExecutionPolicy&& policy, | (6) | (C++17およびそれ以降) |
1)reduce(first, last, typenamestd::iterator_traits<InputIt>::value_type{}) と同じです。
3)reduce(first, last, init, std::plus<>()) と同じです。
5)
binary_op と初期値 init を用いて、場合によっては未規定の方法で並べ替えたり集約したりしながら、範囲 [first; last) を縮小します。 2,4,6)(1,3,5) と同じですが、
policy に従って実行されます。 このオーバーロードは、std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> が true である場合にのみ、オーバーロード解決に参加します。binary_op が交換法則や結合法則を満たさない場合、動作は非決定的になります。
binary_op が終端イテレータを含む [first; last] 内のいずれかのイテレータを無効化したり、いずれかの要素を変更したりした場合、動作は未定義です。
目次 |
[編集]引数
| first, last | - | アルゴリズムを適用する要素の範囲 |
| init | - | 一般化された合計の初期値 |
| policy | - | 使用する実行ポリシー。 詳細は実行ポリシーを参照してください |
| binary_op | - | 入力イテレータを逆参照した結果、他の binary_op の結果、および init に未規定の順序で適用される二項 FunctionObject |
| 型の要件 | ||
-InputIt は InputIterator の要件を満たさなければなりません。 | ||
-ForwardIt は ForwardIterator の要件を満たさなければなりません。 | ||
-T は MoveConstructible の要件を満たさなければなりません。 また、 binary_op(init, *first)、 binary_op(*first, init)、 binary_op(init, init) および binary_op(*first, *first) は T に変換可能でなければなりません。 | ||
[編集]戻り値
init, *first, *(first+1), ... *(last-1) の binary_op による一般化された合計。
ただし一般化された合計 GSUM(op, a
1, ..., a
N) は以下のように定義されます。
- N=1 であれば、結果は a
1 です。 - N > 1 であれば、結果は op(GSUM(op, b
1, ..., b
K), GSUM(op, b
M, ..., b
N)) です。 ただし、
- b
1, ..., b
N は a1, ..., aN の任意の順列であってもよく、 - 1 < K+1 = M ≤ N です。
- b
別の言い方をすると、 reduce は std::accumulate と似た動作をしますが、範囲内の要素は適当な順序でグループ化されたり並べ替えられたりすることがあります。
[編集]計算量
O(last - first) 回の binary_op の適用。
[編集]例外
テンプレート引数 ExecutionPolicy を持つオーバーロードは以下のようにエラーを報告します。
- アルゴリズムの一部として呼び出された関数の実行が例外を投げ、
ExecutionPolicyが3つの標準のポリシーのいずれかの場合は、 std::terminate が呼ばれます。 それ以外のあらゆるExecutionPolicyについては、動作は処理系定義です。 - アルゴリズムがメモリの確保に失敗した場合は、 std::bad_alloc が投げられます。
[編集]ノート
範囲が空の場合は、 init が変更されずに返されます。
[編集]例
reduce と std::accumulate を並べて比較します。
Run this code
#include <iostream>#include <chrono>#include <vector>#include <numeric>#include <execution> int main(){std::vector<double> v(10'000'007, 0.5); {auto t1 = std::chrono::high_resolution_clock::now();double result =std::accumulate(v.begin(), v.end(), 0.0);auto t2 = std::chrono::high_resolution_clock::now();std::chrono::duration<double, std::milli> ms = t2 - t1;std::cout<<std::fixed<<"std::accumulate result "<< result <<" took "<< ms.count()<<" ms\n";} {auto t1 = std::chrono::high_resolution_clock::now();double result = std::reduce(std::execution::par, v.begin(), v.end());auto t2 = std::chrono::high_resolution_clock::now();std::chrono::duration<double, std::milli> ms = t2 - t1;std::cout<<"std::reduce result "<< result <<" took "<< ms.count()<<" ms\n";}}
出力例:
std::accumulate result 5000003.50000 took 12.7365 ms std::reduce result 5000003.50000 took 5.06423 ms
[編集]関連項目
| 指定範囲の要素を合計します (関数テンプレート) | |
| 指定範囲の要素に関数を適用します (関数テンプレート) | |
(C++17) | 不定の計算順序で、関数オブジェクトを適用した結果を reduce します (関数テンプレート) |
