std::rotate

From Cppreference

Swaps the elements in the range [first, last) in such a way, that the element n_first becomes the first element of the new range and n_first - 1 becomes the last element.

[edit] Parameters

[edit] Return value

(none) (pre-C++11 version)
The iterator equal to first + (last - n_first) (C++11 version)

[edit] Complexity

linear in the distance between first and last

[edit] Equivalent function

template<class ForwardIterator>
void rotate(ForwardIterator first, ForwardIterator n_first, ForwardIterator last)
{
    ForwardIterator next = n_first;
    while (first != next) {
        std::swap(*first++, *next++);
        if (next == last) {
            next = n_first;
        } else if (first == n_first) {
            n_first = next;
        }
    }
}

[edit] Example

The following code is an implementation of insertion sort in C++

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
 
int main()
{
    std::vector<int> v{2, 4, 2, 0, 5, 10, 7, 3, 7, 1}; 
 
    std::cout << "before: ";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    for (std::vector<int>::iterator i = v.begin(); i != v.end(); ++i) {
        std::rotate(std::upper_bound(v.begin(), i, *i), i, i+1);
    }
 
    std::cout << "after:  ";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

Output:

before: 2 4 2 0 5 10 7 3 7 1
after:  0 1 2 2 3 4 5 7 7 10

[edit] See also