rotate(3C++) - rotate(3C++)
Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.
NAME
rotate, rotate_copy
- Swaps the segment that contains elements from first through middle-1
with the segment that contains the elements from middle through last.
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 illus‐
trates 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 OutputElements 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.
Rogue Wave Software 02 Apr 1998 rotate(3C++)
