4. partial_sum

最終更新日時(UTC):
が更新

履歴 編集

function template
<numeric>

std::partial_sum

namespace std {
  template <class InputIterator, class OutputIterator>
  OutputIterator
    partial_sum(InputIterator first,
                InputIterator last,
                OutputIterator result);    // (1) C++03
  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++03
  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++03まで : 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++03 :

    *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)

計算量

ちょうど(last - first) - 1回だけbinary_opを適用する

備考

この関数は、他の言語では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

参照