stl sort源码剖析

今天讲一下STL<algorithm>的sort的实现

先直接上代码。因为种种原因，用的是windows版codeblock带的minGW提供的版本，在c++/bits/stl_algo.h下。
template<typename _RandomAccessIterator>
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
if (__first != __last)
{
std::__introsort_loop(__first, __last,std::__lg(__last – __first) * 2);
std::__final_insertion_sort(__first, __last);
}
}
首先要明确几条，凡是下划线开头的变量、函数都是内部的、不开放的，就是说STL的用户不会知道。python直接用变量前加下划线来区分访问权限。
typename可以换成class什么的，就是正常的模版，inline void不解释。参数有两个，就是首尾迭代器，_RandomAccessIterator是最高级的迭代器，可以随机访问。也都知道，sort必须是可以任意访问区间元素才可以用的，因而链表不可以。链表的排序可以看这个。
当然还有一个版本是可以自定义cmp函数的，就在这段代码的后面，类似，不说了。
concept requirements那三行代码，前两行连分号都没，不知道干吗用的……感觉就是好像是声明这里要用到c++lib里面的什么东西吧。不过这也不耽误理解sort了。
然后就是当区间非空的时候开始排序。整个排序分为两部分，std::__introsort_loop和std::__final_insertion_sort，后者就是插入排序，前者相当于qsort的改进版，叫introsort，不知道这个中文名有没有最普遍的翻译，反正叫内X排序，内什么的都有。
提introsort得先说标准的快排。我们知道快排的核心思想很简单，就是找个标志物，比它小放左面，比它大放右面，然后这个元素左右两个区间分别再次进行快排，递归调用。但如果遇到特殊情况，每次选的都是区间里最小的或者最大的，那么区间就没有得到良好的划分，最坏情况是退化到平方级。于是在取这个中点元素的方法上进行尽可能的优化就是快排最直接的优化方式。因为最坏情况是平方，而平均期望是nlogn，因此需要尽可能的让它以平均的情况运行而非最坏情况。因此OIer都知道随机化快排，即从l到r之间取一个随机数作为中间元素的索引位置，因为是随机的所以每次都取到悲剧的概率会很小。而在STL中（起码是GCC所采用的版本中）采用的是从首、中点、尾三个元素中取中值来得到这个标志元素。至于两者哪个好我也不知道。但感觉如果是纯快排的话还是随机的好，除非生成随机数代价很高？不过因为introsort会有各种优化方法，因此标志物选取带来的悲剧会尽可能降低。
std::__introsort_loop的第三个参数是std::__lg(__last – __first) * 2。这是限制递归次数的参数。lg函数的参数即为n，而返回值是满足2^k<=n的最大的k，这个数再乘2就是递归最大次数。因为传统的qsort是一直递归到只有一两个元素的，而很深的递归需要很大的时间和空间开销，因此introsort首先避免了递归过深造成的效率缺失。
接下来看std::__introsort_loop的代码
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size>
void
__introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
while (__last – __first > int(_S_threshold))
{
if (__depth_limit == 0)
{
_GLIBCXX_STD_P::partial_sort(__first, __last, __last);
return;
}
–__depth_limit;
_RandomAccessIterator __cut =
std::__unguarded_partition(__first, __last, _ValueType(std::__median(*__first,*(__first+ (__last- __first)/ 2),*(__last – 1))));
std::__introsort_loop(__cut, __last, __depth_limit);
__last = __cut;
}
}
前几行都没什么问题，先看这个_S_threshold 其定义代码如下：
/**
*  @doctodo
*  This controls some aspect of the sort routines.
*/
enum { _S_threshold = 16 };
不知道为啥搞成enmu，直接const int 不就完了么……总之知道这个数是16就好了。意思就是，当本次递归的区间大小不到16的时候，就不玩了。当然，这时候肯定还没排好呢，但别忘了std::__introsort_loop后面还有 std::__final_insertion_sort，正如其名，负责首尾。
首先就是当递归层数过深的时候，调用这个 _GLIBCXX_STD_P::partial_sort(__first, __last, __last)，其代码如下：
template<typename _RandomAccessIterator>
inline void
partial_sort(_RandomAccessIterator __first,
_RandomAccessIterator __middle,
_RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __middle);
__glibcxx_requires_valid_range(__middle, __last);
std::__heap_select(__first, __middle, __last);
std::sort_heap(__first, __middle);
}
这是一个比较蛋疼的函数，目的是让一个序列比较小的部分有序的在first-middle，比较大的部分随意的在middle-last.就是说前半端有序，后半段无序，但是前半段都比后半段小。因为不带__所以这个也是可以直接用的。从下面实现可以看出，先用一个内部的std::__heap_select去用堆来选择小的在前大的在后，然后一个标准的堆排排序前半段。选择的函数代码不发了，但可以告诉大家实现方法是先让前半段元素形成一个堆（应该是最大堆），然后for循环分别跟后半段的每一个元素比较，一旦某个元素比现在堆里的根部（最大的）要小，就交换两者位置，让堆里的去外面，外面那个进堆，然后调整元素保持最大堆特性。因为堆首（__first）永远是前半段最大的，因此不能有任何一个后半段的元素比前面的大，而交换之后堆的根肯定会变小，因此后半段之前比较过的元素肯定会比新的大（不然之前就换进去了），因而一遍扫描之后就保证前面是的都比后面小，还能保证前面是堆，于是直接sort_heap堆排。这个函数要求已经是堆。
堆是什么呢……这个就先不讲吧，不知道就google，我觉得大多数能看到现在的人都知道什么是堆了。
但这都不是问题，最大的问题是，为什么当递归过深的时候要调用_GLIBCXX_STD_P::partial_sort(__first, __last, __last)？可以看到把中点跟last重合，就是说让他调用__heap_select让整个区间变成堆，然后调用sort_heap进行堆排。我除了蛋疼之外想不到任何一个解释可以说明为何这个写代码的人如此调用而不是直接make_heap(__first, __last)再sort_heap(__first, __last)……
好了不纠结了，回到之前的if (__depth_limit == 0)上。已经明白了，折腾大半圈就是想让introsort在递归过深而元素由不小于16的时候直接换成堆排来实现。
为什么不直接用堆排？我们要看堆排的原理，先是一个扫描建堆，然后每次取出最大元素都需要进行可能的重新调整，因此虽然堆排也是nlogn的算法但是由于需要大量的元素交换，常数很大，而快排的常数很小，因此效率更高。当然在递归过深的时候快排也比较悲剧，理论和实践表明这时候用堆排是更快的。
接下来看代码，我们会发现递归调用只调用了后半段。通常我们写的递归肯定最后两行应该是qsort(l,m-1)和qsort(m+1,r)之类的。这里只调用一个。但调用过后，新的last变成了原来的cut，就是说while循环的下一次就是前一次的左半段。这不影响递归深度，因为在这次循环调用的递归深度限制已经-1，因此剩下的左半段和递归进去的有半段是同样的剩余深度。
cut是参照点的迭代器。通过__unguarded_partition函数返回。他有三个参数，首、尾以及运行前选取的参照点的位置。可以看出STL的实现并没有采用随机，而是取首、中、尾三个元素大小排在中间的那一个。然后此函数将比参照制小的放左面，大的放右面，参照值在中间，并返回该值的迭代器。
以上就是introsort函数的全部内容。但我不知道学术上的标准introsort是如何实现。但肯定还是快排和堆排配合，不过不知道那个16后进行final在不在标准的introsort里面。
然后就是std::__final_insertion_sort(__first, __last)了，已经知道，现在的区间是一个几乎已经排好的区间，只不过当某个子区间小于16的时候，是比较乱的，在整体上是有序的。那就看看如何进行收尾工作：
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator>
void
__final_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last)
{
if (__last – __first > int(_S_threshold))
{
std::__insertion_sort(__first, __first + int(_S_threshold));
std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
}
else
std::__insertion_sort(__first, __last);
}
从名字就知道肯定是插入排序了。如果区间小于16就是一个朴素的插入排序。如果大于16，那么前16个插入排序，后面的std::__unguarded_insertion_sort。这个函数就是一个for循环，每次让第i个元素跟前i-1个元素挨个比，依次从i-1到1扫描一旦i比那个数小把那个数往后诺，如果i比那个数大就不挪了。朴素的__insertion_sort是一个for循环每次让前i个元素通过插入排序保持有序，所以每次第i个元素来了就插到该插的地方就直接进去了。有个优化是如果第i个元素比第一个小，就不扫描直接让1~i-1分别往右，然后第i个去第1个。
因此，__insertion_sort适合完全打乱的初始排序。因为实现方法就是平方级的。但std::__unguarded_insertion_sort建立在中个区间已经比较有序的情况下，即使是插入排序，每次需要调整的连续空间一定不会超过16（因为大于16的区间一定是部分有序的，不会越界）。插入排序的主要时间都用在了挪东西上，如果保证挪的东西很少，那么效率就非常高了。而前期的introsort就是保证这一点。
以上就是STL中sort算法的实现，可以说此算法的高效尤其是相对于单纯qsort的高效是源于introsort这种组合排序算法的优势。至于代码是否写的高效就不知道了。不过可以肯定的是堆排那段是绝对的蛋疼，而二分递归那段那么写跟普通的两个递归哪个好也不知道。其实STL本身设计的初衷虽然考虑到了效率但更主要的首先要保持统一性。因此某些时候甚至很多时候STL的时间效率并不一定就比我们自己写的好。我们自己写的代码因为 不需要考虑更多的扩展性，可能就比STL的快那么一点点。加上STL由于种种原因，设计的很好但实现之后会有些不足。总之STL不是万能的，更不是完美的，他最重要的是方便，节约程序员的时间。提供了一个几乎最好的代码复用方案。
当然，对于ACMer还有以后的OIer来说，他省了不少做题时的功夫，当然也让我们对很多算法研究不够深入。