Standard Template Library Programmer's Guide

For the second version, the one that takes three arguments:

• BidirectionalIterator is a model of Bidirectional Iterator.

• BidirectionalIterator is mutable.

• StrictWeakOrdering is a model of Strict Weak Ordering.

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

Preconditions

• [first, last) is a valid range.

Complexity

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

Example

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<int>(cout, ' '));
 cout << endl;
 prev_permutation(A, A+N);
 cout << 'After prev_permutation: ';
 copy (A, A+N, ostream_iterator<int>(cout, ' '));
 cout << endl;
 next_permutation(A, A+N);
 cout << 'After next_permutation: ';
 copy (A, A+N, ostream_iterator<int>(cout, ' '));
 cout << endl;
}

Notes

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

See also

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

Generalized numeric algorithms

iota

Category: algorithms

Component type: function

Prototype

template <class ForwardIterator, class T>
void iota(ForwardIterator first, ForwardIterator last, T value);

Description

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]

Definition

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.

Requirements on types

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

Preconditions

• [first, last) is a valid range.

Complexity

Linear. Exactly last – first assignments.

Example

int main() {
 vector<int> V(10);
 iota(V.begin(), V.end(), 7);
 copy(V.begin(), V.end(), ostream_iterator<int>(cout, ' '));
 cout << endl;
}

Notes

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

See also

fill, generate, partial_sum

accumulate

Category: algorithms

Component type: function

Prototype

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

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

Description

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,