list的sort是用什么方法如何实现的? 不是快速排序吧?

asker160

std::sort作用于random_accessible的容器，而list不是，所以list有自己的排序算法。
问题是: std::sort使用的快速排序，或者stable_sort使用的归并排序，在迭代的过程中都需要划定一个分治的范围，也就是要有一个划分的点，对可以随机访问的容器而言是很容易了。而对于list而言，要找到某个分治点，总是要前向或者后向遍历才能找到，对吧。
这样一来岂不是常规的qsort/heap_sort算法对于std::list都没有效果了? std::list::sort内部到底是怎么实现的呢，效率又如何?
谢谢。

OwnWaterloo

asker160 发表于 2015-11-25 23:03
这样一来岂不是常规的qsort/heap_sort算法对于std::list都没有效果了? std::list::sort内部到底是怎么实现的呢，效率又如何?

先说效率吧。。。 标准要求是n*lgn的， 但没要求具体用什么算法。

并且标准对效率的定义是按比较次数。。。 类似这样。。。

Complexity: Approximately N log N comparisons, where N is distance(begin(), end()).

BTW： algorithm里面的sort和stable_sort同样只要求效率达标， 并且后者必须是稳定的， 也不要求具体算法。


so。。。  临时创建vector。。。 排序。。。 然后重新组合成list是不是也符合标准。。。？
或者就向后遍历找划分点是不是也行。。。？ 反正又没进行比较。。。
libcxx(clang的实现)还真是这么干的。。。 我已经看到这样的代码了。。。

iterator __e1 = _VSTD::next(__f1, __n2);

有点失望。。。  标准要求得不够严。。。 于是libcxx还真钻了个空。。。


不过g++和msvc带的都没有这样偷懒。
C++模板有一个好处。。。  就是通常来说是能看到源代码的。。。  比如g++ -v，然后找list文件。。。  最终可以在bits/list.tcc里看到实现。

大概解释下。。。
有一个足够大的list数组（没有动态分配，就在栈上分配的一个不太大的数组）， 把它想像成二进制数。 i号list要么是空，要么是长度为i^2的list。
然后将要排序的list里的元素一个一个移动到这个数组里面。 大致这样：

1. 
   
2. 2^0   2^1   2^2 ...
   
3. 0
   
4. 1
   
5. 0     1
   
6. 1     1
   
7. 0     0     1
   

复制代码

最开始初始状态全是长度为0的list。 即00000.....
从this移动一个元素到数组的0号list上。 于是就是1000.....
从this移动一个元素到数组的0号list上。  发生合并(进位)， 得到一个长度为2的list放在数组的1号list上， 就是 01000...
从this移动一个元素到数组的0号list上。  得到11000...
从this移动一个元素到数组的0号list上。  合并两个长度为1的list， 放到1号list上， 此时再次合并两个长度为2的list， 得到长度为4的list， 放到3号list上。
就这样依次下去， 直到将this的元素移动完。
最后再全部合并到this。

这个数组大小只需要lg2(N)就够了。  对数级的。
32位上一个元素至少要12字节（2个指针+1个元素+padding）。 内存分配还可能会有一些利用不上的洞， 用户空间只有大概3G。
大小固定为32的栈上数组就够用了， 不需要动态内存分配。
64位上地址空间利用率更低。。。
大小为64的数组肯定也够用了。

合并次数。。。
长度为1的不超过N次， 长度为2的不超过N/2次， 长度为2^i的不超过N/2^i次。。。
每个位上都不超过N次比较， 最多lg2(N)位。
所以总体也能在N*lg(N)以内。