std::inclusive_scan
ja.cppreference.net から
| ヘッダ <numeric>
|
||
template< class InputIt, class OutputIt >
OutputIt inclusive_scan( InputIt first, InputIt last,
OutputIt d_first );
|
で定義 (1) | (C++17 以上) (C++20 から constexpr) |
template< class ExecutionPolicy,
class ForwardIt1, class ForwardIt2 >
ForwardIt2 inclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 d_first );
|
(2) | (C++17 以上) |
template< class InputIt, class OutputIt, class BinaryOp >
OutputIt inclusive_scan( InputIt first, InputIt last,
OutputIt d_first, BinaryOp op );
|
(3) | (C++17 以上) (C++20 から constexpr) |
template< class ExecutionPolicy,
class ForwardIt1, class ForwardIt2, class BinaryOp >
ForwardIt2 inclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 d_first, BinaryOp op );
|
(4) | (C++17 以上) |
template< class InputIt, class OutputIt,
class BinaryOp, class T >
OutputIt inclusive_scan( InputIt first, InputIt last,
OutputIt d_first, BinaryOp op, T init );
|
(5) | (C++17 以上) (C++20 から constexpr) |
template< class ExecutionPolicy,
class ForwardIt1, class ForwardIt2,
class BinaryOp, class T >
ForwardIt2 inclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 d_first, BinaryOp op, T init );
|
(6) | (C++17 以上) |
1)
inclusive_scan(first, last, d_first, std::plus<>() と同等。3)
op を用いて包括的前置和を計算します。 各整数
i に対して [0, std::distance(first, last)) 内で、以下の操作を順に実行します：
[first,iter]の要素を順に並べてシーケンスを作成します。ここでiterはi番目のfirstの次のイテレータです。opに対するそのシーケンスの一般化された非可換和を計算します。- 結果を
*destに代入します。ここでdestはi番目のd_firstの次のイテレータです。
5) (3) と同じですが、作成される各シーケンスは
init の後に [first, iter] の要素を順に並べて形成されます。2,4,6) (1,3,5) と同じですが、
policy に従って実行されます。 これらのオーバーロードは、以下の式の値が
true である場合にのみオーバーロード解決に参加します：
|
|
(C++20 まで) |
|
|
(C++20 から) |
一般化された非可換和 は、二項演算 binary_op に対する要素のシーケンスに対して次のように定義されます：
- シーケンスに要素が1つしかない場合、和はその要素の値です。
- そうでない場合、以下の操作を順に実行します：
- シーケンスから任意の隣接する2つの要素
elem1とelem2を選択します。 binary_op(elem1, elem2)を計算し、その2つの要素を結果で置き換えます。- 要素が1つになるまでステップ1と2を繰り返します。
実際の二項演算を binary_op とします：
binary_opが結合的でない（浮動小数点数加算など）場合、結果は非決定的です。
- オーバーロード (1-4) で、
binary_op(*first, *first)が 値型 のdecltype(first)に変換可能でない場合、プログラムは ill-formed です。
- オーバーロード (5,6) で、以下の値のいずれかが
Tに変換可能でない場合、プログラムは ill-formed です：
binary_op(init, *first)binary_op(init, init)binary_op(*first, *first)
- 以下の条件のいずれかが満たされる場合、動作は未定義です：
- オーバーロード (1-4) で、
decltype(first)の値型が MoveConstructible でない。 - オーバーロード (5,6) で、
Tが MoveConstructible でない。 binary_op[first,last)の要素を変更する。binary_op[first,last]の任意のイテレータまたは部分範囲を無効にする。
- オーバーロード (1-4) で、
引数
| first, last | - | 加算する要素のソース 範囲 を定義するイテレータのペア |
| d_first | - | 書き込み先の 範囲 の先頭。first
|
| と等しくてもよい。 | policy | - 使用する 実行ポリシー |
| init | - | |
| 初期値 | op | -
二項 FunctionObjectop。入力イテレータの間接参照結果、他の init の結果、および（指定された場合） |
| に適用される。 | ||
型要件
InputIt- は LegacyInputIterator | ||
の要件を満たさなければならない。
OutputIt- は LegacyOutputIterator | ||
の要件を満たさなければならない。
ForwardIt1, ForwardIt2- は LegacyForwardIterator | ||
の要件を満たさなければならない。
戻り値
最後に書き込んだ要素の次の要素を指すイテレータ。
計算量N を std::distance(first, last) とする：
1,2) O(N) 回の
std::plus<>() の適用。3-6) O(N) 回の
op の適用。例外
ExecutionPolicy という名前のテンプレート引数を持つオーバーロードは、次のようにエラーを報告します：
- アルゴリズムの一部として呼び出された関数が例外を投げ、
ExecutionPolicyが 標準ポリシー のいずれかである場合、std::terminate が呼び出されます。その他のExecutionPolicyについては、動作は処理系定義です。 - アルゴリズムがメモリの確保に失敗した場合、std::bad_alloc がスローされます。
例
このコードを実行
#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
int main()
{
std::vector data{3, 1, 4, 1, 5, 9, 2, 6};
std::cout << "Exclusive sum: ";
std::exclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
0);
std::cout << "\nInclusive sum: ";
std::inclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n\nExclusive product: ";
std::exclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
1, std::multiplies<>{});
std::cout << "\nInclusive product: ";
std::inclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
std::multiplies<>{});
}
出力：
Exclusive sum: 0 3 4 8 9 14 23 25
Inclusive sum: 3 4 8 9 14 23 25 31
Exclusive product: 1 3 3 12 12 60 540 1080
Inclusive product: 3 3 12 12 60 540 1080 6480
関連項目
| 範囲内の隣接要素間の差を計算します (関数テンプレート) | |
| 範囲内の要素を加算または畳み込みます (関数テンプレート) | |
| 範囲内の要素の部分和を計算します (関数テンプレート) | |
(C++17) |
呼び出し可能オブジェクトを適用し、その後包括的スキャンを計算します (関数テンプレート) |
(C++17) |
std::partial_sum と似ていますが、i番目の 和から i番目の 入力要素を除外します (関数テンプレート) |