最近在看侯捷的《STL源碼剖析》，其中有許多不太明白之處，后經分析或查找資料有了些理解，現記錄一下。

《STL源碼剖析》學習--6章--random access iterator _rotate算法分析

針對forward iterator 和 bidirectional iterator的_rotate 比較好理解，但是對random access iterator _rotate卻難以理解，作者也沒有過多的文字講解。

參考http://www.cnblogs.com/atyuwen/archive/2009/11/08/rotate.html，這個作者有好些地方沒講清楚，再做一下細致的記錄。

先列出源碼如下：

template<class RandomAccessIterator, class Distance> void __rotate(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Distance*, random_access_iterator_tag) { Distance n = __gcd(last - first, middle - first); while (n--) __rotate_cycle(first, last, frist + n, middle - first, value_type(first)); } template<class EuclideanRingElement> EuclideanRingElement __gcd(EuclideanRingElement m, EuclideanRingElement n) { while (n != 0) { EuclideanRingElement t = m % n; m = n; n = t; } return m; } 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; }

涉及到三個函數，晃一看還真是看不懂，慢慢來。

__gcd()利用的是輾轉相除法來計算兩個數的最大公約數，之前我們數學的時候肯定學過怎么計算兩個數的最大公約數，就是用的這個方法。利用的原理就是公式： gcd(a,b)=gcd(b,r)，其中 r =a mod b，t = a/b。程序中當最后余數為0時，這是m和n相等，即為最大公約數。

再看__rotate_cycle()，畫圖比較容易理解問題，如下，可以理解其作用就是從某個初始化元素開始，依次將其替換成其后相隔固定距離的元素。如果后面沒有足夠的偏移距離了，則又返回頭部繼續計算（相當于求模），直到最后形成一個置換圈為止。

用數字來看，比較清楚，如果last-first長度正好是shift的倍數或者last-first和shift的最大公約數大于1時，只是幾個值之間的循環移位。而當last-first與shift互質是就特化為循環移位操作，如下圖所示。

那么對于調用兩個函數的__rotate()，首先求出偏移距離和串總長的最大公約數n，然后循環n次，分別以串的前n個元素為起點進行__rotate_cycle操作。結束后保證元素進行了旋轉互換，其中的原理是什么呢？

查找資料。這就涉及到數論中的定理，如下《具體數學》一書4.8節：

比如，若m=8,n=6,d=gcd(m,n)=2, 則{0mod 8,?6 mod 8, 12 mod 8,…,50 mod 8}即為 8/2=4個數{0,2,4,6}的某個排列重復兩次，實際上就是{0,6,4,2,0,6,4,2?}；當兩個數互素時，即d=1，上述式實際上為{1,2,3，…，m-1}的某個排列。

了解定理后，就很容易看出__rotate函數的內涵了。middle-first相當于上述公式中的m，而last-first相當于n，Distance n相當于d。

若第一步求得的最大公約數d為1時，第一次進入while，n=0，即從first開始循環移(middle-first）距離，即middle所指元素移動到前面，只需一次__rotate_cycle就可以遍歷到所有的元素，并將每個元素正確的替換為其后相距某個距離的元素，于是也就完成了循環左移操作。

當n>1時，shift =middle-first=m，當每次__rotate_cycle截止的條件是又轉到了起始點，每次都是轉數組長度n的倍數k，kn mod m=0時，此時只有n/d的元素正確移位。

即那么每一次__rotate_cycle只能將n/d的元素正確的左移，其中n為串的總長度，而這些被移動的元素是以d為等間距的，所以循環d次，并分別以串的前d個元素為起點進行__rotate_cycle操作，就能保證將所有的元素都移動到正確的位置上。

再來看一下效率問題，對于random access iterator應該要比bidirectional效率要高，不然不需要這么復雜，bidirectional iterator總共需要三次反轉。

在這個新的算法中，每次__rotate_cycle需要t/n+1次賦值，n次循環，所以總共只需要t+n次賦值操作，顯然是比bidirectional iterator的三次反轉的算法快許多。

總結

以上是生活随笔為你收集整理的《STL源码剖析》学习--6章--_rotate算法分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。