std::reduce
提供: cppreference.com
| ヘッダ <numeric> で定義
|
||
| (1) | ||
| template<class InputIt> typename std::iterator_traits<InputIt>::value_type reduce( |
(C++17以上) (C++20未満) |
|
| template<class InputIt> constexpr typename std::iterator_traits<InputIt>::value_type reduce( |
(C++20以上) | |
| template<class ExecutionPolicy, class ForwardIt> typename std::iterator_traits<ForwardIt>::value_type reduce( |
(2) | (C++17以上) |
| (3) | ||
| template<class InputIt, class T> T reduce(InputIt first, InputIt last, T init); |
(C++17以上) (C++20未満) |
|
| template<class InputIt, class T> constexpr T reduce(InputIt first, InputIt last, T init); |
(C++20以上) | |
| template<class ExecutionPolicy, class ForwardIt, class T> T reduce(ExecutionPolicy&& policy, |
(4) | (C++17以上) |
| (5) | ||
| template<class InputIt, class T, class BinaryOp> T reduce(InputIt first, InputIt last, T init, BinaryOp binary_op); |
(C++17以上) (C++17未満) |
|
| template<class InputIt, class T, class BinaryOp> constexpr T reduce(InputIt first, InputIt last, T init, BinaryOp binary_op); |
(C++17以上) | |
| template<class ExecutionPolicy, class ForwardIt, class T, class BinaryOp> T reduce(ExecutionPolicy&& policy, |
(6) | (C++17以上) |
1) reduce(first, last, typename std::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 は LegacyInputIterator の要件を満たさなければなりません。
| ||
-ForwardIt は LegacyForwardIterator の要件を満たさなければなりません。
| ||
-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が標準のポリシーのいずれかの場合は、 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 します (関数テンプレート) |
