Rotate elements in a sequence

Source code

Declaration

template <class ForwardIterator>
inline 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  Given the sequence in the range [ first, last) , a sequence with each element

moved  to the original location of the element is created, where m is the size of the range [ first, middle) and n is the size of the range [ first, last) .

For the function rotate , this sequence is created in the range [ first, last) .

For the function rotate_copy, this sequence is created in the range the range of size n beginning at result , where n is the size of the range [ first, last) , and the past-the-end iterator  of the resulting sequence is returned.

Type requirements

• BidirectionalIterator must be at least a regular bidirectional iterator .
• ForwardIterator must be at least a readable forward iterator .
• OutputIterator must be at least an output iterator .

Group Mutating sequence operations.

Time complexity Linear.

For the rotate  function, exactly element exchanges are performed, where m is the size of the range [ first, middle) and n is the size of the range [ first, last) .

For the rotate_copy  function, exactly n assignment operations are performed, where n is the size of the range [ first, last) .

Space complexity Constant.

Mutative? Yes.

Example Select here to view the source code for the example.

Implementation Select here to view source code (Copyright (C) 1994, Hewlett-Packard Company) for this algorithm.

Implementation notes For the rotate  function, the two subsequences  in the ranges [ first, middle)

and [ middle, last) are reversed , and then the entire sequence in the range [ first, last) is reversed .

For the rotate_copy  function, the range [ middle, last) is copied  first, and then the range [ first, middle) is copied  immediately following it.