namespace std {
  template <class InputIterator, class OutputIterator>
  OutputIterator
    partial_sum(InputIterator first,
                InputIterator last,
                OutputIterator result);    // (1) C++98
  template <class InputIterator, class OutputIterator>
  constexpr OutputIterator
    partial_sum(InputIterator first,
                InputIterator last,
                OutputIterator result);    // (1) C++20

  template <class InputIterator, class OutputIterator, class BinaryOperation>
  OutputIterator
    partial_sum(InputIterator first,
               InputIterator last,
               OutputIterator result,
               BinaryOperation binary_op); // (2) C++98
  template <class InputIterator, class OutputIterator, class BinaryOperation>
  constexpr OutputIterator
    partial_sum(InputIterator first,
               InputIterator last,
               OutputIterator result,
               BinaryOperation binary_op); // (2) C++20
}

概要

イテレータ範囲[first, last)の値の部分和を計算する。

accumulate()は最終結果のみを得るが、partial_sum()は計算の途中結果のシーケンスを得る。

partial_sum()の引数としてシーケンス{0, 1, 2, 3}が与えられた場合、以下のような計算が行われる：

// 計算の経過
{
  0,            // (1)
  0 + 1,        // (2)
  0 + 1 + 2,    // (3)
  0 + 1 + 2 + 3 // (4)
}

そして最終的に、以下のシーケンスが結果として出力される：

{0, 1, 3, 6}

出力イテレータresultには、そのシーケンスが書き込まれる。

2項演算の関数オブジェクトbinary_opには、第1引数として現在の集積値が渡され(「計算の経過」の(3)では、0 + 1した結果の1が渡される)、第2引数として新たに集積する値が渡される(「計算の経過」の(3)では、2が渡される)。

• (1) : 値を集積する方法として、binary_opをデフォルトでoperator+とする
• (2) : 値を集積する方法をbinary_opとして、任意にユーザーが決定する

要件

• C++98まで : binary_opを呼び出した結果として、いかなる副作用も起こしてはならない
• C++11から : InputIteratorの値型は、*firstの型から構築可能でなければならない
• C++11から : binary_opの戻り値が、InputIteratorの値型に変換可能でなければならない
• C++11から : binary_opの戻り値が、result出力イテレータに書き込めなければならない
• C++11から : binary_opは入力イテレータ範囲[first, last]および出力イテレータ範囲[result, result + (last - first)]の要素を変更してはならず、そのイテレータと部分範囲を無効化してはならない

効果

• (1) : binary_opをoperator+として、(2)の演算を行う

• (2) : 出力結果のイテレータ範囲[result, result + (last - first))には、以下が書き込まれる：

  • C++98 :

  *firstが書き込まれる                             // (1)
  binary_op(*first, *(first + 1))が書き込まれる    // (2)
  binary_op((2)の結果, *(first + 2))が書き込まれる // (3)
  binary_op((3)の結果, *(first + 3))が書き込まれる // (4)
  …
  binary_op((N-2)の結果, *(first + (N-1)))が書き込まれる
  

  • C++20 :

  *firstが書き込まれる                                        // (1)
  binary_op(std::move(*first), *(first + 1))が書き込まれる    // (2)
  binary_op(std::move((2)の結果), *(first + 2))が書き込まれる // (3)
  binary_op(std::move((3)の結果), *(first + 3))が書き込まれる // (4)
  …
  binary_op(std::move((N-2)の結果), *(first + (N-1)))が書き込まれる
  

戻り値

result + (last - first)

計算量

ちょうどmax((last - first) - 1, 0)回だけ2項演算を適用する

備考

この関数は、他の言語ではscanという名前で提供されている。

例

#include <numeric>
#include <iostream>
#include <array>

template <class Range>
void print(const Range& r)
{
  for (const auto& x : r) {
    std::cout << x << " --> ";
  }
  std::cout << "end" << std::endl;
}

int main()
{
  const std::array<double, 5> ar = {.0,.2,.4,.6,.8};

  {
    std::array<double, 5> result;
    std::partial_sum(ar.begin(), ar.end(), result.begin());
    print(result);
  }

  {
    std::array<double, 5> result;
    std::partial_sum(ar.begin(), ar.end(), result.begin(),
                       [](double a, double b) { return 2 * a - b; });
    print(result);
  }
}

出力

0 --> 0.2 --> 0.6 --> 1.2 --> 2 --> end
0 --> -0.2 --> -0.8 --> -2.2 --> -5.2 --> end

関連項目

• std::inclusive_scan()
• std::exclusive_scan()

参照

• P0616R0 De-pessimize legacy <numeric> algorithms with std::move
• P1645R1 constexpr for <numeric> algorithms
  • C++20で、並列バージョン以外の数値計算アルゴリズムがconstexpr対応した
• LWG Issue 539. partial_sum and adjacent_difference should mention requirements
  • C++11で、アキュムレータを用いた効果の規定へ整理され、要件が明記された。あわせて計算量がmax((last - first) - 1, 0)となり、空の範囲に対して負の回数とならないよう修正された（編集上の誤りの訂正であり、実際の挙動は変わらない）