Thinking In C++. Volume 2: Practical Programming

Like copy( ), but actually copies the elements in reverse order. This is essentially a "shuffle-right" operation, and, like copy( ), the source sequence must not contain the destination. The source range [first, last) is copied to the destination, but the first destination element is destinationEnd - 1. This iterator is then decremented after each assignment. The space in the destination range must already exist (to allow assignment), and the destination range cannot be within the source range^.

void reverse(BidirectionalIterator first, BidirectionalIterator last); OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator destination);

Both forms of this function reverse the range [first, last). reverse( ) reverses the range in place, and reverse_copy( ) leaves the original range alone and copies the reversed elements into destination, returning the past-the-end iterator of the resulting range^.

ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);

Exchanges the contents of two ranges of equal size by swapping corresponding elements^.

void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator destination);

Moves the contents of [first, middle) to the end of the sequence, and the contents of [middle, last) to the beginning. With rotate( ), the swap is performed in place; and with rotate_copy( ) the original range is untouched, and the rotated version is copied into destination, returning the past-the-end iterator of the resulting range. Note that while swap_ranges( ) requires that the two ranges be exactly the same size, the "rotate" functions do not^.

bool next_permutation(BidirectionalIterator first, BidirectionalIterator last); bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering binary_pred); bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last); bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering binary_pred);

A permutation is one unique ordering of a set of elements. If you have n unique elements, there are n! (n factorial) distinct possible combinations of those elements. All these combinations can be conceptually sorted into a sequence using a lexicographical (dictionary-like) ordering and thus produce a concept of a "next" and "previous" permutation. Therefore, whatever the current ordering of elements in the range, there is a distinct "next" and "previous" permutation in the sequence of permutations^.

The next_permutation( ) and prev_permutation( ) functions rearrange the elements into their next or previous permutation and if successful return true. If there are no more "next" permutations, the elements are in sorted order; so next_permutation( ) returns false. If there are no more "previous" permutations, the elements are in descending sorted order; so previous_permutation( ) returns false^.

The versions of the functions that have a StrictWeakOrdering argument perform the comparisons using binary_pred instead of operator<.

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

This function randomly rearranges the elements in the range. It yields uniformly distributed results if the random-number generator does. The first form uses an internal random number generator, and the second uses a user-supplied random-number generator. The generator must return a value in the range [0, n) for some positive n^.

BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred); BidirectionalIterator stable_partition(BidirectionalIterator first,   BidirectionalIterator last, Predicate pred);

The "partition" functions move elements that satisfy pred to the beginning of the sequence. An iterator pointing one past the last of those elements is returned (which is, in effect, and "end" iterator" for the initial subsequence of elements that satisfy pred). This location is often called the "partition point"^.

With partition( ), the order of the elements in each resulting subsequence after the function call is not specified, but with stable_parition( ), the relative order of the elements before and after the partition point will be the same as before the partitioning process^.