STLソース分析のrotateアルゴリズム

前言stl_algo.hファイルには多くのアルゴリズムが実装されているが、ここではSTL分析でいくつかの関数を選択して分析するが、他のアルゴリズムは興味を持って自分で見ることができ、本節ではstl_algo.hファイルのrotateアルゴリズムを分析する.このアルゴリズムが実現する機能は[first,middle],[midddle,last]の2つの区間の要素を交換することである.
义齿

template <class ForwardIterator>
inline void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last) 
{
  if (first == middle || middle == last) return;
    //       : first, middle, last
  __rotate(first, middle, last, distance_type(first), iterator_category(first));
}

forward_iterator_tagバージョン
注意:

firstは前段部分のポインタ

である.

iは後段部分のポインタ

を示す.

template <class ForwardIterator, class Distance>
void __rotate(ForwardIterator first, ForwardIterator middle,
              ForwardIterator last, Distance*, forward_iterator_tag) 
{
    //        ,             
  for (ForwardIterator i = middle; ;) {
      //  middle    ,           ,               
    iter_swap(first, i);
    ++first;
    ++i;
      //         
    if (first == middle) {
        //              
      if (i == last) return;
        //     middle  ,        first = old_middle      
      middle = i;
    }
      //         
    else if (i == last)
        //     i  ,     middle      
      i = middle;
  }
}

交換全体の時間的複雑度はO(n)であり、空間的なオーバーヘッドはない.
bidirectional_iterator_tagバージョン

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);
}

random_access_iterator_tagバージョン
最大公因子減少時間複雑度を採用

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, 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;
}

まとめ
本節では、rotateの2つのセグメントの要素を交換することを分析し、全体的な実現は難しくないが、異なる反復器タイプが最適な関数を選択して実現することを考慮し、最大の効率向上の問題を考慮する必要がある.次の節では、stl_algo.hの他の基本的なアルゴリズムを分析し続けます.