本文共 2057 字，大约阅读时间需要 6 分钟。

std stable_sort

转载：

上周，刚上线的项目中，发现推荐结果排序不稳定，如果用stable_sort()性能会比降低，然后我就修改了比较函数，如果评分相等，比较上架时间

auto cmp = [](const GidScore& a, const GidScore& b) {    if (a.score == b.score) {        return a.create_time >= b.create_time;  //!!!    }    return a.score > b.score;}

上面代码看起来没啥问题，但是测试时发现遇到特定的数据会导致出core文件，通过gdb查看core文件不能直接看不来具体的原因，打log发现，排序后有个元素内容被修改了。然后我试着把>=改为>好了。后来google发现，也有其他人也会遇到这个问题，是因为cmp函数导致的。

1. f(x, x) must be false.
2. f(x, y) implies !f(y, x)
3. f(x, y) and f(y, z) imply f(x, z).
4. if x is equivalent to y and y is equivalent to z, then x is equivalent to z.
   如果我们的cmp函数里使用了>=则违反了1和2。所以比较时只能用>或<.
   再看下为什么会导致出core呢。
   sort代码：

inline void sort(_RandomAccessIter __first, _RandomAccessIter __last,                 _Compare __comp) {  if (__first != __last) {    __introsort_loop(__first, __last,                     __VALUE_TYPE(__first),                     __lg(__last - __first) * 2,                     __comp);    __final_insertion_sort(__first, __last, __comp);  }}

sort先是调用了__introsort_loop然后是__final_insertion_sort，

void __unguarded_insertion_sort_aux(_RandomAccessIter __first,                                     _RandomAccessIter __last,                                    _Tp*, _Compare __comp) {  for (_RandomAccessIter __i = __first; __i != __last; ++__i)    __unguarded_linear_insert(__i, _Tp(*__i), __comp);}void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,                                _Compare __comp) {  _RandomAccessIter __next = __last;  --__next;    while (__comp(__val, *__next)) {    *__last = *__next;    __last = __next;    --__next;  }  *__last = __val;}

该函数中用cmp去从后往前挨个比较，如果_comp一直返回true，则一直__next–，如果使用>=,数组元素全部为相等，则返回的next指针一直递减，除非访问到非法地址才会停下来。所以在数组全部相同时，>=会导致崩溃。

作者：lxfeng

转载地址：https://blog.csdn.net/qq_22054285/article/details/88535846 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！