**Library:** Algorithms

Function

An algorithm that rotates the given sequence left by swapping the segment that contains elements from `start` through `mid-1` with the segment that contains the elements from `mid` through `finish`

#include <algorithm> namespace std { template <class ForwardIterator> void rotate(ForwardIterator start, ForwardIterator mid, ForwardIterator finish); template <class ForwardIterator, class OutputIterator> OutputIterator rotate_copy(ForwardIterator start, ForwardIterator mid, ForwardIterator finish, OutputIterator result); }

The `rotate()` algorithm takes three iterator arguments: `start`, which defines the beginning of a sequence; `finish`, which defines the end of the sequence; and `mid`, which defines a point within the sequence. `rotate()` swaps the segment that contains elements from `start` through `mid-1` with the segment that contains the elements from `mid` through `finish`. After `rotate()` has been applied, the element that was in position `mid`, is in position` start`, and the other elements in that segment are in the same order relative to each other. Similarly, the element that was in position `start` is now in position `finish-mid +1`. An example illustrates how `rotate()` works:

Say that we have the sequence:

` 2 4 6 8 1 3 5 `

If we call `rotate()` with `mid` pointing to `5`, the two segments are

` 2 4 6 8 and 1 3 5 `

After we apply `rotate()`, the new sequence is:

` 1 3 5 2 4 6 8`

Note that the element that was in the fifth position is now in the first position, and the element that was in the first position is in position 4 (`finish - start + 1`, or 8 - 5 +1 =4).

The formal description of this algorithms is: for each non-negative integer `i < (finish - start)`, `rotate()` places the element from the position `start + i` into position `start + (i + (finish - mid)) % (finish - start)`.` [start, mid)` and `[mid, finish)` are valid ranges.

`rotate_copy()` rotates the elements as described above, but instead of swapping elements within the same sequence, it copies the result of the rotation to a sequence specified by `result`. `rotate_copy()` copies the range `[start, finish)` to the range `[result, result + (finish - start))` such that for each non- negative integer `i < (finish - start)` the following assignment takes place:

*(result + (i + (finish - mid)) % (finish - start)) = *(start + i).

The ranges `[start, finish)` and `[result, result, + (finish - start)) `may not overlap.

For `rotate()`, at most `finish - start `swaps are performed.

For `rotate_copy()`, `finish - start` assignments are performed.

// // rotate.cpp // #include <algorithm> // for rotate #include <iostream> // for cout, endl #include <vector> // for vector int main () { typedef std::vector<int, std::allocator<int> > Vector; // Initialize a vector with an array of integers. const Vector::value_type arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; Vector v (arr + 0, arr + sizeof arr / sizeof *arr); typedef std::ostream_iterator<int, char, std::char_traits<char> > Iter; // Print out elements in original (sorted) order. std::cout << "Elements before rotate: \n "; std::copy (v.begin (), v.end (), Iter (std::cout, " ")); // Rotate the elements. std::rotate (v.begin (), v.begin () + 4, v.end ()); // Print out the rotated elements. std::cout << "\n\nElements after rotate: \n "; std::copy (v.begin (), v.end (), Iter (std::cout, " ")); std::cout << std::endl; return 0; } Program Output:

Elements before rotate: 1 2 3 4 5 6 7 8 9 10 Elements after rotate: 5 6 7 8 9 10 1 2 3 4

*ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.2.10*