STL左旋转字符串Rotate的深入理解和自我实现

STL对左旋转字符串针对三种不同数据结构进行了不同的实现。

对单向链表采用的是同步位移，双向链表是三次翻转，都很简单，主要看看针对随机存取的数组做的循环位移实现。

STL这个版本的源码如下：

template <class RandomAccessIterator, class Distance>
void __rotate(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Distance*, random_access_iterator_tag)
{
    // gcd是求最大公约数的函数。
    Distance n = __gcd(last - first, middle - first);

    while (n--)
        // 需要执行__rotate_cycle n次。
        __rotate_cycle(first, last, first + n, middle - first, value_type(first));
}

template <class RandomAccessIterator, class Distance, class T>
void __rotate_cycle(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator initial, Distance shift, T*)
{
    T value = *initial;
    RandomAccessIterator ptr1 = initial;
    RandomAccessIterator ptr2 = ptr1 + shift;

    while (ptr2 != initial) {
        *ptr1 = *ptr2;
        ptr1 = ptr2;
        if (last - ptr2 > shift)
            ptr2 += shift;
        else
            ptr2 = first + (shift - (last - ptr2));
    }

    *ptr1 = value;
}

template <class EuclideanRingElement>
EuclideanRingElement __gcd(EuclideanRingElement m, EuclideanRingElement n)
{
    while (n != 0) {
        EuclideanRingElement t = m % n;
        m = n;
        n = t;
    }

    return m;
}

举个例子来说明算法过程，数组123456789，把123翻转到右边，*first=1,*last=9,*middle=4;

要旋转字符串（123）的长度为3，上下字符串长度为6，3和6的最大公约数为3，因此需要翻转3遍；

第一遍从*(initial+shift)=6开始，6移到3的位置，9移到6的位置，下一个位置是ptr2 = first + (shift - (last - ptr2))=0+(3-(8-8))=3，不满足ptr2 != initial的条件，退出循环，然后*ptr1 = value，即把数字3移动到数字9的位置，从而完成了3,6,9三个数字的位移，下面的2遍循环则分别完成2,5,8和1,4,76个数字的位移，最后得到最终结果456789123。

整个算法过程可用下图表示：

STL左旋转字符串Rotate的深入理解和自我实现

原文：http://blog.csdn.net/chenqin158741019/article/details/44600221