Manoj Rao bio photo

Manoj Rao

Your Average Common Man

Email Twitter Github

Earlier, I had written about std::rotate and how it can be used to implement other useful algos. But how do we implement std::rotate itself?

In this book, Stepanov and Rose talk about different ways to implement this algorithm. One of them is the Gries-Mills algorithms that’s based on swapping ranges. A clever alternative (also simpler to implement is the one that employs reversal).

Turns out, the standard library has both implementations and switches the impl based on the iterator passed to the algorithm. The swapping version which roughly goes like:

Block Swap

_RandomAccessIterator __p = __first;
_RandomAccessIterator __ret = __first + (__last - __middle);
for (;;) {
    _RandomAccessIterator __q = __p + __k;
    for (_Distance __i = 0; __i < __n - __k; ++ __i) {
        std::iter_swap(__p, __q);
    __n %= __k;
    if (__n == 0)
        return __ret;
    std::swap(__n, __k);
    __k = __n - __k;


std::__reverse(__first,  __middle, bidirectional_iterator_tag());
std::__reverse(__middle, __last,   bidirectional_iterator_tag());

// following is the spiritual equivalent of reverse(first, last)
while (__first != __middle && __middle != __last) {
    std::iter_swap(__first, --__last);


My Podcast!

If you like topics such as this then please consider subscribing to my podcast. I talk to some of the stalwarts in tech and ask them what their favorite productivity hacks are:

Available on iTunes Podcast

Visit Void Star Podcast’s page on iTunes Podcast Portal. Please Click ‘Subscribe’, leave a comment.

Get it iTunes