adjacent_difference


Category: algorithms	Component type: function

Prototype

Adjacent_difference is an overloaded name; there are actually two adjacent_difference functions.

template <class InputIterator
class OutputIterator>
OutputIterator adjacent_difference(InputIterator first
InputIterator last

                                   OutputIterator result);

template <class InputIterator
class OutputIterator
class BinaryFunction>
OutputIterator adjacent_difference(InputIterator first
InputIterator last

                                   OutputIterator result

                                   BinaryFunction binary_op);

Description

Adjacent_difference calculates the differences of adjacent elements in the range [first last). This is *first is assigned to *result [1] and for each iterator i in the range [first + 1 last) the difference of *i and *(i - 1) is assigned to *(result + (i - first)). [2]

The first version of adjacent_difference uses operator- to calculate differences and the second version uses a user-supplied binary function. In the first version for each iterator i in the range [first + 1 last) *i - *(i - 1) is assigned to *(result + (i - first)). In the second version the value that is assigned to *(result + 1) is instead binary_op(*i *(i - 1)).

Definition

Defined in the standard header numeric and in the nonstandard backward-compatibility header algo.h.

Requirements on types

For the first version:

ForwardIterator is a model of Forward Iterator.
OutputIterator is a model of Output Iterator.
If x and y are objects of ForwardIterator's value type then x - y is defined.
InputIterators value type is convertible to a type in OutputIterator's set of value types.
The return type of x - y is convertible to a type in OutputIterator's set of value types.

For the second version:

ForwardIterator is a model of Forward Iterator.
OutputIterator is a model of Output Iterator.
BinaryFunction is a model of Binary Function.
InputIterator's value type is convertible to a BinaryFunction's first argument type and second argument type.
InputIterators value type is convertible to a type in OutputIterator's set of value types.
BinaryFunction's result 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 an empty range otherwise exactly (last - first) - 1 applications.

Example

int main()
{
  int A[] = {1
4
9
16
25
36
49
64
81
100};
  const int N = sizeof(A) / sizeof(int);
  int B[N];

  cout << "A[]:         ";
  copy(A
A + N
ostream_iterator<int>(cout
" "));
  cout << endl;

  adjacent_difference(A
A + N
B);
  cout << "Differences: ";
  copy(B
B + N
ostream_iterator<int>(cout
" "));
  cout << endl;

  cout << "Reconstruct: ";
  partial_sum(B
B + N
ostream_iterator<int>(cout
" "));
  cout << endl;
}

Notes

[1] The reason it is useful to store the value of the first element as well as simply storing the differences is that this provides enough information to reconstruct the input range. In particular if addition and subtraction have the usual arithmetic definitions then adjacent_difference and partial_sum are inverses of each other.

[2] Note that result is permitted to be the same iterator as first. This is useful for computing differences "in place".