std::partial_sum

ヘッダー `<numeric>` で定義
template< class InputIt, class OutputIt > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );	(1)	(C++20 以降 constexpr)
template< class InputIt, class OutputIt, class BinaryOp > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first, BinaryOp op );	(2)	(C++20 以降 constexpr)

1) [first, last)が空の場合、何も行いません。

それ以外の場合は、以下の操作を順番に実行します。

アキュムレータ acc を作成します。この型は InputIt の値型であり、*first で初期化されます。
acc を *d_first に代入します。
[1, std::distance(first, last)) の各整数 i について、以下の操作を順番に実行します。

a) iter を first の次の i 番目のイテレータとして、acc + *iter(until C++20)std::move(acc) + *iter(since C++20) を計算します。

b) 結果を acc に代入します。

c) dest を d_first の次の i 番目のイテレータとして、acc^[1] を *dest に代入します。

2) (1) と同じですが、op(acc, *iter)(until C++20)op(std::move(acc), *iter)(since C++20) の代わりに、op(acc, *iter)(until C++20)op(std::move(acc), *iter)(since C++20) を計算します。

実際のバイナリ操作として binary_op が与えられた場合

以下のいずれかの条件が満たされる場合、プログラムは不適格です。

InputIt の値型は *first から構築できません。
acc は d_first に書き込み可能ではありません。
binary_op(acc, *iter)(until C++20)binary_op(std::move(acc), *iter)(since C++20) の結果は、InputIt の値型に暗黙的に変換可能ではありません。

返される d_last を、以下のいずれかの条件が満たされた場合、動作は未定義です。

binary_op は、[first, last) または [d_first, d_last) のいずれかの要素を変更します。
binary_op は、[first, last] または [d_first, d_last] のいずれかのイテレータまたはサブ範囲を無効にします。

↑ 実際に代入される値は、前のステップでの代入の結果です。ここでは代入結果を acc と仮定します。

first, last	-	合計する要素の範囲を定義するイテレーターのペア
d_first	-	デスティネーション範囲の先頭。first と同じでもよい
op	-	適用される二項演算関数オブジェクト。関数のシグネチャは以下と同等である必要があります。 Ret fun(const Type1 &a, const Type2 &b); シグネチャは const & を持つ必要はありません。型 Type1 は、std::iterator_traits<InputIt>::value_type のオブジェクトが Type1 に暗黙的に変換可能でなければなりません。型 Type2 は、`InputIt` のオブジェクトをデリファレンスし、その結果を Type2 に暗黙的に変換可能でなければなりません。型 Ret は、`InputIt` のオブジェクトをデリファレンスし、型 Ret の値を代入可能でなければなりません。
型要件
- `InputIt` は LegacyInputIterator の要件を満たす必要があります。
- `OutputIt` は LegacyOutputIterator の要件を満たさなければなりません。

[編集] Return value

書き込まれた最後の要素の次の要素を指すイテレータ。ただし、[first, last) が空の場合は d_first を返します。

[編集] Complexity

std::distance(first, last) を $\scriptsize N$ $N$ とする

1)

N-1

回の operator+ の適用。

2) 二項関数 op の

N-1

回の適用。

[編集] Possible implementation

partial_sum (1)

template<class InputIt, class OutputIt>
constexpr // since C++20
OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first)
{
    if (first == last)
        return d_first;
 
    typename std::iterator_traits<InputIt>::value_type sum = *first;
    *d_first = sum;
 
    while (++first != last)
    {
        sum = std::move(sum) + *first; // std::move since C++20
        *++d_first = sum;
    }
 
    return ++d_first;
 
    // or, since C++14:
    // return std::partial_sum(first, last, d_first, std::plus<>());
}

partial_sum (2)

template<class InputIt, class OutputIt, class BinaryOp>
constexpr // since C++20
OutputIt partial_sum(InputIt first, InputIt last, 
                     OutputIt d_first, BinaryOp op)
{
    if (first == last)
        return d_first;
 
    typename std::iterator_traits<InputIt>::value_type acc = *first;
    *d_first = acc;
 
    while (++first != last)
    {
        acc = op(std::move(acc), *first); // std::move since C++20
        *++d_first = acc;
    }
 
    return ++d_first;
}

[編集] Notes

acc は、LWG issue 539 の解決により導入されました。結果を直接合計する（つまり *(d_first + 2) = (*first + *(first + 1)) + *(first + 2);）のではなく acc を使用する理由は、以下の型が一致しない場合に後者の意味が不明瞭になるためです。

InputIt の値型
OutputIt の書き込み可能な型
operator+ または op のパラメータの型
operator+ または op の戻り値の型

acc は、計算の各ステップの値の格納と提供を行う中間オブジェクトとして機能します。

その型は InputIt の値型です。
d_first に書き込まれます。
その値は operator+ または op に渡されます。
operator+ または op の戻り値を格納します。

enum not_int { x = 1, y = 2 };
 
char i_array[4] = {100, 100, 100, 100};
not_int e_array[4] = {x, x, y, y};
int  o_array[4];
 
// OK: uses operator+(char, char) and assigns char values to int array
std::partial_sum(i_array, i_array + 4, o_array);
 
// Error: cannot assign not_int values to int array
std::partial_sum(e_array, e_array + 4, o_array);
 
// OK: performs conversions when needed
// 1. creates “acc” of type char (the value type)
// 2. the char arguments are used for long multiplication (char -> long)
// 3. the long product is assigned to “acc” (long -> char)
// 4. “acc” is assigned to an element of “o_array” (char -> int)
// 5. go back to step 2 to process the remaining elements in the input range
std::partial_sum(i_array, i_array + 4, o_array, std::multiplies<long>{});

[編集] Example

このコードを実行

#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
 
int main()
{
    std::vector<int> v(10, 2); // v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}
 
    std::cout << "The first " << v.size() << " even numbers are: ";
    // write the result to the cout stream
    std::partial_sum(v.cbegin(), v.cend(), 
                     std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    // write the result back to the vector v
    std::partial_sum(v.cbegin(), v.cend(),
                     v.begin(), std::multiplies<int>());
 
    std::cout << "The first " << v.size() << " powers of 2 are: ";
    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

出力

The first 10 even numbers are: 2 4 6 8 10 12 14 16 18 20 
The first 10 powers of 2 are: 2 4 8 16 32 64 128 256 512 1024

[編集] Defect reports

以下の動作変更を伴う欠陥報告が、以前に公開されたC++標準に遡って適用されました。

DR	適用対象	公開された動作	正しい動作
LWG 242	C++98	op には副作用があってはなりません。	関連する範囲を変更できません。
LWG 539	C++98	結果に必要な型要件評価と代入が有効であるための要件が欠落していました。	追加された

[編集] See also

adjacent_difference	範囲内の隣接する要素間の差を計算する (関数テンプレート) [編集]
accumulate	範囲の要素を合計または畳み込む (関数テンプレート) [編集]
inclusive_scan (C++17)	std::partial_sum と同様で、 $i$ 番目の入力要素を $i$ 番目の合計に含めます。 (関数テンプレート) [編集]
exclusive_scan (C++17)	std::partial_sum と同様で、 $i$ 番目の入力要素を $i$ 番目の合計から除外します。 (関数テンプレート) [編集]

[1] 実際に代入される値は、前のステップでの代入の結果です。ここでは代入結果を acc と仮定します。

[1]

コンパイラサポート
フリースタンディングとホスト
言語
標準ライブラリ
標準ライブラリヘッダー
名前付き要件
機能テストマクロ (C++20)
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
メモリ管理ライブラリ
メタプログラミングライブラリ (C++11)
汎用ユーティリティライブラリ
コンテナライブラリ
イテレータライブラリ
Rangesライブラリ (C++20)
アルゴリズムライブラリ
文字列ライブラリ
テキスト処理ライブラリ
数値ライブラリ
日付と時刻ライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
並行サポートライブラリ (C++11)
実行制御ライブラリ (C++26)
Technical specifications (技術仕様)
シンボルインデックス
外部ライブラリ

cppreference.com

名前空間

変種

表示

操作