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 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)`

*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 !