SGI STL的list的函数的实现源码大致如下：
//list 不能使用sort函数，因为list的迭代器是bidirectional_iterator, 而sort //sort函数要求random_access_iterator template<class T,class Alloc> void list<T,Alloc>::sort() { //如果元素个数小于等于1，直接返回 if(node->next==node||node->next->next==node) return ; list<T,Alloc> carry; //中转站 list<T,Alloc> counter[64]; int fill=0; while(!empty()) { carry.splice(carry.begin(),*this,begin()); //每次取出一个元素 int i=0; while(i<fill&&!counter[i].empty()) { counter[i].merge(carry); //将carry中的元素合并 //到counter[i]中 carry.swap(counter[i++]); //交换之后counter[i-1]为空 } carry.swap(counter[i]); if(i==fill) ++fill; } for(int i=1;i<fill;++i) { counter[i].merge(counter[i-1]); } swap(counter[fill-1]); }
这个sort的实现非常好：
fill--当前可以处理的元素个数为2^fill个
counter[fill]--可以容纳2^(fill+1)个元素
carry--一个临时中转站，在处理的元素个数不足2^fill个时，在counter[i](0<i<fill)之前转移元素
具体是显示步骤是：
1、每次读一个数据到carry中，并将carry的数据转移到counter[0]中
1)当counter[0]中的数据个数少于2时，持续转移数据到counter[0]中
2)当counter[0]的数据个数等于2时，将counter[0]中的数据转移到counter[1]...从counter[i]转移到counter[i+1],直到counter[fill]中数据个数达到2^(fill+1)个。
2、++fill,重复步骤1.