|
| |
|
| 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 backward-compatibility header algo.h.
Requirements on types
For the first version:
-
InputIterator is a model of InputIterator.
-
OutputIterator is a model of OutputIterator.
-
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 InputIterator.
-
OutputIterator is a model of OutputIterator.
-
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
