Standard Template Library Programmer's Guide

V.push_back(0);

V.push_back(1);

V.push_back(2);

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

// Output: 0 1 2

list L(V.size());

reverse_copy(V.begin(), V.end(), L.begin());

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

// Output: 2 1 0

reverse , copy

Category: algorithms

Component type: function

template

inline ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);

Rotate rotates the elements in a range. That is, the element pointed to by middle is moved to the position first , the element pointed to by middle + 1 is moved to the position first + 1 , and so on. One way to think about this operation is that it exchanges the two ranges [first, middle) and [middle, last) . Formally, for every integer n such that 0 <= n < last – first , the element *(first + n) is assigned to *(first + (n + (last – middle)) % (last – first)) . Rotate returns first + (last – middle) .

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

• ForwardIterator is a model of Forward Iterator.

• ForwardIterator is mutable.

• [first, middle) is a valid range.

• [middle, last) is a valid range. [1]

Linear. At most last – first swaps are performed. [2]

char alpha[] = "abcdefghijklmnopqrstuvwxyz";

rotate(alpha, alpha + 13, alpha + 26);

printf("%s\n", alpha);

// The output is nopqrstuvwxyzabcdefghijklm

[1] It follows from these two requirements that [first, last) is a valid range.

[2] Rotate uses a different algorithm depending on whether its arguments are Forward Iterators, Bidirectional Iterators, or Random Access Iterators. All three algorithms, however, are linear.

rotate_copy

Category: algorithms

Component type: function

template

OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);

Rotate_copy copies elements from the range [first, last) to the range [result, result + (last – first)) such that *middle is copied to *result , *(middle + 1) is copied to *(result + 1) , and so on. Formally, for every integer n such that 0 <= n < last – first , rotate_copy performs the assignment *(result + (n + (last – middle)) % (last – first)) = *(first + n) . Rotate_copy is similar to copy followed by rotate , but is more efficient. The return value is result + (last – first) .

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

• ForwardIterator is a model of Forward Iterator.

• OutputIterator is a model of Output Iterator.

• ForwardIterator 's value type is convertible to a type in OutputIterator 's set of value types.

• [first, middle) is a valid range.

• [middle, last) is a valid range. [1]

• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + (last – first)) is a valid range.

• The ranges [first, last) and [result, result + (last – first)) do not overlap.

Linear. Rotate_copy performs exactly last – first assignments.

const char alpha[] = "abcdefghijklmnopqrstuvwxyz";

rotate_copy(alpha, alpha + 13, alpha + 26, ostream_iterator(cout));

// The output is nopqrstuvwxyzabcdefghijklm

[1] It follows from these two requirements that [first, last) is a valid range.

rotate , copy .

Category: algorithms

Component type: function

Random_shuffle is an overloaded name; there are actually two random_shuffle functions.

template

void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);

template

void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand)

Random_shuffle randomly rearranges the elements in the range [first, last) : that is, it randomly picks one of the N! possible orderings, where N is last – first . [1] There are two different versions of random_shuffle . The first version uses an internal random number generator, and the second uses a Random Number Generator, a special kind of function object , that is explicitly passed as an argument.

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

For the first version:

• RandomAccessIterator is a model of Random Access Iterator

For the second version:

• RandomAccessIterator is a model of Random Access Iterator

• RandomNumberGenerator is a model of Random Number Generator

• RandomAccessIterator 's distance type is convertible to RandomNumberGenerator 's argument type.

• [first, last) is a valid range.

• last – first is less than rand 's maximum value.

Linear in last – first . If last != first , exactly (last – first) – 1 swaps are performed.

const int N = 8;

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

random_shuffle(A, A + N);