STL源码剖析之list的sort函数实现

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