C++中的rotate函數

寫在前面

在C++中rotate函數有多中重載類型，這裡隻讨論一種情況，當STL中對應容器的疊代器類型為ForwardIteartor以及更低的情況，我們不開辟新的空間，直接在容器上完成旋轉，不借助任何其餘空間。

函數原型

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));                                            //根據疊代器類型的不同，選擇對應最快的計算方式
}
           

根據不同的疊代器類型，進行不同的操作，對于ForwardIteartor以及更低的類型而言，不能進行雙向操作，是以不能使用reverse函數，并且再次申請空白記憶體區域會造成額外的時間空間上的浪費，是以我們直接在原來容器的基礎上直接進行旋轉操作

實作方法

#include <iostream>
#include <functional>
#include <algorithm>

using namespace std;

template<class T>
struct display{
    operator()(T a){
        cout<<a<<" ";
    }
};

template<class T>
void _rotate(T first,T middle,T last)
{
    if (first == middle || middle == last) return;
    for(T i = middle;;){
        swap(*first,*i);
        ++first;
        ++i;
        if(first == middle){              //目前半段互換完成
            if(i == last) return ;        //同時後半段互換完成，那麼表示，整體已經互換完成，可以直接退出
            middle = i;                   //否則表示後半段還沒有互換完成，講middle指向i位置，繼續進行互換
        }
        else if(i == last)                //表示後半段互換完成，則将i重新指回middle，繼續進行
            i = middle;
    }
}

int main()
{
    int a[] = {0,1,2,3,4,5,6,7,8,9};
//    rotate(a,a+10,a+10);
    _rotate(a,a+10,a+10);
    for_each(a,a+10,display<int>());
    cout<<endl;
    return 0;
}
           

函數原型

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;
    ++i;
    if (first == middle) {
      if (i == last) return;
      middle = i;
    }
    else if (i == last)
      i = middle;
  }
}
           

後記

感覺這是一個十分精巧的實作方法，在這裡記錄一下

參考書籍

《STL源碼剖析》侯捷著