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:

std::rotate 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.
Return value: The iterator equal to first + (last - n_first)

cppreference

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:

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.

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:

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 !