## rotate, rotate_copy

    Algorithm

- Summary
- Data Type and Member Function Indexes
- Synopsis
- Description
- Complexity
- Example
- Warnings

### Summary

Swaps the segment that contains elements from `first` through `middle-1` with the segment that contains the elements from `middle` through `last`.

### Data Type and Member Function Indexes
(exclusive of constructors and destructors)

None

### Synopsis

    #include <algorithm>
    template <class ForwardIterator>
    void rotate (ForwardIterator first,
                 ForwardIterator middle,
                 ForwardIterator last);

    template <class ForwardIterator, class OutputIterator>
    OutputIterator rotate_copy (ForwardIterator first,
                                ForwardIterator middle,
                                ForwardIterator last,
                                OutputIterator result);

### Description

The rotate algorithm takes three iterator arguments: `first`, which defines the start of a sequence; `last`, which defines the end of the sequence; and `middle`, which defines a point within the sequence. rotate "swaps" the segment that contains elements from `first` through `middle-1` with the segment that contains the elements from `middle` through `last`. After rotate has been applied, the element that was in position `middle`, is in position `first`, and the other elements in that segment are in the same order relative to each other. Similarly, the element that was in position `first` is now in position `last-middle +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 `middle = 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 (`last - first + 1`, or 8 - 5 +1 =4).

The formal description of this algorithms is: for each non-negative integer `i < (last - first)`, rotate places the element from the position `first + i` into position `first + (i + (last - middle)) % (last - first)`. `[first, middle)` and `[middle, last)` 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 container specified by `result`. rotate_copy copies the range `[first, last)` to the range `[result, result + (last - first))` such that for each non- negative integer `i < (last - first)` the following assignment takes place:

`*(result + (i + (last - middle)) % (last -first)) = *(first + i).`

The ranges `[first, last)` and `[result, result, + (last - first))` may not overlap.

### Complexity

For rotate, at most `last - first` swaps are performed.

For rotate_copy, `last - first` assignments are performed.

### Example

    //
    // rotate
    //
     #include <algorithm>
     #include <vector>
     #include <iostream>
     using namespace std;

     int main()
     {
       //Initialize a vector with an array of ints
       int arr[10] = {1,2,3,4,5,6,7,8,9,10};
       vector<int> v(arr, arr+10);

       //Print out elements in original (sorted) order
       cout << "Elements before rotate: " << endl << "     ";
       copy(v.begin(),v.end(),
            ostream_iterator<int,char>(cout," "));
       cout << endl << endl;

       //Rotate the elements
       rotate(v.begin(), v.begin()+4, v.end());
       //Print out the rotated elements
       cout << "Elements after rotate: " << endl << "     ";
       copy(v.begin(),v.end(),
            ostream_iterator<int,char>(cout," "));
       cout << 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

### Warnings

If your compiler does not support default template parameters, then you always need to supply the `Allocator` template argument. For instance, you need to write:

`vector<int, allocator<int> >`

instead of:

`vector<int>`

If your compiler does not support namespaces, then you do not need the using declaration for `std`.

Copyright (c) 1998, Rogue Wave Software, Inc.
Send mail to report errors or comment on the documentation.
OEM Release, June 1998