.\" ident @(#)rotate.3
.\" Standard Template Library
.\" $$RW_INSERT_HEADER "slyrs.man"
.TH rotate 3C++ "02 Apr 1998" "Rogue Wave Software" "-"
.ce2
Standard C++ Library   
Copyright 1998, Rogue Wave Software, Inc.   

.SH NAME

\f2rotate\fP, \f2rotate_copy\fP

\ - Swaps the segment that contains elements from \f2first\fP through \f2middle-1\fP with the segment that contains the elements from \f2middle\fP through \f2last\fP.



.SH  SYNOPSIS


.RE
.RS 0
#include <algorithm>
.br
template <class ForwardIterator>
.br
void rotate (ForwardIterator first,
.RE
.RS 12
ForwardIterator middle,
.br
ForwardIterator last);
.RE
.RS 0

.br
template <class ForwardIterator, class OutputIterator>
.br
OutputIterator rotate_copy (ForwardIterator first,
.RE
.RS 27
ForwardIterator middle,
.br
ForwardIterator last,
.br
OutputIterator result);



.SH  DESCRIPTION


The rotate algorithm takes three iterator arguments: \f2first\fP, which defines the start of a sequence; \f2last\fP, which defines the end of the sequence; and \f2middle\fP, which defines a point within the sequence. rotate "swaps" the segment that contains elements from \f2first\fP through \f2middle-1\fP with the segment that contains the elements from \f2middle\fP through \f2last\fP. After rotate has been applied, the element that was in position \f2middle\fP, is in position\f2 first\fP, and the other elements in that segment are in the same order relative to each other. Similarly, the element that was in position \f2first\fP is now in position \f2last-middle +1\fP. An example illustrates how rotate works:

Say that we have the sequence:

\f2   2 4 6 8 1 3 5 \fP

If we call rotate with \f2middle = 5\fP, the two segments are

\f2   2 4 6  8      and      1 3 5 \fP

After we apply rotate, the new sequence is:

\f2   1 3 5 2 4 6 8\fP

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 (\f2last - first + 1\fP, or 8 - 5 +1 =4).

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

\f2*(result + (i + (last - middle)) % (last -first)) = *(first + i).\fP

The ranges \f2[first, last)\fP and \f2[result, result, + (last - first)) \fPmay not overlap. 



.SH  COMPLEXITY


For rotate, at most \f2last - first \fPswaps are performed.

For rotate_copy, \f2last - first\fP assignments are performed.



.SH  EXAMPLE



.RE
.RS 0
//
.br
// rotate
.br
//
.RE
.RS 1
#include <algorithm>
.br
#include <vector>
.br
#include <iostream>
.RE
.RS 0
using namespace std;
.br

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

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

.RE
.RS 3
//Rotate the elements
.br
rotate(v.begin(), v.begin()+4, v.end());
.br
//Print out the rotated elements
.RE
.RS 2
cout << "Elements after rotate: " << endl << "     ";
.br
copy(v.begin(),v.end(),
.RE
.RS 7
ostream_iterator<int,char>(cout," "));
.RE
.RS 2
cout << endl;
.RE
.RS 0

.RE
.RS 2
return 0;
.RE
.RS 1
}

.br
.RE
.RS 0
Program Output



.RE
.RS 0

.br
Elements before rotate:
.RE
.RS 4
1 2 3 4 5 6 7 8 9 10
.RE
.RS 0
Elements after rotate:
.RE
.RS 4
5 6 7 8 9 10 1 2 3 4



.SH  WARNINGS 


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

\f2vector<int, allocator<int> >\fP

instead of:

\f2vector<int>\fP

If your compiler does not support namespaces, then you do not need the using declaration for \f2std\fP.