STL在rotate上的优化是极尽其所能的。分别对前向访问，双向访问，随机访问的数据结构实现了三个版本的rotate。下面是自己按照对三种算法的理解，自己进行的实现。实现中我尽力避免使用C++的特性，从而以后可以在纯C的代码中使用。
下面是我使用到的数据结构，单向链表与双向链表，用于实现算法和验证算法的正确性：
//单链表节点 typedef struct Node* Link; struct Node{ int value; Link next; Link forward(Link& i) { i=i->next; return i; } void swap(Link& i) { int temp=i->value; i->value=this->value; this->value=temp; } }; typedef struct BiNode* BiLink; struct BiNode{ int value; BiLink next; BiLink prev; BiLink forward(BiLink& i) { i=i->next; return i; } BiLink backward(BiLink& i) { i=i->prev; return i; } void swap(BiLink& i) { int temp=i->value; i->value=this->value; this->value=temp; } };
版本一：forward iterator,即类单向链表上的rotate
//forward iterator,即类单向链表 void forwardRotate(Link head,Link middle) { Link i=middle; while(true) { head->swap(i); head->forward(head); i->forward(i); if(head==middle) { if(i==NULL) return ; //如果前后两指针同时到达末尾，则结束 middle=i; //如果前者先到达末尾，则将i作为middle，继续rotate } else if(i==NULL) i=middle; //如果后者先到达末尾，则将middle作为i，继续rotate } }
另附上注释的图像版以帮助理解：
版本二：bidirection iterator,即类双向链表上的rotate
这个版本的算法很容易理解，即是分段进行反转，之后对左右数据进行反转，代码如下：
void reverse(BiLink first,BiLink last) { while(first!=last &&first!=last->backward(last)) { last->swap(first); first->forward(first); } } void bidirectionRotate(BiLink first,BiLink middle,BiLink last) { reverse(first,middle); reverse(middle,last); reverse(first,last); }
版本三：random access iterator,即类数组上的rotate
该版本的效率无疑是最高的，当然算法因为涉及到有关群论的知识所以有点难以理解。其理论支持详见：数组循环移位问题
自己实现版本的代码如下：
//求最大公约数 int gcd(int m,int n) { int t; while(n!=0) { t=m%n; m=n; n=t; } return m; } //循环移位 void rotate_cycle(int array[],int len,int initial,int shift) { int value=array[initial]; int first=initial; int next=initial+shift; while(next!=initial) { array[first]=array[next]; first=next; next=(next+shift)%len; } array[first]=value; } void randomRotate(int array[],int middle,int len) { int n=gcd(len,middle); while(n--) rotate_cycle(array,len,n,middle); }
最后附上我自己的测试代码：
int main() { int len=20; srand(time(0)); //单向访问链表的rotate Link head=new Node; head->value=25; cout<<head->value<<"\t"; Link p=head; Link middle; for(int i=0;i<len;i++) { Link next=new Node; p->next=next; next->value=rand()%200; cout<<next->value<<"\t"; if(i==len/4*3) middle=p; p=p->next; } cout<<endl; p->next=NULL; forwardRotate(head,middle); p=head; while(p!=NULL) { cout<<p->value<<"\t"; p=p->next; } cout<<endl; //双向链表的rotate BiLink bihead=new BiNode; bihead->value=25; cout<<bihead->value<<"\t"; BiLink bip=bihead; BiLink bimiddle; for(int i=0;i<len;i++) { BiLink binext=new BiNode; bip->next=binext; binext->prev=bip; binext->value=rand()%200; cout<<binext->value<<"\t"; if(i==len/4) bimiddle=bip; bip=bip->next; } cout<<endl; BiNode end; bip->next=&end; end.prev=bip; bidirectionRotate(bihead,bimiddle,&end); bip=bihead; while(bip!=&end) { cout<<bip->value<<"\t"; bip=bip->next; } cout<<endl; int array[len]; for(int i=0;i<len;i++) { array[i]=rand()%200; cout<<array[i]<<"\t"; } cout<<endl; randomRotate(array,len/3,len); for(int i=0;i<len;i++) cout<<array[i]<<"\t"; cout<<endl; return 0; }
OK，大致如此了。三个版本的rotate，极至的优化手段，这也许就是STL的魅力所在吧。
本文作者 ： cyningsun
本文地址 ： https://www.cyningsun.com/04-25-2011/stl-rotate.html
版权声明 ：本博客所有文章除特别声明外，均采用 CC BY-NC-ND 3.0 CN 许可协议。转载请注明出处！
