 # Implement Rotate

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;
}
``````