解读STL里的std::sort函数

本文是个人对 C++ 标准库里的 std::sort 函数的分析、解读。鉴于个人能力有限,文中若有错误、疏漏还请各位来打我啊多多指教QAQ

当然,各家编译器的实现可能不同,这里我是用的是 LLVM 的实现。

LLVM > libcxx release 37 > algorithm

即 Xcode 8.2.1 中所使用的版本。其实在某一行上的实现方式有微小的不同,但是实际上是等价的。而且那一行也不涉及到这里讨论的 std::sort 函数。

trivial difference
trivial difference

这篇 post 由以下几个部分构成

引入


假设有一组由 vector 保存的元素。这里为了简单,我们使用 int 这种基本数据类型,并且直接指定为一组数字。

std::vector<int> array{2, 8, 5, 7, 3, 9, 1, 0, 5};

当我们准备调用 std::sort 时,可以看到,IDE 的代码提示告诉我们有 5 种不同的 std::sort。

five std::sort functions
five std::sort functions

阅读 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).

is_copy_constructible - cplusplus

那么加上前面的 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.

is_trivially_copy_constructible - cplusplus

简单复制构造的类是这样一种类(它通过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;                // 情况1x <= 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
}
声明: 本文为0xBBC原创, 转载注明出处喵~

《解读STL里的std::sort函数》有6个想法

      1. 两年不碰C++风格的语言之后……
        看着代码感觉好陌生

        (于是,当我阅读以前写的代码时,总觉得,现在的我不如过去的我)
        QuQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注