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 the standard header numeric, and in the nonstandard
backwardcompatibility header 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.
See also
adjacent_difference, accumulate, inner_product,
count
Copyright ©
1999 Silicon Graphics, Inc. All Rights Reserved.
TrademarkInformation
webmaster@www.sgi.com