std::partial_sum

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

sum (1)

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

custom (2)

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

Compute partial sums of range

Assigns to every element in the range starting at result the partial sum of the corresponding elements in the range [first,last).

If x represents an element in [first,last) and y represents an element in result, the ys can be calculated as:


y₀ = x₀ 

y₁ = x₀ + x₁ 

y₂ = x₀ + x₁ + x₂ 

y₃ = x₀ + x₁ + x₂ + x₃ 

y₄ = x₀ + x₁ + x₂ + x₃ + x₄ 

 ... ... ...

The default operation is to add the elements up, but a different operation can be specified as binary_op instead.

The behavior of this function template is equivalent to:

template <class InputIterator, class OutputIterator>
   OutputIterator partial_sum (InputIterator first, InputIterator last,
                               OutputIterator result)
{
  if (first!=last) {
    typename iterator_traits<InputIterator>::value_type val = *first;
    *result = val;
    while (++first!=last) {
      val = val + *first;   // or: val = binary_op(val,*first)
      *++result = val;
    }
    ++result;
  }
  return result;
}

Parameters

first, last: Input iterators to the initial and final positions in a sequence. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
result: Output iterator to the initial position in the destination sequence where the partial sums are stored. The range starts at result and shall have a size large enough to contain as many elements as the range above ([first,last)).
binary_op: Binary operation taking two elements of the type pointed by the InputIterator as arguments, and returning the result of the replacement for the sum operation.
This can either be a function pointer or a function object.

Return value

An iterator pointing to past the last element of the destination sequence where resulting elements have been stored, or result if [first,last) is an empty range.

Example

// partial_sum example
#include <iostream>     // std::cout
#include <functional>   // std::multiplies
#include <numeric>      // std::partial_sum

int myop (int x, int y) {return x+y+1;}

int main () {
  int val[] = {1,2,3,4,5};
  int result[5];

  std::partial_sum (val, val+5, result);
  std::cout << "using default partial_sum: ";
  for (int i=0; i<5; i++) std::cout << result[i] << ' ';
  std::cout << '\n';

  std::partial_sum (val, val+5, result, std::multiplies<int>());
  std::cout << "using functional operation multiplies: ";
  for (int i=0; i<5; i++) std::cout << result[i] << ' ';
  std::cout << '\n';

  std::partial_sum (val, val+5, result, myop);
  std::cout << "using custom function: ";
  for (int i=0; i<5; i++) std::cout << result[i] << ' ';
  std::cout << '\n';
  return 0;
}

Output:


using default partial_sum: 1 3 6 10 15
using functional operation multiplies: 1 2 6 24 120
using custom function: 1 4 8 13 19

Complexity

Linear in the distance between first and last, minus one (in number of additions or applications of binary_op).

Data races

The elements in the range [first,last) are accessed (each object is accessed exactly once).
The elements in the range beginning at result are modified.

Exceptions

Throws if any of binary_op, the assignments or an operation on an iterator throws.
Note that invalid arguments cause undefined behavior.