Though you should (almost) never do that for a serious project, rolling your own STL is very interesting from an educational point of view.
First, it will definitely improve your knowledge of how the language works.
Second, without repeating the same old Richard Feynman quote, it will also give you a very keen understanding of how other implementations of the STL might behave internally.
This post (or series of, maybe), will cover the insides of the STL, by explaining how they can possibly be implemented. Our case study today will be an in-place modifying algorithm, the well-named std::rotate
!
std::rotate
The rotate
algorithm is quite simple to understand: as its name states, it allows rotating a range of elements. As with every part of the STL, it is thoroughly documented on cppreference. If you are too lazy to check that link right now, I got you covered:
1 2 |
template <typename ForwardIt> ForwardIt rotate(ForwardIt first, ForwardIt n_first, ForwardIt last); |
cppreference
std::rotate
swaps the elements in the range[first, last)
in such a way that the elementn_first
becomes the first element of the new range andn_first - 1
becomes the last element.
Return value: The iterator equal tofirst + (last - n_first)
Note: as you noticed, it respects the usual STL design: instead of rotating a given number of times, we rotate until a given element becomes the first element in the range.
A quick drawing can help us visualize what the algorithm actually does:

We could roll our own algorithm for this, however cppreference already offers a possible (but alas, uncommented) implementation for a conforming rotate
function. We will follow that implementation, writing the code step by step in order to explain how it works.
Avoiding unnecessary work
Just like many algorithms, rotate
has a few cases for which we can bail out early.
The first one is when first
and n_first
are equal: the definition given above states that after rotating, n_first
will become the first element of the range. Thus, that is already the case, we can just stop there.
The second case for which we can avoid doing any work is when n_first
and last
are equal. This is trickier to figure out given the STL definition of the algorithm, but we can picture the rotation like a circular shift.
From that point of view, last
wraps around back to first
. That way, if n_first
and last
are equal and last
wraps around to first
, then it’s just as if we were in the case where first
and n_first
were equal.
Therefore, this is how our implementations begins:
1 2 3 4 5 6 7 8 9 10 11 |
template <typename ForwardIt> ForwardIt rotate(ForwardIt first, ForwardIt n_first, ForwardIt last) { if (first == n_first) { return last; // simplification of first + (last - n_first) } if (n_first == last) { return first; // simplification of first + (last - n_first) } // ... } |
Baby-rotate’s first algorithm
Now that we’re done with the easiest cases, let’s dive into the algorithm. A good start would be to go through the range using first
and n_first
, until n_first
reaches last
, and swap their content at each step. The implementation is quite straightforward, and uses the iter_swap function to swap the iterators contents.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
template <typename ForwardIt> ForwardIt rotate(ForwardIt first, ForwardIt n_first, ForwardIt last) { // Early bail-out cases omitted for brevity ForwardIt left = first; ForwardIt right = n_first; while (right != last) { iter_swap(left, right); ++left; ++right; } return left; } |
The following is a view of the range before each step of the algorithm (that is, everytime the condition of the while
is evaluated).

So far, this algorithm seems to perform correctly, and matches all our requirements… For the first part of the range only. As we notice, 2
and 1
are now reversed !
Here is another example showing what happens:

The issue is that right
reached last
before left
could reach past the element 3
. Because our algorithm stopped there, that element has not been rotated.
Handing remaining cases
So, do we have to drop our whole algorithm and go back to the start ? Luckily, we don’t !
If we consider the state of the resulting range above, we see that all we would have to do to restore the correct order is to rotate the range [left
, right
) by 1
.
We can generalize that by saying that we should perform a rotation such that the former first element of the input range (first
) becomes the first element of the range [left
, right
).
It looks very much like an operation that our rotate function could perform !
Here is an application of the same rotation algorithm, on the range [left
, right
) :

As we can see, we end up with the desired result. We can then finish our implementation of rotate
:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
template <typename ForwardIt> ForwardIt rotate(ForwardIt first, ForwardIt n_first, ForwardIt last) { // Early bail-out cases omitted for brevity ForwardIt left = first; ForwardIt right = n_first; ForwardIt old_first = first; while (right != last) { if (left == old_first) { old_first = right; // after the swap, the contents of "left" will be in "right" } iter_swap(left, right); ++left; ++right; } rotate(left, old_first, right); return left; } |
We simply added an extra iterator to keep track of where the content of the first
iterator goes after the swaps, and then perform the additional rotate in the end.
And voilà, we now understand the details of how std::rotate
can be implemented !