partial_sum


Category: algorithms	Component type: function

Prototype

Partial_sum is an overloaded name; there are actually two partial_sum functions.

template <class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator first, InputIterator last,
                           OutputIterator result);

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

Description

Partial_sum calculates a generalized partial sum: *first is assigned to *result, the sum of *first and *(first + 1) is assigned to *(result + 1), and so on. [1]

More precisely, a running sum is first initialized to *first and assigned to *result. For each iterator i in [first + 1, last), in order from beginning to end, the sum is updated by sum = sum + *i (in the first version) or sum = binary_op(sum, *i) (in the second version) and is assigned to *(result + (i - first)). [2]

Definition

Defined in algo.h.

Requirements on types

For the first version:

InputIterator is a model of Input Iterator.
OutputIterator is a model of Output Iterator.
If x and y are objects of InputIterator's value type, then x + y is defined.
The return type of x + y is convertible to InputIterator's value type.
InputIterator's value type is convertible to a type in OutputIterator's set of value types.

For the second version:

InputIterator is a model of Input Iterator.
OutputIterator is a model of Output Iterator.
BinaryFunction is a model of BinaryFunction.
InputIterator's value type is convertible to BinaryFunction's first argument type and second argument type.
BinaryFunction's result type is convertible to InputIterator's value type.
InputIterator's value type is convertible to a type in OutputIterator's set of value types.

Preconditions

[first, last) is a valid range.
[result, result + (last - first)) is a valid range.

Complexity

Linear. Zero applications of the binary operation if [first, last) is a empty range, otherwise exactly (last - first) - 1 applications.

Example

int main()
{
  const int N = 10;
  int A[N];

  fill(A, A+N, 1);
  cout << "A:                 ";
  copy(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;

  cout << "Partial sums of A: ";
  partial_sum(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;
}

Notes

[1] Note that result is permitted to be the same iterator as first. This is useful for computing partial sums "in place".

[2] The binary operation is not required to be either associative or commutative: the order of all operations is specified.