本文是个人对 C++ 标准库里的 std::sort 函数的分析、解读。鉴于个人能力有限,文中若有错误、疏漏还请各位来打我啊多多调指教QAQ
当然,各家编译器的实现可能不同,这里我是用的是 LLVM 的实现。
LLVM > libcxx release 37 > algorithm
即 Xcode 8.2.1 中所使用的版本。其实在某一行上的实现方式有微小的不同,但是实际上是等价的。而且那一行也不涉及到这里讨论的 std::sort 函数。
这篇 post 由以下几个部分构成
- 引入
- 真正的 sort 实现
- 0 ~ 5 个元素时的排序
- __sort3 的实现
- __sort4, __sort5 的实现
- 6 ~ limit 的实现
- 较大规模时的实现
- 不完全的插入排序
- 总结
- 附带注释的 std::sort
引入
假设有一组由 vector 保存的元素。这里为了简单,我们使用 int 这种基本数据类型,并且直接指定为一组数字。
std::vector<int> array{2, 8, 5, 7, 3, 9, 1, 0, 5};
当我们准备调用 std::sort 时,可以看到,IDE 的代码提示告诉我们有 5 种不同的 std::sort。
阅读 algorithm 的源代码,可以发现其实后四种最终都是调用的
template <class _RandomAccessIterator, class _Compare> inline void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)>
于是从这个函数开始分析吧。在 algorithm 中的实现如下
// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare template <class _RandomAccessIterator, class _Compare> inline_LIBCPP_INLINE_VISIBILITY void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { #ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); __sort<_Comp_ref>(__first, __last, __c); #else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; __sort<_Comp_ref>(__first, __last, __comp); #endif // _LIBCPP_DEBUG }
首先需要一个可以随机访问的迭代器,如果是使用了 STL 容器的话。如果是普通的数组的话,就直接传递地址。然后是一个比较函数的类型,既可以使用 std::less 或者 std::greater,也可以根据自己的需求传入一个 lambda 函数,传入 lambda 函数时,_Compare 类型会由编译器自动推导。
std::sort 函数传入需要排序的第一个元素和最后一个元素的位置。然后是刚才说的比较大小的函数,这个函数将会被传入两个元素,并且返回这两个元素的比较大小之后的结果。需要注意的是,这个比较必须是严格小于(仅当 “a 小于 b” 时才返回 true),而不能是返回一个 “a 小于等于 b” 的比较结果。
在函数体中,有一个用于 libcxx 调试时的宏,这里我们直接看 release 部分的代码。
typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; __sort<_Comp_ref>(__first, __last, __comp);
先是给模版的 _Compare 类型定义了一个的左值引用类型,这里是为了之后我们递归调用自己时,能够保持比较函数使用引用方式进行传递。然后第二行调用了真正的排序实现。
真正的 sort 实现
/// 具体实现的函数 /// _RandomAccessIterator 支持随机访问的迭代器 /// _Compare 比较函数的类型 /// __first 需要排序的开始的地方 /// __last 需要排序的结束的地方 /// __comp 比较函数 template <class _Compare, class _RandomAccessIterator> void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
可以看到,这个模版函数将 _Compare 类型放到了 _RandomAccessIterator 类型之前,这是为了之后递归调用时只需要写明 _Compare 的类型,而 _RandomAccessIterator 类型由编译器推导。
在有了第一个元素和最后一个元素的位置(我们将迭代器当作指针使用)之后,需要得到一共有多少个元素,元素的个数决定了排序的规模和我们的策略。但是对于真正的迭代器类型,两个迭代器相减,可能有不同的返回值类型,为了避免type casting,我们使用 type_traits 中提供的 std::iterator_traits 获得差值类型。
typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
有了迭代器做减法所得到的差值的类型之后,我们还需要迭代器本身指向的元素的类型。
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
为什么需要这个 value_type 呢,因为在 C++ 中,一个(广义的)对象可能是用户自己定义的 class、struct 或者 union,又或者是诸如 int、double 这样的基本数据类型。单个基本数据类型在构造 (construct) 或赋值 (assign) 时产生的开销我们可以忽略不计,但如果是用户定义的类型,则会根据具体情况而变化。例如用户自己显式定义了对象的复制构造函数,在这个函数中做了大量数据的复制操作。(在显示定义了对象的复制复制函数也有类似的情况)
于是这一点决定了我们的策略,即在什么规模下,我们使用某种排序方式(稍后则会提到)是可接受的。于是有了这一句判断
const difference_type __limit = std::is_trivially_copy_constructible<value_type>::value && std::is_trivially_copy_assignable<value_type>::value ? 30 : 6;
刚才简单的解释了为什么要这两个条件,接下来解释这两个条件的含义以及成立的要求。
对第一个,std::is_trivially_copy_constructible。先抛开 trivially 这个修饰词,copy constructible type(可复制构造类型)的含义很简单,如果一个类型有显式或隐式的复制构造函数,那么就是可复制构造的
A copy constructible class is a class that has a copy constructor (either its implicit constructor or a custom defined one).
那么加上前面的 trivially 这个修饰词之后呢?trivially copy constructible type(简单复制构造类型) 是指一个可以通过同类型的值或者引用构造的类型。标量类型、可以简单复制构造的类 和 数组 都是这种类型。
A trivially copy constructible type is a type which can be trivially constructed from a value or reference of the same type. This includes scalar types, trivially copy constructible classes and arrays of such types.
简单复制构造的类是这样一种类(它通过class, struct, union关键字定义):
- 使用隐式定义的复制构造函数
- 没有virtual成员
- 它的基类和非静态数据成员(如果有的话),也必须是简单复制构造类型
下一个条件,is_trivially_copy_assignable。与上面的类似,如果说一个类型是copy assignable的话,那么它有显式或隐式的复制赋值函数。加上前面的 trivially 这个修饰词之后,即如果说一个类型是 trivially copy assignable的话,那么
- 使用隐式定义的复制赋值函数
- 没有virtual成员
- 它的基类和非静态数据成员(如果有的话),也必须是简单复制赋值类型
0 ~ 5 个元素时的排序
之后是一个超大的 while 循环,我们先来看它的前面部分(加上注释之后)
while (true) { __restart: // 拿到需要排序的元素的长度 difference_type __len = __last - __first; // 处理长度为 0 到 5 时的排序 switch (__len) { // 长度为 0 或 1 时就无需排序了 case 0: case 1: return; case 2: // 只有2个元素时,直接比较并交换(如果需要交换的话) if (__comp(*--__last, *__first)) swap(*__first, *__last); return; case 3: // 只有3个元素时,同样直接比较并交换(不过加了一层函数调用,稍后分析) _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); return; case 4: // 只有4个元素时,同上 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); return; case 5: // 只有5个元素时,同上 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); return; }
__sort3 的实现
那么 0 到 2 个元素时就不说了,看看 __sort3 做了什么。
// stable, 2-3 compares, 0-2 swaps template <class _Compare, class _ForwardIterator> unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
可以看到,这是只有 3 个元素时的排序函数,它使用 2 到 3 次比较,0 到 2 次交换即可完成,排序完成时,有 \(x <= y <= z\)(他们所指向的元素的大小),返回值为 swap 的次数。三个数比较大小并排序的逻辑比较简单,直接看代码就能明白,但请再次注意,x、y、z是指针,我们交换的是指向的元素的值,指针本身指向的位置并没有改变。知道这一点的话,注释读起来就很简单了。
template <class _Compare, class _ForwardIterator> unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c) { unsigned __r = 0; if (!__c(*__y, *__x)) // if x <= y { if (!__c(*__z, *__y)) // if y <= z return __r; // x <= y && y <= z // x <= y && y > z swap(*__y, *__z); // x <= z && y < z __r = 1; if (__c(*__y, *__x)) // if x > y { swap(*__x, *__y); // x < y && y <= z __r = 2; } return __r; // x <= y && y < z } if (__c(*__z, *__y)) // x > y, if y > z { swap(*__x, *__z); // x < y && y < z __r = 1; return __r; } swap(*__x, *__y); // x > y && y <= z __r = 1; // x < y && x <= z if (__c(*__z, *__y)) // if y > z { swap(*__y, *__z); // x <= y && y < z __r = 2; } return __r; } // x <= y && y <= z
__sort4, __sort5 的实现
在看懂 __sort3 之后,__sort4 和 __sort5 其实就很简单了。先来看 __sort4
// stable, 3-6 compares, 0-5 swaps template <class _Compare, class _ForwardIterator> unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _Compare __c)
它接受 5 个参数,第一个到第四个是需要排序的 x1, x2, x3, x4,最后一个仍是比较函数。__sort4 的想法非常简单,不论你传入的顺序是什么,__sort4 都利用 __sort3 将 x1, x2, x3 排好序,最后找准 x4 的位置就行,找位置的方式是将 x4 与排序好的三个数按从大到小的顺序比较,即先和 x3 比较,若 x4 大于等于 x3,则顺序是 x1, x2, x3, x4。若 x4 小于 x3,则交换 x4 和 x3 指向的元素的值(指针本身指向的位置并没有改变),然后将 x3(x3 指向的元素就是原来 x4 所指向的) 和 x2 比较……以此类推。
// stable, 3-6 compares, 0-5 swaps template <class _Compare, class _ForwardIterator> unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _Compare __c) { // 先利用__sort3 将 x1, x2, x3 排好序 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c); // 此时有 x1 <= x2 <= x3 // 接下来找好 x4 的位置 if (__c(*__x4, *__x3)) { // 如果 x4 < x3 // 交换 x3 和 x4 swap(*__x3, *__x4); ++__r; if (__c(*__x3, *__x2)) { // 如果 x3 < x2 // 交换 x2 和 x3 swap(*__x2, *__x3); ++__r; if (__c(*__x2, *__x1)) { // 如果 x2 < x1 // 交换 x1 和 x2 swap(*__x1, *__x2); ++__r; } } } return __r; }
接下来的 __sort5 和 __sort4 的做法几乎一样,除了先是使用 __sort4 排序好前四个之外。
// stable, 4-10 compares, 0-9 swaps template <class _Compare, class _ForwardIterator> unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) { // 先将 x1, x2, x3, x4 排好序 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c); // 此时有 x1 <= x2 <= x3 <= x4 // 接下来找好 x5 的位置 if (__c(*__x5, *__x4)) { // 如果 x5 < x4 // 交换 x4 和 x5 swap(*__x4, *__x5); ++__r; if (__c(*__x4, *__x3)) { // 如果 x4 < x3 // 交换 x3 和 x4 swap(*__x3, *__x4); ++__r; if (__c(*__x3, *__x2)) { // 如果 x3 < x2 // 交换 x2 和 x3 swap(*__x2, *__x3); ++__r; if (__c(*__x2, *__x1)) { // 如果 x2 < x1 // 交换 x1 和 x2 swap(*__x1, *__x2); ++__r; } } } } return __r; }
以上是需要排序的元素在 0 到 5 个时的处理。
6 ~ limit 的实现
接下来,还记得我们一开始声明的那个 __limit 变量吗,当我们排序的对象是 trivially copy constructible 且 trivially copy assignable 的时候,__limit 的值为30,否则则为6。那么它限制的是什么呢?就是排序规模在\((5, \_\_limit]\)时的策略。当排序的元素个数处于\((5, \_\_limit]\)时,
if (__len <= __limit) { _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); return; }
这里调用了 __insertion_sort_3 来排序。这个比较简单,是一个插入排序,并且要求至少有 3 个元素。这里的插入排序与教科书一样的插入排序略有一些区别。
template <class _Compare, class _RandomAccessIterator> void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
这里的插入排序接受的参数和 __sort 相同,然后因为需要一个临时变量,所以也先定义了一下 value_type
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
随后利用刚才的 __sort3 将前三个元素排好序。于是排好序的长度为 3,并且使用 __j 指向排好序的末尾。
接下来令 __i = __j + 1,即 __i 指向排好序的部分的后一个元素,然后将 __i 指向的元素和 __j 指向的元素比较,如果 __i 指向的元素大于等于 __j 指向的元素,那么说明已经排好的部分,再加上 __i 指向的元素 所组成的部分也是排好序的。此时让 __j 指向新的末尾,即将 __i 赋值给 __j,这里的赋值是改变 __j 指向的位置,而不是改变 __j 所指向的元素的值。
那如果刚才 __i 指向的元素小于 __j 指向的元素呢?那么我们需要为 __i 指向的元素找到它应该在的位置(在排好序的部分中插入 __i 所指向的这个元素),查找的方式是先将 __i 指向的元素保存到一个临时变量中,然后从排好序的末尾开始,让那个元素往后移一位,再将临时变量与前一个比较,若结果还是小于,则将前一个也往后移一位……直到临时变量大于等于某个数,或者到了头的时候才停止。
例如 4 个数时,前三个已经排好序。
$$1\quad 3\quad 4\quad 2$$
此时先将 2 和 4 比较,得出 2 小于 4,于是将 2 保存到临时变量中,将 4 往后移一位,有
$$1\quad 3\quad 4\quad 4$$
再将 2 和 3 比较,得出 2 小于 3,于是再将 3 往后移一位,有
$$1\quad 3\quad 3\quad 4$$
最后,将 2 和 1 比较,得出 2 大于 1,于是将 2 写入 1 之后的那个位置,有
$$1\quad 2\quad 3\quad 4$$
此时排序完成。
template <class _Compare, class _RandomAccessIterator> void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // 定义迭代器里面所用的值类型 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; // 先将传入的前三个排好序 _RandomAccessIterator __j = __first+2; __sort3<_Compare>(__first, __first+1, __j, __comp); // 为已经排好序的部分的后一个元素 i 找位置 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) { // 将 __i 所指向的元素与已经排好的最后那个比较 if (__comp(*__i, *__j)) { // 若 __i 所指向的元素小于排好序的最后那个元素 // 则说明需要把这第 i 个插入到已经排好序的里面 // 将 __i 所指向的元素保存到临时变量 t 里 value_type __t(_VSTD::move(*__i)); // 然后将把排好序部分,从尾到头,一个一个向后移动 // 直到 t 正好大于某个数 或者 到了头的时候 停止 // 使用 __k 来每次做比较 _RandomAccessIterator __k = __j; // 使用 __j 来作为每次赋值的位置 __j = __i; do { // 将 __k 指向的元素的值赋值到 __j 指向的位置上 *__j = _VSTD::move(*__k); // 更新 __j 指向的位置 __j = __k; } while (__j != __first && __comp(__t, *--__k)); // 若 __j 还不是第一个位置 // (__k 移动到 __k 的前一个位置之后),t 的值比 __k 的值还小时, // 说明我们还没为 t 找到合适的位置 // 继续我们的移动过程 // 当循环结束时,说明 t 有了合适的位置 // 将 t 赋值到 j 的位置 *__j = _VSTD::move(__t); } // 让 __j 指向新的末尾 __j = __i; } }
较大规模时的实现
那当排序长度大于 __limit 的时候,怎么处理呢?
_RandomAccessIterator __m = __first; _RandomAccessIterator __lm1 = __last; --__lm1; // last minus 1, 指向最后一个元素 unsigned __n_swaps; { difference_type __delta; if (__len >= 1000) { // 当需要排序的元素个数大于等于 1000 时 // 我们先将五等分点的元素进行排序(排序后仍在五等分点上) __delta = __len/2; __m += __delta; __delta /= 2; __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp); // 此时在五等分点的五个元素是排好序的 } else { // 当需要排序的元素个数小于 1000 时 // 我们将三等分点的元素进行排序(排序后仍在三等分点上) __delta = __len/2; __m += __delta; __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); // 此时在三等分点的三个元素是排好序的 } } // __m 所指向的元素的值处于被选中的三个/五个元素的值中的中间 // 我们的目标是区间 [__first, __m) 的元素的值都小于 __m 所指向的元素的值,[__m, __last) 的元素的值都大于等于 __m 所指向的元素的值 _RandomAccessIterator __i = __first; _RandomAccessIterator __j = __lm1; // __m 所指向的元素的值一定小于等于 __lm1 所指向的元素的值 // 因为无论是 3 等分还是 5 等分,__m 和 __lm1 都参与了排序,且 __m 的位置在中间
因为我们的目标是区间 [__first, __m) 的元素的值都小于 __m 所指向的元素的值,[__m, __last) 的元素的值都大于等于 __m 所指向的元素的值,但是如果我们刚才选几个数时运气不太好,正好让 __first 所指向的元素的值等于 __m 所指向的元素的值的话,我们的第一个区间就空了,这就非常糟糕了。于是为了处理这个情况
if (!__comp(*__i, *__m)) // if *__first == *__m,如果 __first 所指向的元素的值等于 __m 所指向的元素的值 { // *__first == *__m, *__first doesn't go in first part // __first 所指向的元素的值等于 __m 所指向的元素的值, 于是 __first 所指向的元素不应该在第一个区间 // manually guard downward moving __j against __i // 手动让 __j 让 __i 靠近 while (true) { if (__i == --__j) { // *__first == *__m, *__m <= all other elements // __first 所指向的元素的值等于 __m 所指向的元素的值, __m 所指向的元素的值小于等于所有其他元素的值 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) // 重新划分为区间 [__first, __i) == __first 所指向的元素的值, 和 __first 所指向的元素的值小于区间 [__i, __last) 上任何元素的值 ++__i; // __first + 1 // __i 移动到 __first 所指的后一个元素(第二个) __j = __last; if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) // 如果__first 所指向的元素的值等于 __last-1 所指向的元素(即最后一个元素)的值 // 有可能全是相等的元素 // 从第二个(上方的++__i)开始依次与 __first 所指向的元素的值相比 { while (true) { if (__i == __j) // 如果 __i 已经指向了 __last // 说明全都是大小相等的元素 return; // [__first, __last) all equivalent elements if (__comp(*__first, *__i)) { // 如果 __first 小于某个 __i 指向的元素 // 说明这一组不全是相等的元素 // 我们的确可以重新划分 swap(*__i, *__j); ++__n_swaps; ++__i; break; } ++__i; } } // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 // [__first, __i) == *__first 且 *__first < [__j, __last) 且 __j == __last - 1 // 这说明第二个区间只有一个数,并且这个数大于第一区间所有的数 // 如果 __i 指向的和 __j 指向的是同一位置 if (__i == __j) // 那么两个区间可以合在一起,并且是排好序的 return; // 如果第一区间的右端和第二区间的左端不在同一位置 while (true) { // 将 __i 向后移动,直到 __first 指向的元素的值小于 __i 指向的元素的值 while (!__comp(*__first, *__i)) ++__i; // 将 __j 向前移动,直到 __first 指向的元素的值不再小于 __j 指向的元素的值 while (__comp(*__first, *--__j)) ; // 如果 __i 的位置大于等于 __j 的位置 // 说明两个区间发生了重叠,这意味着 // 第一区间上 __first 所指向的元素的值比某元素的值小 // 第二区间上某元素的值比 __first 所指向的元素的值小 if (__i >= __j) break; // 若两个区间没有交叉 // 则交换 __i 和 __j 所指向的元素的值 swap(*__i, *__j); ++__n_swaps; // 将 __i 向后移动一位 ++__i; } // [__first, __i) == *__first and *__first < [__i, __last) // The first part is sorted, sort the secod part // _VSTD::__sort<_Compare>(__i, __last, __comp); // 最后我们将得到这样的两个区间 // 第一个区间上的元素的值都相等,范围是 [__first, __i) // 第二个区间上的元素都有 __first 所指向的元素的值小于第二个区间上的任意元素 // 第二个区间的范围是[__i, __last) // 显然,我们只需要再对第二区间排序就可以了 // 直接重设开头的地址 __first = __i; // 然后重新开始 goto __restart; } // 这里是之前判断是否有 “__first 所指向的元素的值等于 __m 所指向的元素的值, __m 所指向的元素的值小于等于所有其他元素的值” 的地方 if (__comp(*__j, *__m)) { // 如果有一个元素小于 __m 所指的元素的值的话 // 则不会是那种情况 swap(*__i, *__j); ++__n_swaps; break; // found guard for downward moving __j, now use unguarded partition } } }
进行到这一步的时候,我们已经处理了如下情况
$$\begin{align}&&n\in[0, 5]\\
&&n\in(5, \_\_limit]\\
&1, 1, \dots , 1&\text{全相等}\\
&1, 1, \dots , 1, 2&\text{两边区间正好接在一起}\end{align}$$
后两种情况都是在 __first 所指向的元素的值与 __m 所指向的元素的值等于的情况下才有的,那么在不相等的时候呢?
// It is known that *__i < *__m // 此时有 __i 所指向的元素的值小于 __m 所指向的元素的值 // __i 的初值是 __first // __i 向后移动一位 ++__i; // j points beyond range to be tested, *__m is known to be <= *__lm1 // __m 所指向的元素的值必有小于等于 __lm1 所指向的元素的值(因为排序) // if not yet partitioned... // 如果还没有划分区间 if (__i < __j) { // known that *(__i - 1) < *__m // __i 的前一个元素的值小于 __m 所指向的元素的值 // known that __i <= __m // __i 的位置小于等于 __m 的位置 while (true) { // __m still guards upward moving __i // __m 的位置是 __i 移动的上界 // 因为当 __i 移动到 __m 的位置时,此循环条件必不成立 // 让 __i 向后移动,直到某个 __i 所指向的元素的值不再小于 __m 所指向的元素的 while (__comp(*__i, *__m)) ++__i; // It is now known that a guard exists for downward moving __j // 移动 __j 时,也有一个下界存在 // 让 __j 向前移动,直到某个 __j 所指向的元素的值小于 __m 所指向的元素的 while (!__comp(*--__j, *__m)) ; // 如果区间有交叉了,则跳出循环 if (__i > __j) break; // 否则交换 __i 和 __j 所指向的元素的值 swap(*__i, *__j); ++__n_swaps; // It is known that __m != __j // If __m just moved, follow it // 如果 __i 移动到了 __m 的位置 if (__m == __i) // 重新设置 __m 的位置 __m = __j; ++__i; } }
运行完上面那段之后,就会有区间 [__first, __i) 上都小于 __m 所指向的元素的值,以及 __m 所指向的元素的值小于等于区间 [__i, __last) 上任意元素的值,但是由于不清楚 __i 和 __m 的位置,所以我们还需要再稍微判断调整一下
// [__first, __i) < *__m and *__m <= [__i, __last) if (__i != __m && __comp(*__m, *__i)) { // 如果 __i 和 __m 不是在同一个位置 // 且 __m 所指向的元素的值比 __i 所指向的元素的值小 // 那么交换 __i 和 __m 所指向的元素的值 swap(*__i, *__m); ++__n_swaps; }
这样以来,我们就有了区间 [__first, __i) 上都小于 __i 所指向的元素的值,以及 __i 所指向的元素的值小于等于区间 [__i+1, __last) 上任意元素的值
现在,还记得我们一直记录的交换次数(__n_swaps)吗?
// If we were given a perfect partition, see if insertion sort is quick... // 如果我们现在有一个完美的划分,让我们试试插入排序是否够快 if (__n_swaps == 0) { // 如果一直没发生过交换的话 // 试试在 [__first, __i) 上进行不完全(限制插入次数)的插入排序 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp)) { // 如果在 [__i+1, __last) 上进行不完全插入排序能够很快排好的话 if (__fs) // 如果在 [__first, __i) 上进行不完全插入排序也能够很快排好的话 // 那么就排序完成 return; // 否则将末尾设置为 __i // 即再来处理 [__first, __i) 这一段 __last = __i; continue; } else { // 如果在 [__i+1, __last) 上进行不完全插入排序没有很快排好的话 // 即在 [__i+1, __last) 上插入次数达到限制 if (__fs) { // 但是在 [__first, __i) 上能够很快排好的话 // 设置排序起点为 ++__i // 即再来处理 [__i+1, __last) 这一段 __first = ++__i; continue; } } // 如果运行到了这里 // 说明 [__first, __i) 和 [__i+1, __last) 都不能很快排好 }
不完全的插入排序
上面代码中提到的不完全(限制插入次数)的插入排序是什么样的呢?
/// 不完全的插入排序 /// 限制了插入次数 template <class _Compare, class _RandomAccessIterator> bool __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // 这里对 0 ~ 5 的元素个数处理与 __sort 里相同 switch (__last - __first) { case 0: case 1: return true; case 2: if (__comp(*--__last, *__first)) swap(*__first, *__last); return true; case 3: _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); return true; case 4: _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); return true; case 5: _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); return true; } // 下面部分和之前提到的 __insertion_sort_3 基本相同 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; _RandomAccessIterator __j = __first+2; __sort3<_Compare>(__first, __first+1, __j, __comp); // 除了这里限制了最多有 8 个数插入之外 const unsigned __limit = 8; unsigned __count = 0; for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) { if (__comp(*__i, *__j)) { value_type __t(_VSTD::move(*__i)); _RandomAccessIterator __k = __j; __j = __i; do { *__j = _VSTD::move(*__k); __j = __k; } while (__j != __first && __comp(__t, *--__k)); *__j = _VSTD::move(__t); // 这里是对限制的判断 if (++__count == __limit) // 如果 __i 是末尾的话 // 说明刚好在第 8 次插入时完成了排序 return ++__i == __last; } __j = __i; } return true; }
那么 [__first, __i) 和 [__i+1, __last) 都不能很快排好的话,我们就递归调用自己
// sort smaller range with recursive call and larger with tail recursion elimination // 对小的区间使用递归调用,对大的区间使用尾递归消除 if (__i - __first < __last - __i) { // 如果前一个区间的元素个数较少 // 递归调用排好前面的区间 _VSTD::__sort<_Compare>(__first, __i, __comp); // _VSTD::__sort<_Compare>(__i+1, __last, __comp); // 外层的 while 循环排序起点改到 __i+1 __first = ++__i; } else { // 如果后一个区间的元素个数较少 // 递归调用排好后面的区间 _VSTD::__sort<_Compare>(__i+1, __last, __comp); // _VSTD::__sort<_Compare>(__first, __i, __comp); // 外层的 while 循环排序终点改到 __i __last = __i; }
总结
LLVM 的 libcxx 中实现的 std::sort 的核心流程如下
procedure __sort(first, last, comp): 设置 limit 的大小 - 排序的类型是简单复制构造、简单复制赋值时,limit := 30 - 否则,limit := 6 while True: 更新排序长度 len := last - first 处理 0 ~ 5 [0, 5] 个元素的排序 - 0, 1直接返回 - 2 比较大小并交换(如果需要) - 3 __sort3 - 4 利用 __sort3 排前三个,找第四个的位置 - 5 利用 __sort4 排前四个,找第五个的位置 返回 处理 6 ~ limit [6, limit] 个元素的排序 插入排序 返回 处理 (limit, +inf) 个元素的排序 如果个数大于等于 1000,将五等分点的五个数原地排序 否则将三等分点的三个数原地排序 // 目标是 [__first, __m) 的元素的值都小于 __m 所指向的元素的值,[__m, __last) 的元素的值都大于等于 __m 所指向的元素的值 如果 *__first == *__m 考虑全部相等的情况 全部相等,返回 考虑可以分成两个区间,其中第一个区间全部相等并等于 *__first,而第二个区间只有一个数 返回 考虑可以分成两个区间,[__first, __i) == *__first and *__first < [__i, __last) 通过设置__first := __i,排序 [__i, __last) 如果 *__first < *__m 调整到 [__first, __i) < *__i and *__i <= [__i+1, __last) 如果没发生过交换,可能是只有个别没排好,试着对两个区间使用限制插入次数的插入排序 如果第一区间排好了 且 第二区间也排好了 返回 如果第一区间排好了 但 第二区间没排好 处理 [__i+1, __last) 如果第二区间排好了 但 第一区间没排好 处理 [__first, __i) 如果第一区间没排好 且 第二区间没排好 找出元素个数较少的那个区间 递归调用自己 更改排序范围 // 之后会回到外层的 while,尾递归消除
附带注释的 std::sort
// sort // stable, 2-3 compares, 0-2 swaps /// 当只有3个元素时的排序函数 /// 2到3次比较,0到2次交换 /// __libcxx_sort3执行完时,x <= y <= z template <class _Compare, class _ForwardIterator> unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c) { unsigned __r = 0; // 下面所有的x,y,z若没有指明 // 则均是运行到那一步时,x,y,z的值(可能经过值交换) if (!__c(*__y, *__x)) { // 如果x <= y if (!__c(*__z, *__y)) { // 如果y <= z return __r; // 根据传递性,得到情况0,x <= y && y <= z } // 如果上面没有返回的话 // 说明 x <= y && y > z swap(*__y, *__z); // 交换 y 和 z // 此时 x <= z && y < z __r = 1; // 情况1,x <= z && y < z // 需要再次比较 x 和 y if (__c(*__y, *__x)) { // 如果 x > y swap(*__x, *__y); // 交换 x 和 y __r = 2; // 此时 x < y && y <= z } return __r; } // 已经知道x > y后 if (__c(*__z, *__y)) { // 如果 y > z // 那么传入时的大小顺序是 x > y > z // 我们排序的目标是 x < y < z swap(*__x, *__z); // 于是交换 x 和 z __r = 1; return __r; } // x > y, y <= z swap(*__x, *__y); // 交换 x 和 y // 此时 y > x, x <= z __r = 1; if (__c(*__z, *__y)) { // 如果 y > z swap(*__y, *__z); // 交换 y 和 z // 此时 z > y 且 z > x, x <= y __r = 2; } return __r; } // x <= y && y <= z // stable, 3-6 compares, 0-5 swaps /// 当只有4个元素时的排序函数 /// 3到6次比较,0到5次交换 /// __sort4执行完时,x1 <= x2 <= x3 <= x4 template <class _Compare, class _ForwardIterator> unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _Compare __c) { // 先利用__sort3 将 x1, x2, x3 排好序 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c); // 此时有 x1 <= x2 <= x3 // 接下来找好 x4 的位置 if (__c(*__x4, *__x3)) { // 如果 x4 < x3 // 交换 x3 和 x4 swap(*__x3, *__x4); ++__r; if (__c(*__x3, *__x2)) { // 如果 x3 < x2 // 交换 x2 和 x3 swap(*__x2, *__x3); ++__r; if (__c(*__x2, *__x1)) { // 如果 x2 < x1 // 交换 x1 和 x2 swap(*__x1, *__x2); ++__r; } } } return __r; } // stable, 4-10 compares, 0-9 swaps /// 当只有5个元素时的排序函数 /// 4到10次比较,0到9次交换 /// __sort5执行完时,x1 <= x2 <= x3 <= x4 <= x5 template <class _Compare, class _ForwardIterator> unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) { // 先将 x1, x2, x3, x4 排好序 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c); // 此时有 x1 <= x2 <= x3 <= x4 // 接下来找好 x5 的位置 if (__c(*__x5, *__x4)) { // 如果 x5 < x4 // 交换 x4 和 x5 swap(*__x4, *__x5); ++__r; if (__c(*__x4, *__x3)) { // 如果 x4 < x3 // 交换 x3 和 x4 swap(*__x3, *__x4); ++__r; if (__c(*__x3, *__x2)) { // 如果 x3 < x2 // 交换 x2 和 x3 swap(*__x2, *__x3); ++__r; if (__c(*__x2, *__x1)) { // 如果 x2 < x1 // 交换 x1 和 x2 swap(*__x1, *__x2); ++__r; } } } } return __r; } template <class _Compare, class _RandomAccessIterator> void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // 定义迭代器里面所用的值类型 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; // 先将传入的前三个排好序 _RandomAccessIterator __j = __first+2; __sort3<_Compare>(__first, __first+1, __j, __comp); // 为已经排好序的部分的后一个元素 i 找位置 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) { // 将 __i 所指向的元素与已经排好的最后那个比较 if (__comp(*__i, *__j)) { // 若 __i 所指向的元素小于排好序的最后那个元素 // 则说明需要把这第 i 个插入到已经排好序的里面 // 将 __i 所指向的元素保存到临时变量 t 里 value_type __t(_VSTD::move(*__i)); // 然后将把排好序部分,从尾到头,一个一个向后移动 // 直到 t 正好大于某个数 或者 到了头的时候 停止 // 使用 __k 来每次做比较 _RandomAccessIterator __k = __j; // 使用 __j 来作为每次赋值的位置 __j = __i; do { // 将 __k 指向的元素的值赋值到 __j 指向的位置上 *__j = _VSTD::move(*__k); // 更新 __j 指向的位置 __j = __k; } while (__j != __first && __comp(__t, *--__k)); // 若 __j 还不是第一个位置 // (__k 移动到 __k 的前一个位置之后),t 的值比 __k 的值还小时, // 说明我们还没为 t 找到合适的位置 // 继续我们的移动过程 // 当循环结束时,说明 t 有了合适的位置 // 将 t 赋值到 j 的位置 *__j = _VSTD::move(__t); } // 让 __j 指向新的末尾 __j = __i; } } /// 不完全的插入排序 /// 限制了插入次数 template <class _Compare, class _RandomAccessIterator> bool __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // 这里对 0 ~ 5 的元素个数处理与 __sort 里相同 switch (__last - __first) { case 0: case 1: return true; case 2: if (__comp(*--__last, *__first)) swap(*__first, *__last); return true; case 3: _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); return true; case 4: _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); return true; case 5: _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); return true; } // 下面部分和之前提到的 __insertion_sort_3 基本相同 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; _RandomAccessIterator __j = __first+2; __sort3<_Compare>(__first, __first+1, __j, __comp); // 除了这里限制了最多有 8 个数插入之外 const unsigned __limit = 8; unsigned __count = 0; for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) { if (__comp(*__i, *__j)) { value_type __t(_VSTD::move(*__i)); _RandomAccessIterator __k = __j; __j = __i; do { *__j = _VSTD::move(*__k); __j = __k; } while (__j != __first && __comp(__t, *--__k)); *__j = _VSTD::move(__t); // 这里是对限制的判断 if (++__count == __limit) // 如果 __i 是末尾的话 // 说明刚好在第 8 次插入时完成了排序 return ++__i == __last; } __j = __i; } return true; } /// 具体实现的函数 /// _RandomAccessIterator 支持随机访问的迭代器 /// _Compare 比较函数的类型 /// __first 需要排序的开始的地方 /// __last 需要排序的结束的地方 /// __comp 比较函数 template <class _Compare, class _RandomAccessIterator> void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // _Compare is known to be a reference type // 使用 type_traits 中提供的 std::iterator_traits 获得差值类型 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; // 迭代器本身指向的元素的类型 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; // 检查迭代器中的使用的类是否有简单复制构造函数 // copy constructible type (可复制构造类型)的含义很简单,如果一个类型有显式或隐式的复制构造函数,那么就是可复制构造的 // Checks whether a type is CopyConstructible, i.e. has an accessible explicit or implicit copy constructor. If the requirement is met, a member constant value equal true is provided, otherwise value is false. // http://en.cppreference.com/w/cpp/types/is_copy_constructible // http://www.cplusplus.com/reference/type_traits/is_trivially_copy_constructible/ // trivially copy constructible type(简单复制构造函数) 是指一个可以通过同类型的值或者引用构造的类型。标量类型,可以简单复制构造的类 和 数组 都是这种类型。 // A trivially copy constructible type is a type which can be trivially constructed from a value or reference of the same type. This includes scalar types, trivially copy constructible classes and arrays of such types. // 简单复制构造的类是这样一种类(它通过class, struct, union关键字定义): // - 使用隐式定义的复制构造函数 // - 没有virtual成员 // - 它的基类和非静态数据成员(如果有的话),也必须是简单复制构造的 // A trivially copy constructible class is a class (defined with class, struct or union) that: // uses the implicitly defined copy constructor. // has no virtual members. // its base class and non-static data members (if any) are themselves also trivially copy constructible types. // 下一个条件,is_trivially_copy_assignable // 与上面的类似,如果说一个类型是copy assignable的话,那么它有显式或隐式的复制赋值函数 // 如果说一个类型是 trivially copy assignable的话,那么 // - 使用隐式定义的复制赋值函数 // - 没有virtual成员 // - 它的基类和非静态数据成员(如果有的话),也必须是简单复制赋值的 constdifference_type __limit = is_trivially_copy_constructible<value_type>::value && is_trivially_copy_assignable<value_type>::value ? 30 : 6; while (true) { __restart: // 需要排序的元素的长度 difference_type __len = __last - __first; // 处理长度为 0 到 5 时的排序 switch (__len) { // 长度为 0 或 1 时就无需排序了 case 0: case 1: return; case 2: // 只有2个元素时,直接比较并交换(如果需要交换的话) if (__comp(*--__last, *__first)) swap(*__first, *__last); return; case 3: // 只有3个元素时,同样直接比较并交换(不过加了一层函数调用,稍后分析) _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); return; case 4: // 只有4个元素时,同上 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); return; case 5: // 只有5个元素时,同上 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); return; } // 如果排序长度小于限制时 // - 当元素是 简单复制构造 且 简单复制赋值 时,限制是 30 // - 否则限制是 6 if (__len <= __limit) { _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); return; } // __len > 5 // * __len > __limit * _RandomAccessIterator __m = __first; _RandomAccessIterator __lm1 = __last; --__lm1; // last minus 1, 指向最后一个元素 unsigned __n_swaps; { difference_type __delta; if (__len >= 1000) { // 当需要排序的元素个数大于等于 1000 时 // 我们先将五等分点的元素进行排序(排序后仍在五等分点上) __delta = __len/2; __m += __delta; __delta /= 2; __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp); // 此时在五等分点的五个元素是排好序的 } else { // 当需要排序的元素个数小于 1000 时 // 我们将三等分点的元素进行排序(排序后仍在三等分点上) __delta = __len/2; __m += __delta; __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); // 此时在三等分点的三个元素是排好序的 } } // *__m is median // partition [__first, __m) < *__m and *__m <= [__m, __last) // (this inhibits tossing elements equivalent to __m around unnecessarily) // __m 所指向的元素的值处于被选中的三个/五个元素的值中的中间 // 我们的目标是区间 [__first, __m) 的元素的值都小于 __m 所指向的元素的值,[__m, __last) 的元素的值都大于等于 __m 所指向的元素的值 _RandomAccessIterator __i = __first; _RandomAccessIterator __j = __lm1; // j points beyond range to be tested, *__m is known to be <= *__lm1 // The search going up is known to be guarded but the search coming down isn't. // Prime the downward search with a guard. // __m 所指向的元素的值一定小于等于 __lm1 所指向的元素的值 // 因为无论是 3 等分还是 5 等分,__m 和 __lm1 都参与了排序,且 __m 的位置在中间 if (!__comp(*__i, *__m)) // if *__first == *__m, 如果 __first 所指向的元素的值等于 __m 所指向的元素的值 { // *__first == *__m, *__first doesn't go in first part // __first 所指向的元素的值等于 __m 所指向的元素的值, 于是 __first 所指向的元素不应该在第一个区间 // manually guard downward moving __j against __i // 手动让 __j 让 __i 靠近 while (true) { if (__i == --__j) { // *__first == *__m, *__m <= all other elements // __first 所指向的元素的值等于 __m 所指向的元素的值, __m 所指向的元素的值小于等于所有其他元素的值 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) // 重新划分为区间 [__first, __i) == __first 所指向的元素的值, 和 __first 所指向的元素的值小于区间 [__i, __last) 上任何元素的值 ++__i; // __first + 1 // __i 移动到 __first 所指的后一个元素(第二个) __j = __last; if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) // 如果__first 所指向的元素的值等于 __last-1 所指向的元素(即最后一个元素)的值 // 有可能全是相等的元素 // 从第二个(上方的++__i)开始依次与 __first 所指向的元素的值相比 { while (true) { if (__i == __j) // 如果 __i 已经指向了 __last // 说明全都是大小相等的元素 return; // [__first, __last) all equivalent elements if (__comp(*__first, *__i)) { // 如果 __first 小于某个 __i 指向的元素 // 说明这一组不全是相等的元素 // 我们的确可以重新划分 swap(*__i, *__j); ++__n_swaps; ++__i; break; } ++__i; } } // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 // [__first, __i) == *__first 且 *__first < [__j, __last) 且 __j == __last - 1 // 这说明第二个区间只有一个数,并且这个数大于第一区间所有的数 // 如果 __i 指向的和 __j 指向的是同一位置 if (__i == __j) // 那么两个区间可以合在一起,并且是排好序的 return; // 如果第一区间的右端和第二区间的左端不在同一位置 while (true) { // 将 __i 向后移动,直到 __first 指向的元素的值小于 __i 指向的元素的值 while (!__comp(*__first, *__i)) ++__i; // 将 __j 向前移动,直到 __first 指向的元素的值不再小于 __j 指向的元素的值 while (__comp(*__first, *--__j)) ; // 如果 __i 的位置大于等于 __j 的位置 // 说明两个区间发生了重叠,这意味着 // 第一区间上 __first 所指向的元素的值比某元素的值小 // 第二区间上某元素的值比 __first 所指向的元素的值小 if (__i >= __j) break; // 若两个区间没有交叉 // 则交换 __i 和 __j 所指向的元素的值 swap(*__i, *__j); ++__n_swaps; // 将 __i 向后移动一位 ++__i; } // [__first, __i) == *__first and *__first < [__i, __last) // The first part is sorted, sort the secod part // _VSTD::__sort<_Compare>(__i, __last, __comp); // 最后我们将得到这样的两个区间 // 第一个区间上的元素的值都相等,范围是 [__first, __i) // 第二个区间上的元素都有 __first 所指向的元素的值小于第二个区间上的任意元素 // 第二个区间的范围是[__i, __last) // 显然,我们只需要再对第二区间排序就可以了 // 直接重设开头的地址 __first = __i; // 然后重新开始 goto __restart; } // 这里是之前判断是否有 “__first 所指向的元素的值等于 __m 所指向的元素的值, __m 所指向的元素的值小于等于所有其他元素的值” 的地方 if (__comp(*__j, *__m)) { // 如果有一个元素小于 __m 所指的元素的值的话 // 则不会是那种情况 swap(*__i, *__j); ++__n_swaps; break; // found guard for downward moving __j, now use unguarded partition } } } // It is known that *__i < *__m // 此时有 __i 所指向的元素的值小于 __m 所指向的元素的值 // __i 的初值是 __first // __i 向后移动一位 ++__i; // j points beyond range to be tested, *__m is known to be <= *__lm1 // __m 所指向的元素的值必有小于等于 __lm1 所指向的元素的值(因为排序) // if not yet partitioned... // 如果还没有划分区间 if (__i < __j) { // known that *(__i - 1) < *__m // __i 的前一个元素的值小于 __m 所指向的元素的值 // known that __i <= __m // __i 的位置小于等于 __m 的位置 while (true) { // __m still guards upward moving __i // __m 的位置是 __i 移动的上界 // 因为当 __i 移动到 __m 的位置时,此循环条件必不成立 // 让 __i 向后移动,直到某个 __i 所指向的元素的值不再小于 __m 所指向的元素的 while (__comp(*__i, *__m)) ++__i; // It is now known that a guard exists for downward moving __j // 移动 __j 时,也有一个下界存在 // 让 __j 向前移动,直到某个 __j 所指向的元素的值小于 __m 所指向的元素的 while (!__comp(*--__j, *__m)) ; // 如果区间有交叉了,则跳出循环 if (__i > __j) break; // 否则交换 __i 和 __j 所指向的元素的值 swap(*__i, *__j); ++__n_swaps; // It is known that __m != __j // If __m just moved, follow it // 如果 __i 移动到了 __m 的位置 if (__m == __i) // 重新设置 __m 的位置 __m = __j; ++__i; } } // [__first, __i) < *__m and *__m <= [__i, __last) if (__i != __m && __comp(*__m, *__i)) { // 如果 __i 和 __m 不是在同一个位置 // 且 __m 所指向的元素的值比 __i 所指向的元素的值小 // 那么交换 __i 和 __m 所指向的元素的值 swap(*__i, *__m); ++__n_swaps; } // [__first, __i) < *__i and *__i <= [__i+1, __last) // If we were given a perfect partition, see if insertion sort is quick... // 如果我们现在有一个完美的划分,让我们试试插入排序是否够快 if (__n_swaps == 0) { // 如果一直没发生过交换的话 // 试试在 [__first, __i) 上进行不完全(限制插入次数)的插入排序 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp)) { // 如果在 [__i+1, __last) 上进行不完全插入排序能够很快排好的话 if (__fs) // 如果在 [__first, __i) 上进行不完全插入排序也能够很快排好的话 // 那么就排序完成 return; // 否则将末尾设置为 __i // 即再来处理 [__first, __i) 这一段 __last = __i; continue; } else { // 如果在 [__i+1, __last) 上进行不完全插入排序没有很快排好的话 // 即在 [__i+1, __last) 上插入次数达到限制 if (__fs) { // 但是在 [__first, __i) 上能够很快排好的话 // 设置排序起点为 ++__i // 即再来处理 [__i+1, __last) 这一段 __first = ++__i; continue; } } // 如果运行到了这里 // 说明 [__first, __i) 和 [__i+1, __last) 都不能很快排好 } // sort smaller range with recursive call and larger with tail recursion elimination // 对小的区间使用递归调用,对大的区间使用尾递归消除 if (__i - __first < __last - __i) { // 如果前一个区间的元素个数较少 // 递归调用排好前面的区间 _VSTD::__sort<_Compare>(__first, __i, __comp); // _VSTD::__sort<_Compare>(__i+1, __last, __comp); // 外层的 while 循环排序起点改到 __i+1 __first = ++__i; } else { // 如果后一个区间的元素个数较少 // 递归调用排好后面的区间 _VSTD::__sort<_Compare>(__i+1, __last, __comp); // _VSTD::__sort<_Compare>(__first, __i, __comp); // 外层的 while 循环排序终点改到 __i __last = __i; } } } // This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare template <class _RandomAccessIterator, class _Compare> inline_LIBCPP_INLINE_VISIBILITY void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { #ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); __sort<_Comp_ref>(__first, __last, __c); #else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; __sort<_Comp_ref>(__first, __last, __comp); #endif // _LIBCPP_DEBUG }
一堆一堆的下划线看起来真是太费劲了。。。
受益匪浅喵~
呜哇,还请多多指教(。・ω・。)
呜喵
晚上好喵~
两年不碰C++风格的语言之后……
看着代码感觉好陌生
(于是,当我阅读以前写的代码时,总觉得,现在的我不如过去的我)
QuQ
当我看到以前在 OI 队写的代码时,也有这样的体会……QAQ