stl中list的sort()函数解析

list不能使用STL算法sort()，必须使用自己的sort()member function，因为STL算法sort()只接受RandomAccessIterator，而list提供的是

Bidirectional Iterators

算法描述：

template<class T>
	void list<T>::sort() {
		sort(WKstl::less<T>());
	}
	template<class T>
	template<class Compare>
	void list<T>::sort(Compare comp) {
		if (empty() || head.p->next == tail.p)
			return;
		list carry;
		list 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, comp);
				carry.swap(counter[i++]);
			}
			carry.swap(counter[i]);
			if (i == fill)
				++fill;
		}
		for (int i = 0; i != fill; ++i) {
			counter[i].merge(counter[i - 1], comp);
		}
		swap(counter[fill - 1]);
	}
}

步骤一：

list carry;
list counter[64];

这是一些空链表，用于辅助操作

*this是待排序的list

步骤二：

carry.splice(carry.begin(),*this,begin());

每次都是将*this链表中的首元素移入空链表carry中，并在*this中删除移走的元素

步骤三：

现在i=fill=0，不满足while (i < fill && !counter[i].empty())

执行carry.swap(counter[0]);

然后将fill置为1

 

这样一次while（！empty()）执行完毕，开始下一轮

步骤一：

carry.splice(carry.begin(),*this,begin());

同上，将*this中的首元素拼接到carry中

步骤二：

counter[0].merge(carry,comp);

此时，进入内层while循环，将链表carry中的元素合并（按comp方式进行合并，比如<）到counter[0]中

carry.swap(counter[i++]);

将链表carry与counter[0]进行交换

步骤三：

现在i=fill=1，不满足while (i < fill && !counter[i].empty())

执行carry.swap(counter[1]);

然后将fill置为2

最后对3的处理也是同理

总之，每次执行完一次while,链表carry总是为空链表，而链表counter[i]中存放目前sort好的元素，链表list[i-1]...list[0]为空链表。直到最后把所有元素都按照comp方式排好序

最后，swap(counter[fill-1]);

也就是把排好序的所有元素再换回*this中