名前空間
変種
操作

std::partial_sum

提供: cppreference.com
< cpp‎ | algorithm
 
 
アルゴリズムライブラリ
実行ポリシー (C++17)
非変更シーケンス操作
(C++11)(C++11)(C++11)
(C++17)
変更シーケンス操作
未初期化記憶域の操作
分割操作
ソート操作
(C++11)
二分探索操作
集合操作 (ソート済み範囲用)
ヒープ操作
(C++11)
最小/最大演算
(C++11)
(C++17)
順列
数値演算
partial_sum
C のライブラリ
 
ヘッダ <numeric> で定義
template< class InputIt, class OutputIt >
OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );
(1)
template< class InputIt, class OutputIt, class BinaryOperation >

OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first,

                      BinaryOperation op );
(2)

範囲 [first, last) の部分範囲の部分和を計算し、それらを d_first から始まる範囲に書き込みます。 1つめのバージョンは要素を加算するために operator+ を使用し、2つめのバージョンは指定された二項関数を使用します。 どちらの場合も、左側の被演算子に std::move が適用されます。 (C++20およびそれ以降)

以下の操作と同等です。

*(d_first)   = *first;
*(d_first+1) = *first + *(first+1);
*(d_first+2) = *first + *(first+1) + *(first+2);
*(d_first+3) = *first + *(first+1) + *(first+2) + *(first+3);
...

op は副作用を持っていてはなりません。

(C++11以前)

op は終端イテレータを含むいかなるイテレータも無効化してはならず、影響のある範囲のいかなる要素も変更してはなりません。

(C++11およびそれ以降)

目次

[編集] 引数

first, last - 加算する要素の範囲
d_first - 書き込み先範囲の先頭。 first と等しくても構いません
op - 適用される二項演算関数オブジェクト。

関数のシグネチャは以下と同等であるべきです。

 Ret fun(const Type1 &a, const Type2 &b);

シグネチャが const & を持つ必要はありません。
Type1 は、 iterator_traits<InputIt>::value_type 型のオブジェクトから暗黙に変換可能なものでなければなりません。 型 Type2 は、 InputIt 型のオブジェクトの逆参照から暗黙に変換可能なものでなければなりません。 型 Retiterator_traits<InputIt>::value_type 型のオブジェクトに代入可能なものでなければなりません。 ​

型の要件
-
InputItInputIterator の要件を満たさなければなりません。
-
OutputItOutputIterator の要件を満たさなければなりません。

[編集] 戻り値

最後に書き込まれた要素の次の要素を指すイテレータ。

[編集] 計算量

ちょうど (last - first) - 1 回の二項演算の適用。

[編集] 実装例

1つめのバージョン
template<class InputIt, class OutputIt>
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<>());
}
2つめのバージョン
template<class InputIt, class OutputIt, class BinaryOperation>
OutputIt partial_sum(InputIt first, InputIt last, 
                     OutputIt d_first, BinaryOperation op)
{
    if (first == last) return d_first;
 
    typename std::iterator_traits<InputIt>::value_type sum = *first;
    *d_first = sum;
 
    while (++first != last) {
       sum = op(std::move(sum), *first); // std::move since C++20
       *++d_first = sum;
    }
    return ++d_first;
}

[編集]

#include <numeric>
#include <vector>
#include <iostream>
#include <iterator>
#include <functional>
 
int main()
{
    std::vector<int> v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}; // or std::vector<int>v(10, 2);
 
    std::cout << "The first 10 even numbers are: ";
    std::partial_sum(v.begin(), v.end(), 
                     std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    std::partial_sum(v.begin(), v.end(), v.begin(), std::multiplies<int>());
    std::cout << "The first 10 powers of 2 are: ";
    for (auto 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

[編集] 関連項目

指定範囲の隣接する要素間の差を計算します
(関数テンプレート) [edit]
指定範囲の要素を合計します
(関数テンプレート) [edit]
std::partial_sum と同様ですが、計算順序は不定です
(関数テンプレート) [edit]
std::inclusive_scan と同様ですが、 i 番目の合計に i 番目の要素が含まれません
(関数テンプレート) [edit]