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);
        ++__p;
        ++__q;
    }
    __n %= __k;
    if (__n == 0)
        return __ret;
    std::swap(__n, __k);
    __k = __n - __k;
}

Reversal

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);
    ++__first;
}

References:


Bring Your Own Cause

If you think any info here has remotely helped you consider dropping a penny for this cause, just click me . You can visit https://www.bbc.com/news/world-asia-india-52672764 Unfortunately, there are plenty of sad things happening all over the world, if you have a different cause or charity you'd rather support please do. And if you did make a donation, please drop a note to me (annotated) or leave a comment here (anonymous is OK!) and I will use that as motivation to write more useful content here.

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