Compute a sequence from its partial sums into another sequence

Source code

Declaration

template <class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last,
                                   OutputIterator result);

template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator adjacent_difference(InputIterator first, InputIterator last,
                                   OutputIterator result,
                                   BinaryOperation binary_op);

Description   From the sequence in the range [ first, last) , the first adjacent_difference  function generates the sequence , , , ...,

and the second adjacent_difference  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 original sequence from the sequence of 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 S operator()(T, T), where T and S are the dereference types of InputIterator and OutputIterator, respectively.

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.