rotate/rotate_copy詳解

旋轉元素次序:rotate

源碼:

template<class _RanIt,

class _Diff,

class _Ty> inline

void _Rotate(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Diff *, _Ty *)

{ // rotate [_First, _Last), random-access iterators

_Diff _Shift = _Mid - _First;

_Diff _Count = _Last - _First;

for (_Diff _Factor = _Shift; _Factor != 0; )//求最大公因子

{ // find subcycle count as GCD of shift count and length

_Diff _Tmp = _Count % _Factor;

_Count = _Factor;

_Factor = _Tmp;

}

if (_Count < _Last - _First)

for (; 0 < _Count; --_Count)

{ // rotate each subcycle

_RanIt _Hole = _First + _Count;

_RanIt _Next = _Hole;

_RanIt _Next1 = _Next + _Shift == _Last ? _First : _Next + _Shift;

for (; ; )

{ // percolate elements back around subcycle

iter_swap(_Next, _Next1);

_Next = _Next1;

_Next1 = _Shift < _Last - _Next1 ? _Next1 + _Shift

: _First + (_Shift - (_Last - _Next1));

if (_Next1 == _Hole)

break;

}

}

}

int main()

{

vector<int> vecInt;

for( int i = 0;i < 10;++ i )

{

vecInt.push_back( i * 10 );

}

rotate( vecInt.begin(),vecInt.begin() + 7,vecInt.end() );

copy( vecInt.begin(),vecInt.end(),ostream_iterator<int>( cout," " ) );

system( "pause" );

return 0;

}

這段代碼确實難懂,看了幾遍沒有看懂.

想去借助源碼剖析,結果聽失望的,侯捷對于forward和bidirectional iterator兩個版本有細緻的講解,唯獨random access iterator沒有.

前面兩個算法易懂,關鍵是後一個算法.__rotate_cycle在幹嘛呢?這樣做有的原理是啥呢?還是不清楚.感覺侯捷可能自己也沒法講解,"故意"跳過.

關于這個函數的講解可能就暫時過了.去Google一下,發現在部落格園裡面有一篇文章對後面的那個函數解釋的比較詳細.但是它說到數論,這個沒有學過.很可惜.

暫時先過吧.