对STL 中算法rotate Random access iterator 源码理解

 // 最大公因数，利用辗转相除法

    
 // __gcd() 应用于 __rotate() 的 random access iterator 版
    
 template <class EuclideanRingElement>
    
 EuclideanRingElement __gcd(EuclideanRingElement m, EuclideanRingElement n)
    
 {
    
   while (n != 0) {           //这里是一个迭代
    
     EuclideanRingElement t = m % n;
    
     m = n;
    
     n = t;
    
   }
    
   return m;
    
 }
    
  
    
 // rotate 的 random access iterator 版
    
 template <class RandomAccessIterator, class Distance>
    
 void __rotate(RandomAccessIterator first, RandomAccessIterator middle,
    
           RandomAccessIterator last, Distance*,
    
           random_access_iterator_tag) {
    
   // 以下迭代器的相减操作只使用于RandomAccessIterator
    
   // 取全长和前段（移动的位数）的最大公因数
    
 Distance n = __gcd(last - first, middle - first);
    
 // 链数为gcd（m,n） 。链中元素个数为n/gcd(m,n)。
    
   while (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;                  //ptr1指向“槽”的位置
    
     if (last - ptr2 > shift)   //还没有到达最后一个元素
    
       ptr2 += shift;
    
 else
    
       ptr2 = first + (shift - (last - ptr2)); //此处可以将这个代数式解开发现如：ptr2=ptr2-翻转第二部分的长度 这样就非常好了理解了
    
   }
    
   *ptr1 = value;
    
 }
    
  
    
 // 分派函式（dispatch function）
    
 template <class ForwardIterator>
    
 inline void rotate(ForwardIterator first, ForwardIterator middle,
    
                ForwardIterator last) {
    
   if (first == middle || middle == last) return;         //交换的中间点在首尾，返回
    
   __rotate(first, middle, last, distance_type(first),
    
        iterator_category(first));
    
 }
    
  
    
 //_copy版本的rotate
    
 template <class ForwardIterator, class OutputIterator>
    
 OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,
    
                        ForwardIterator last, OutputIterator result) {
    
   return copy(first, middle, copy(middle, last, result));
    
 }