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;
- }
__gcd是求两个数的最大公约数，也是循环位移的遍数。
举个例子来说明算法过程，数组123456789，把123翻转到右边，*first=1,*last=9,*middle=4;
要旋转字符串（123）的长度为3，字符串长度为9，3和9的最大公约数为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。
整个算法过程可用下图表示：
自我实现C++的int版：
- #include <iostream>
- using namespace std;
- int __gcd(int a, int b)
- {
- while (b)
- {
- int tmp = a%b;
- a = b;
- b = tmp;
- }
- return a;
- }
- void __rotate_cycle(int *data, int first, int last, int initial, int shift)
- {
- int val = data[initial];
- int pos1 = initial;
- int pos2 = initial + shift;
- while (pos2 != initial)
- {
- data[pos1] = data[pos2];
- pos1 = pos2;
- pos2 = (pos2 + shift) % (last - first + 1);
- }
- data[pos1] = val;
- }
- void __rotate(int *data,int first, int middle, int last)
- {
- int gcd = __gcd(last - first+1, middle - first);
- cout << "循环位移" << gcd << "遍" << endl;
- while (gcd--)
- {
- __rotate_cycle(data, first, last, first + gcd, middle - first);
- }
- }
- void main()
- {
- int data1[10] = {1,2,3,4,5,6,7,8,9,10};
- __rotate(data1, 0, 3, 9);
- for (int i = 0; i < 10; i++)
- {
- cout << data1[i] << " ";
- }
- cout << endl;
- int data2[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
- __rotate(data2, 0, 4, 9);
- for (int i = 0; i < 10; i++)
- {
- cout << data2[i] << " ";
- }
- cout << endl;
- int data3[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
- __rotate(data3, 0, 5, 9);
- for (int i = 0; i < 10; i++)
- {
- cout << data3[i] << " ";
- }
- cout << endl;
- int data4[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
- __rotate(data4, 0, 6, 9);
- for (int i = 0; i < 10; i++)
- {
- cout << data4[i] << " ";
- }
- int c = 0;
- cin >> c;
- }
运行结果：
