STL的rotate函数分析

「爱情、让人受尽委屈。」 2022-03-19 03:50 186阅读 0赞

STL的rotate其实就可以看做是一个循环移位的函数。

首先对于循环移位操作有以下的几种思路：

1)最简单的想法就是每次移动一位进行循环遍历整个容器，算法复杂度为O(n\*m)。

2)运用分组交换（尽可能使数组的前面连续几个数为所要结果）：若a长度大于b，将ab分成a0a1b，交换a0和b，得ba1a0，只需再迭代交换a1 和a0。算法复杂度为O(n)。

3)运用3次翻转操作（reverse），因为(arbr)r=ab。算法复杂度为O(n)。

4)构建循环操作链，对链中的元素进行循环移位。算法复杂度为O(n)。

这里链数为gcd（m,n） 。链中元素个数为n/gcd(m,n)。

注：方案4涉及到数论中的一个小定理：若有两个正整数m、n，且gcd(m,n)=d，那么序列\{m%n, 2m%n, 3m%n,..., nm%n\}一定是\{0, d, 2d,..., n-d\}的某个排列并重复出现d次，其中%号代表求模操作。比如若m=6, n=8，d=gcd(m,n)=2，那么\{6%8, 12%8, 18%8,..., 48%8\}即为\{0，2，4，6\}的某个排列并重复。特别地，若m、n互素，d=1，那么序列\{m%n,2m%n,3m%n,...,(n-1)m%n\}实际上就是\{1, 2, 3,..., n-1\}的某个排列。这个定理的证明过程可以很多书中找到（比如具体数学4.8节），这里不再详述。

对于STL的rotate函数针对不同类型的迭代器有不同的效率，共分为3个版本（ForwardIterator，BidirectionalIterator，RandomAccessIterator）。

由于BidirectionIterator有双端移动的能力，所以能调用reverse函数。选择方案3。

由于RandomAccessIterator具有+n操作能力，所以选择方案4。

**现在的问题是，后三种算法的复杂度都是O（n），那么为什么要用三种不同的算法？？**

// 分派函数（dispatch function）
    template <class BidirectionalIterator>
    inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {
      __reverse(first, last, iterator_category(first));
    }
    
    // reverse 的 bidirectional iterator 版
    template <class BidirectionalIterator>
    void __reverse(BidirectionalIterator first, BidirectionalIterator last, 
                   bidirectional_iterator_tag) {
      while (true)
        if (first == last || first == --last)   //剩余需交换元素个数小于2
          return;
        else
          iter_swap(first++, last);             //iter_swap()函数为交换迭代器所指元素的值
    }
    
    // reverse 的 random access iterator 版
    template <class RandomAccessIterator>
    void __reverse(RandomAccessIterator first, RandomAccessIterator last,
                   random_access_iterator_tag) {
      // 注意，以下的 first < last 判断动作，只适用于 random iterators. 
      while (first < last) iter_swap(first++, --last); 
    }
    
    //_copy版本的revese函数
    template <class BidirectionalIterator, class OutputIterator>
    OutputIterator reverse_copy(BidirectionalIterator first,
                                BidirectionalIterator last,
                                OutputIterator result) {
      while (first != last) {	// 遍历整个序列
        --last;				     
        *result = *last;		
        ++result;				  }
      return result;
    }
    
    // rotate 的 forward iterator 版
    template <class ForwardIterator, class Distance>
    void __rotate(ForwardIterator first, ForwardIterator middle,
                  ForwardIterator last, Distance*, forward_iterator_tag) {
      for (ForwardIterator i = middle; ;) {
        iter_swap(first, i);	// 前后段元素一一交换
        ++first;				// 双双前进1
        ++i;					
        // 以下判断是前段[first, middle)先结束还是后段[middle,last)先结束
        if (first == middle) {		// 前段先结束
          if (i == last) return; 	// 如果后段也结束了，那么就结束了
          middle = i;				// 否则进行调整，之后再进行迭代
        }
        else if (i == last)	     // 后段先结束
          i = middle;			// 否则进行调整，之后再进行迭代
      }
    }
    
    // rotate 的 bidirectional iterator 版
    template <class BidirectionalIterator, class Distance>
    void __rotate(BidirectionalIterator first, BidirectionalIterator middle,
                  BidirectionalIterator last, Distance*,
                  bidirectional_iterator_tag) {
      reverse(first, middle);
      reverse(middle, last);
      reverse(first, last);
    }
    
    // 最大公因数，利用辗转相除法
    // __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
    //为了跳出循环！真有点不明白为什么不用while（true），然后此处直接break？？
          ptr2 = first + (shift - (last - 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));
    }

现在可以进行之前问题的分析了，由于ForwardIterator版本需要进行迭代，所以引入了更多的判断（前后段的结束次序）。

BidirectionalIterator版本不需要进行迭代进行n次交换就可以了。RandomAccessIterator版本与BidirectionalIterator版本最大的区别是交换方式。B版本的交换是使用两两交换（iter\_swap），R版本的交换是使用循环赋值。所以B版本操作一次需要3次

赋值操作，而R版本只需要一次。也可以说B版本复杂度为O(3tn),R版本复杂度为O(tn)。