4. partial_sum

    • Class / Function / Type

      std::

    • Header file

      <>

    • Other / All

    crsearch v3.0.23

    最終更新日時(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

    関連項目

    参照