Standard Template Library Programmer's Guide

• StrictWeakOrdering is a model of Strict Weak Ordering.

• BidirectionalIterator 's value type is convertible to StrictWeakOrdering 's argument type.

• [first, last) is a valid range.

Linear. At most (last – first) / 2 swaps.

int main() {

int A[] = {2, 3, 4, 5, 6, 1};

const int N = sizeof(A) / sizeof(int);

cout << "Initially: ";

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

cout << endl;

prev_permutation(A, A+N);

cout << "After prev_permutation: ";

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

cout << endl;

next_permutation(A, A+N);

cout << "After next_permutation: ";

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

cout << endl;

}

[1] If all of the elements in [first, last) are distinct from each other, then there are exactly N! permutations. If some elements are the same as each other, though, then there are fewer. There are, for example, only three ( 3!/2! ) permutations of the elements 1 1 2 .

[2] Note that the lexicographically greatest permutation is, by definition, sorted in nonascending order.

next_permutation , lexicographical_compare , LessThan Comparable, Strict Weak Ordering, sort

Category: algorithms

Component type: function

template

void iota(ForwardIterator first, ForwardIterator last, T value);

Iota assigns sequentially increasing values to a range. That is, it assigns value to *first , value + 1 to *(first + 1) and so on. In general, each iterator i in the range [first, last) is assigned value + (i – first) . [1]

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.

• ForwardIterator is a model of Forward Iterator.

• ForwardIterator is mutable.

• T is Assignable.

• If x is an object of type T , then x++ is defined.

• T is convertible to ForwardIterator 's value type.

• [first, last) is a valid range.

Linear. Exactly last – first assignments.

int main() {

vector V(10);

iota(V.begin(), V.end(), 7);

copy(V.begin(), V.end(), ostream_iterator(cout, " "));

cout << endl;

}

[1] The name iota is taken from the programming language APL.

fill , generate , partial_sum

Category: algorithms

Component type: function

Accumulate is an overloaded name; there are actually two accumulate functions.

template

T accumulate(InputIterator first, InputIterator last, T init);

template

T accumulate(InputIterator first, InputIterator last, T init, BinaryFunction binary_op);

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

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

For the first version, the one that takes two arguments:

• InputIterator is a model of Input Iterator.

• 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 Input Iterator.

• T is a model of Assignable.

• BinaryFunction is a model of Binary Function.

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

• [first, last) is a valid range.

Linear. Exactly last – first invocations of the binary operation.

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()) << endl;

}

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

inner_product , partial_sum , adjacent_difference , count

Category: algorithms