std::sort与严格弱排序

1. 引言

今天用std::sort函数自定义排序时，程序崩溃了。原因是std::sort要求比较函数comp满足严格弱排序。

函数签名如下

template<typename RandomIter>
void sort(RandomIter first, RandomIter last, Compare comp);

错误示例：

std::sort(nums.begin(), nums.end(), [](int a, int b){
    return a <= b;
})

正确示例：

std::sort(nums.begin(), nums.end(), [](int a, int b){
    return a < b;
})

原因就是小于等于<=比较不满足“严格弱序”关系。

2. 严格弱序比较

2.1 小于比较

小于、小于等于、等于、大于等于、大于，这5种比较可以提炼出一个基础的比较，即小于比较。

• 大于：x > y <=> y < x
• 大于等于：x >= y <=> !(x < y)
• 小于等于：x <= y <=> !(y < x)
• 等于：x = y <=> !(x < y) && !(y < x)

2.2 严格弱序

满足严格弱序的3个条件：

• 两个关键字不能同时“严格弱序”于对方
• 如果a“严格弱序”于b，且b“严格弱序”于c，则a必须“严格弱序”于c
• 如果存在两个关键字，任何一个都不“严格弱序”于另一个，则这两个关键字是相等的。

对于一个满足严格弱序的比较函数comp()，如果x < y，则comp(x, y)一定返回false。

3. std::sort函数底层的排序算法是什么？

内省排序。具体点说就是：

数据量大时，采用快速排序，分段归并排序，一旦分段后的数据量小于某个阈值（16），就改用插入排序，如果递归层次太深，还会改用堆排序。

4. 为什么需要严格弱序?

std::sort中使用到了快速排序，如果比较函数不遵守“严格弱序”，就会发生下标(迭代器)越界，导致程序崩溃。

template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
_RandomAccessIterator
__unguarded_partition(_RandomAccessIterator __first,
               _RandomAccessIterator __last,
               _Tp __pivot, _Compare __comp)
{
    while (true) {
       while (__comp(*__first, __pivot)) { // <-------------------
         ++__first;
       }
       --__last;
       while (__comp(__pivot, *__last)) {
         --__last;
       }
       if (!(__first < __last)) {
         return __first;
       }
       std::iter_swap(__first, __last);
       ++__first;
    }
}

如果后面的元素值都和pivot相等，则__comp()函数一直返回true，++__first会一直循环，直至发生越界，程序崩溃。