Skip to content

Latest commit

 

History

History
144 lines (111 loc) · 4.61 KB

partial_sum.md

File metadata and controls

144 lines (111 loc) · 4.61 KB
Raw

partial_sum

  • numeric[meta header]
  • std[meta namespace]
  • function template[meta id-type]
namespace std {
  template <class InputIterator, class OutputIterator>
    OutputIterator partial_sum(
      InputIterator first, InputIterator last,
      OutputIterator result);                              // (1)

  template <class InputIterator, class OutputIterator, class BinaryOperation>
      OutputIterator partial_sum(
        InputIterator first, InputIterator last,
        OutputIterator result, BinaryOperation binary_op); // (2)
}

概要

範囲の値の部分和を計算する。

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)))が書き込まれる
    • std::move[link /reference/utility/move.md]

戻り値

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);
  }
}
  • std::partial_sum[color ff0000]
  • ar.begin()[link /reference/array/array/begin.md]
  • ar.end()[link /reference/array/array/end.md]
  • result.begin()[link /reference/array/array/begin.md]

出力

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

参照