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:
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.
