rotate(), rotate_copy()

Library:  Algorithms

Function

• Local Index
• Summary
• Synopsis
• Description
• Complexity
• Example
• Standards Conformance

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