Compute partial sums of one sequence into another sequence

Source code

Declaration

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   From the sequence in the range [ first, last) , the first partial_sum  function generates the sequence , , , ...,

and the second partial_sum  function generates the sequence , , , ...,

.

For both functions, the resulting sequence is placed into the range of size n beginning at the location referenced by result. An iterator referring to the past-the-end  location of the result sequence is returned.

To generate the partial sums   in just one sequence, result should be the beginning of the same sequence as first.

Type requirements

• InputIterator must be at least an input iterator .
• OutputIterator must be at least an output iterator .
• BinaryOperation must be a function object type that provides T operator()(T, T), where T is the dereference type of InputIterator.

Group Generalized numeric operations.

Time complexity Linear.

The number of applications of operator+ or the function object op is one less than the size of the range [ first, last) .

Space complexity Constant.

Mutative? Yes.

Details Assumes that binary_op does not cause side effects .

Glossary terms BinaryOperation, constant space, dereference type, function object, function object type, InputIterator, iterator, linear time, mutative, operator+, OutputIterator, past-the-end iterator, partial sums, range, sequence, side effect.

Example Select here to view the source code for the example.

Implementation Select here to view source code (Copyright (C) 1994, Hewlett-Packard Company) for this algorithm.