Standard Template Library Programmer's Guide

fill(A, A+N, 1);

cout << "A: ";

copy(A, A+N, ostream_iterator(cout, " "));

cout << endl;

cout << "Partial sums of A: ";

partial_sum(A, A+N, ostream_iterator(cout, " "));

cout << endl;

}

[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.

adjacent_difference , accumulate , inner_product , count

Category: algorithms

Component type: function

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

template

OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);

template

OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryFunction binary_op);

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)) .

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

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.

• InputIterator' s 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.

• InputIterator 's 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.

• [first, last) is a valid range.

• [result, result + (last – first)) is a valid range.

Linear. Zero applications of the binary operation if [first, last) is an empty range, otherwise exactly (last – first) – 1 applications.

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(cout, " "));

cout << endl;

adjacent_difference(A, A + N, B);

cout << "Differences: ";

copy(B, B + N, ostream_iterator(cout, " "));

cout << endl;

cout << "Reconstruct: ";

partial_sum(B, B + N, ostream_iterator(cout, " "));

cout << endl;

}

[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".

partial_sum , accumulate , inner_product , count

Category: algorithms

Component type: function

Power is an overloaded name; there are actually two power functions.

template

inline T power(T x, Integer n);

template

T power(T x, Integer n, MonoidOperation op);

Power is generalized exponentiation: it raises the value x to the power n , where n is a non-negative integer.

The first version of power returns x raised to the n th power; that is, it returns x * x … * x , where x is repeated n times. [1] If n == 0 , then it returns identity_element(multiplies()) .

The second version of power is just like the first except that it uses an arbitrary Monoid Operation instead of multiplies , returning identity_element(op) when n == 0 .

Important note: power does not assume that multiplication is commutative, but it does rely crucially on the fact that multiplication is associative. If you have defined * or MonoidOperation to be a non-associative operation, then powerwill give you the wrong answer . [2]

Defined in the standard header numeric, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.

For the first version:

• multiplies is a model of Monoid Operation.

• Integer is an integral type.

For the second version:

• MonoidOperation is a model of Monoid Operation.

• T is MonoidOperation 's argument type.