STLのrotate関数解析

STLのrotateは実は循環シフトの関数と見なすことができる.
まず、循環シフト操作について以下のいくつかの考え方がある.
1)最も簡単な考え方は,1つ移動するたびに容器全体を循環し,アルゴリズムの複雑さはO(n*m)である.
2)パケット交換(可能な限り配列の前の連続数を所望の結果とする):a長がbより大きい場合、abをa 0 a 1 bに分割し、a 0とbを交換し、ba 1 a 0を得、a 1とa 0を反復的に交換するだけである.アルゴリズムの複雑さはO(n)である.
3)r=abのため,3回の反転操作(reverse)を用いる.アルゴリズムの複雑さはO(n)である.
4)ループ操作チェーンを構築し,チェーン内の要素をループシフトする.アルゴリズムの複雑さはO(n)である.
ここで鎖数はgcd(m,n)である.チェーン内の要素個数はn/gcd(m,n)である.
注:スキーム4は数論の中の1つの小さい定理に関連します:もし2つの正の整数m、nがあって、しかもgcd(m、n)=dがあれば、シーケンス{m%n、2 m%n、3 m%n、...、nm%n}はきっと{0,d,2 d,...,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,2 m%n,3 m%n,…,(n−1)m%n}は、実際には{1,2,3,…,n−1}のいずれかの配列である.この定理の証明過程は多くの本の中で見つけることができる(例えば具体的な数学4.8節)、ここでは詳しく述べない.
    
STLのrotate関数は、異なるタイプの反復器に対して異なる効率を有し、3つのバージョン(ForwardIterator,BidirectionalIterator,RandomAccessIterator)に分けられる.
BidirectionIteratorは両端移動の機能があるため、reverse関数を呼び出すことができます.シナリオ3を選択します.
RandomAccessIteratorは+n操作能力を有するため、シナリオ4を選択する.
 
現在の問題は,後の3つのアルゴリズムの複雑さがO(n)であるのに,なぜ3つの異なるアルゴリズムを用いるのかということである.

//     （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バージョンの交換は2つの交換(iter_swap)を用い,Rバージョンの交換はループ割り当てを用いた.したがって、Bバージョンの操作は一度に3回必要です
割り当て操作は、Rバージョンでは1回のみ必要です.Bバージョン複雑度はO(3 tn)、Rバージョン複雑度はO(tn)ともいえる.