Accumulate all elements in a sequence

Source code

Declaration

template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init);

template <class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init,
             BinaryOperation binary_op);

Description    For the sequence in the range [ first, last) , the first accumulate  function returns

and the second accumulate  function returns . The first function may be used to sum  the elements in a sequence, and the second function may be used more generally to accumulate  the elements of a sequence using some binary function.

Type requirements

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

Group Generalized numeric operations.

Time complexity Linear.

The number of applications of operator+ or the function object binary_op is n, where n is the size of the range [ first, last) .

Space complexity Constant.

Mutative? No.

Details Returns init if first = last. 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+, 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.

Implementation notes accumulate  is similar to the APL reduction  operator and the Common Lisp reduce  function, but it avoids the difficulty of defining the result of reduction  on an empty sequence  by always requiring an initial value.

Accumulation   is done by adding  each value (or performing the specified binary operation), in order, to the initial value to create a modified initial value.