SGI_STL中std::list::sort的实现细节

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

template <class T,class Alloc>
void list<T, Alloc>::sort()
{
    //以下是书中自带的注释
    //
    //以下判断，如果是空链表，或仅有一个元素,就不进行任何操作
    //使用 size() == 0 || size() == 1 来判断,虽然也可以,但是比较慢
    //
    //以上是书中自带的注释
    //SGI STL中 list 是使用双向环链表实现的，其中链表的尾部是一个空节点，即head->pre是一个空节点，指向尾部。
    if(node->next == node || sink_type(node->next)->next == node)
        return;
    //以下是书中自带的注释
    //
    //一些新的lists，作为中介数据的存放区
    //
    //以上是书中自带的注释
    list<T, Alloc> carry;
    list<T, Alloc> counter[64];
    int fill = 0;
    //在下列循环中,每次最后都将全部数据合并到counter[fill]，然后执行++fill
    /*
        外层循环每次循环从list头部取出一个节点放入carry中，
            内层循环每次循环将carry合并入counter[i]后放回carry，能够保证清空counter[i]，然后++i
        外层循环能够保证每次执行完carry都会被清空，内容放入counter[fill]
    */
    while(!empty())
    {
        //将链表中的begin()插入到carry.begin()的位置
        carry.splice(carry.begin(), *this, begin)//常数级操作
        int i = 0;//常数级操作
        //要求是i<fill 并且counter[i]不能为空，保证有数据可以取出
        while(i < fill && !counter[i].empty())
        {
            counter[i].merge(carry);//m+n次操作
            carry.swap(counter[i++]);//常量级
        }
        //清空carry
        carry.swap(counter[i]);//常量级
        if (i == fill) ++fill;//常量级 i==fill 这个判断是为因 ！counter[i].empty(),即出现counter[i]为空的情况下准备的
    }
    //因为在merge过程中，list会为空，因此
    for (int i== 1;i < fill; i++)
        counter[i].merge(counter[i-1]);
    swap(counter[fill-1];)
}