| |
|
Category: algorithms | | Component type: function |
Prototype
Accumulate
is an overloaded name; there are actually two accumulate
functions.
template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init);
template <class InputIterator, class T, class BinaryFunction>
T accumulate(InputIterator first, InputIterator last, T init,
BinaryFunction binary_op);
Description
Accumulate
is a generalization of summation: it computes the sum (or some other binary operation) of init
and all of the elements in the range [first, last)
. [1]
The functors binary_op
is not required to be either commutative or associative: the order of all of accumulate
's operations is specified. The result is first initialized to init
. Then, for each iterator i
in [first, last)
, in order from beginning to end, it is updated by result = result + *i
(in the first version) or result = binary_op(result, *i)
(in the second version).
Definition
Defined in the standard header numeric, and in the nonstandard backward-compatibility header algo.h.
Requirements on types
For the first version, the one that takes two arguments:
-
InputIterator
is a model of InputIterator.
-
T
is a model of Assignable.
-
If
x
is an object of type T
and y
is an object of InputIterator
's value type, then x + y
is defined.
-
The return type of
x + y
is convertible to T
.
For the second version, the one that takes three arguments:
-
InputIterator
is a model of InputIterator.
-
T
is a model of Assignable.
-
BinaryFunction
is a model of BinaryFunction.
-
T
is convertible to BinaryFunction
's first argument type.
-
The value type of
InputIterator
is convertible to BinaryFunction
's second argument type.
-
BinaryFunction
's return type is convertible to T
.
Preconditions
-
[first, last)
is a valid range.
Complexity
Linear. Exactly last - first
invocations of the binary operation.
Example
int main()
{
int A[] = {1, 2, 3, 4, 5};
const int N = sizeof(A) / sizeof(int);
cout << "The sum of all elements in A is "
<< accumulate(A, A + N, 0)
<< endl;
cout << "The product of all elements in A is "
<< accumulate(A, A + N, 1, multiplies<int>())
<< endl;
}
Notes
[1] There are several reasons why it is important that accumulate
starts with the value init
. One of the most basic is that this allows accumulate
to have a well-defined result even if [first, last)
is an empty range: if it is empty, the return value is init
. If you want to find the sum of all of the elements in [first, last)
, you can just pass 0
as init
.
See also
inner_product
, partial_sum
, adjacent_difference
, count