std::sort与严格弱排序


C++1037 阅0 评

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),就改用插入排序,如果递归层次太深,还会改用堆排序

std::sort排序算法实现方式

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会一直循环,直至发生越界,程序崩溃。

最后更新 2023-05-31
评论 ( 0 )
OωO
隐私评论