导读：刷题经常用的
std::sort函数的比较器隐藏着一个bug，不小心就容易导致coredump。
今天来聊聊STL中一个隐藏BUG的函数： std::sort。
前言
这个问题呢，实际上是来自于交流群小伙伴@Tgive在刷leetcode-56时发现的（完整的代码见附录），最终定位到是std::sort函数的第三个参数写错了，即比较器Compartor写的不对：
Compartor将==判断为true则无法通过；更改为false，能accept。
std::sort部分的代码如下所示：区别仅仅在于lhs[0] == rhs[0]时返回的是false还是true：
std::vector<std::vector<int>>& intervals;
// 未通过版本
std::sort(intervals.begin(), intervals.end(),
[](const std::vector<int> &lhs, const std::vector<int> &rhs)
{
return lhs.at(0) <= rhs.at(0); // lhs[0] == rhs[0]，返回 true
});
// 通过版本
std::sort(intervals.begin(), intervals.end(),
[](const std::vector<int> &lhs, const std::vector<int> &rhs)
{
return lhs.at(0) < rhs.at(0); // lhs[0] == rhs[0]，返回 false
}); 我把这个同学的代码运行了一次后，发现leetcode的编译器（GCC）报错如下：
terminate called after throwing an instance of 'std::out_of_range' what(): vector::_M_range_check: __n (which is 0) >= this->size() (which is 0)
一开始我以为是这个同学的代码问题，没考虑到一些边界情况，导致越界。后来自己测试下，发现确实是std::sort问题，但是自己写了几个简单的demo，std::sort函数又表现正常，令人匪夷所思。
『源码面前，了无秘密』 --- 侯捷
于是乎，开启 std::sort函数的源码探索之路。
- 更好阅读体验，点击：踩坑记 (1) | std::sort函数隐藏着BUG，你知道吗
- 更多硬核知识，点击并关注: look_code_art，精彩等你发现
- 欢迎加入 [C++学习交流](https://w.url.cn/s/AEPtI***---
std::sort
STL的std::sort函数是基于Musser在1996年提出的内省排序（Introspective sort）算法实现。这个算法是个缝合怪，它汲取了插入排序、堆排序以及快排的优点：
- 针对大数据量，使用快排，时间复杂度是
O(NlogN)； - 若快排递归深度超过阈值
__depth_limit，改用堆排序，防止快排递归过深，同时保持时间复杂度仍是O(NlogN)； - 当数据规模小于阈值
_S_threshold时，改用插入排序。
下面从源码角度分析 std::sort函数是怎么实现这一过程的。
std::__sort
std::sort函数在内部就是直接调用的std::__sort函数。因此下面，直接从std::__sort函数开始分析。
std::__sort代码如下。
template <typename _RandomAccessIterator, typename _Compare>
inline void
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
if (__first != __last)
{
// 先是完成局部有序
std::__introsort_loop(__first, __last,
std::__lg(__last - __first) * 2,
__comp);
// 再完全有序
std::__final_insertion_sort(__first, __last, __comp);
}
} 可以看出，std::__sort主体上分为两个部分：
- 首先，由
__introsort_loop函数使得[__first, __last)区间在多个局部有序； - 其次，对第一步的结果，再进行一次插入排序
std::__final_insertion_sort，保证整个[__first, __last)区间有序。
下面从以上两点进行详述。
为便于讲解，在下面的描述中，将比较器
_Compare当作默认的std::less来处理。
std::__introsort_loop
__introsort_loop函数，其代码实现如下：
template <typename _RandomAccessIterator, typename _Size, typename _Compare>
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Size __depth_limit,
_Compare __comp)
{
// 限制条件1
while (__last - __first > int(_S_threshold)) {
// 限制条件2
if (__depth_limit == 0) {
std::__partial_sort(__first, __last, __last, __comp); // 堆排序
return;
}
//下面是快排
--__depth_limit;
_RandomAccessIterator __cut = std::__unguarded_partition_pivot(__first, __last, __comp); // 寻找轴点
std::__introsort_loop(__cut, __last, __depth_limit, __comp); // 递归
__last = __cut;
}
} 从上面可以看出，__introsort_loop函数是个递归函数，并且存在两个限制条件，或者说是递归基：
每次递归时，
[__first, __last)区间的元素个数必须大于_S_threshold：当不满足这个条件时，
__introsort_loop函数就开始返回，这会导致元素个数小于阈值_S_threshold的小区间仍然是无序的。那么这部分小区间怎么实现有序呢？？？
最大递归深度
__depth_limit：当
__depth_limit==0时，快排递归深度达到限制，为避免递归层数过深，STL就对当前的[__first, __last)区间进行堆排序。从另一个角度看，相当于通过
__depth_limit限制条件，将__introsort_loop函数划分为快排、堆排两部分，而且不一定每次都会调用堆排，需要满足__depth_limit限制条件。
因此，__introsort_loop函数能正常递归，需要满足以下条件：
__last - __first > int(_S_threshold) && __depth_limit > 0
下面就从这两个限制点继续讲解。
Sthreshold
下面，开始讲解第【1】个限制条件_S_threshold。
我们把先深度限制条件__depth_limit去掉，只看快排部分。那么 __introsort_loop 函数的while循环可简洁如下：
while (__last - __first > int(_S_threshold)) {
// ...
// 寻找分割区间的轴点
auto __cut = std::__unguarded_partition_pivot(__first, __last, __comp);
// 在右分支递归
std::__introsort_loop(__cut, __last, __depth_limit, __comp);
// 进入左分支
__last = __cut;
} 有没有发现，这个快排的实现异常简洁？
在__introsort_loop函数实现中，第一眼看上去似乎只有右分支递归，而忽略了左侧分支？
这一切都是为了效率。
STL将 __introsort_loop 放在了while循环中，寻找到分割 [__first, __last)区间的分割点__cut后，每次先进入右分支递归，在右侧分支递归回来之后，下一步是：
__last = __cut;
这样，在下一个循环中进入左分支。
相比较常规快排实现，最直观的感受，就是减少一次函数调用的开销。此外，进入左分支后，可能就不满足__last - __first > int(_S_threshold) 限制条件，那么当前循环就退出了，避免递归。
因此，当 __introsort_loop函数因不满足_S_threshold阈值条件，逐层返回到std::__sort函数中时，完整的[__first, __last)区间中会有许多元素个数小于_S_threshold的无序区间，他们的有序性留给最后的插入排序__final_insertion_sort函数来完成。
std::__unguarded_partition_pivot
快排的最后一点，我们来看看STL是如何寻找分割位置__cut 的。这一部分是由__unguarded_partition_pivot函数实现。
template <typename _RandomAccessIterator, typename _Compare>
inline _RandomAccessIterator
__unguarded_partition_pivot(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Compare __comp)
{
0 + (5-0)/2 = 2
// 中间位置
_RandomAccessIterator __mid = __first + (__last - __first) / 2;
// 取三点的中值，并置于 __first 处
std::__move_median_to_first(__first,
__first + 1, __mid, __last - 1,
__comp);
// 对 [__first, __last) 进行分割，并返回分割点 __cut
return std::__unguarded_partition(__first + 1, __last, __first, __comp);
} __unguarded_partition_pivot的实现分为两步：
- 选择一个轴点
pivot，用于后续比较。 - 基于该轴点
pivot分割[__first, __last)区间，使得[__first, __cut)区间的元素不大于pivot，[__cut, __last)区间的元素不小于pivot。
下面从这两点进行讲解。
std::__move_median_to_first
__move_median_to_first函数，用意很明显，就是找出__a、__b、__c的中值，并将这个中值放在__result位置处。因此，根据传入参数，就是找出__first+1、__mid、__last-1三个位置的中值，并将中值和__first位置的值进行交换。
这个函数比较简单，其中的iter_swap函数是交换两个迭代器指向的值，具体代码解释如下。
template <typename _Iterator, typename _Compare>
void
__move_median_to_first(_Iterator __result,
_Iterator __a, _Iterator __b, _Iterator __c,
_Compare __comp)
{
// __a < __b
if (__comp(__a, __b))
{
// __a < __b < __c
if (__comp(__b, __c))
std::iter_swap(__result, __b); // __b
// __a < __c <= _b
else if (__comp(__a, __c))
std::iter_swap(__result, __c); // _c
else
// __c <= __a < __b
std::iter_swap(__result, __a); // _a
}
// __b <= __a < __c
else if (__comp(__a, __c))
std::iter_swap(__result, __a); // __a
// __b <= c <= a
else if (__comp(__b, __c))
std::iter_swap(__result, __c); // _c
else
// __c <= _b <= __a
std::iter_swap(__result, __b); // _b
} std::__unguarded_partition
上面找到待比较的轴点pivot之后，下面就是分割[__first, __last)区间。
分割的核心思想：寻找分割位置__cut，使得[__first, __cut)区间的元素都不大于 pviot，[__cut, __last)区间的元素都不小于pivot，然后返回分割点__cut的位置。
这部分代码讲解，见下面代码注释。
template <typename _RandomAccessIterator, typename _Compare>
_RandomAccessIterator
__unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last,
_RandomAccessIterator __pivot,
_Compare __comp)
{
while (true)
{
while (__comp(__first, __pivot)) ++__first; // *__first < *__pivot
/*** 跳出循环时，满足：*__first >= *__pivot ***/
--__last;
while (__comp(__pivot, __last)) --__last; // *__pivot < *__last
/*** 跳出循环时，满足：*__pivot >= *__last ***/
if (!(__first < __last)) // __fist >= __last ，表示左右边界相遇，此轮遍历结束
return __first; // 返回分割点位置
/** 经过上面两个while循环，
* 此时： *__first >= *__pivot && *__pivot >= *__last
* 不满足分割要求，因此需要交换__first, __last 两点的值
*/
std::iter_swap(__first, __last);
++__first;
}
} by the way
__unguarded_partition函数，有个__unguarded 前缀，表示这个函数里没有越界检测。
那么问题来了，为什么可以没有越界检测？
以pivot左侧的区间为例：
// 无越界检测版本 while (__comp(__first, __pivot)) ++__first; // 常见实现版本 while (__first < __last && __comp(__first, __pivot)) ++__first;
首先，明确两点：
__unguarded_partition中传入参数__first，实际上是__unguarded_partition_pivot函数中的__first+1位置；__unguarded_partition中传入参数__pivot，实际上是__unguarded_partition_pivot函数中的__first位置。
__pivot是__unguarded_partition_pivot函数中的三个点（__first+1、__mid、__last-1）的中值，即__pivot值肯定并不是最大的。
因此，在__unguarded_partition函数中：
++__first时，肯定存在一个点__pos，其值不小于__pivot处的值；- 要使得
__comp(__first, __pivot)为true，必须是*__first < *__pivot； - 又因为至少存在一个点
__pos，满足*__pos >= *__pivot，使得__comp(__first, __last)为false，
因此，__first > __last的越界情况就不会发生，最终__first会在某个位置停下。同理右侧区间的判断。
因此，即使不要边界检测，也不会发生越界错误。
隐藏的BUG
但是注意了，__unguarded_partition函数，没有引入边界检测仍能正确运行，是基于正确的比较器算法。可当用户传入错误的比较器算法时，比如本文开篇自定义的比较器算法，就容易产生BUG，还是难以检测的BUG。
打开cppreference，可以看到STL要求std::sort的比较器是符合严格弱序性质的，其中容易导致BUG的是这么一条：
当比较器对象comp传入两个相等对象，返回值必须是false！！！
如果不符合严格弱序性质，则会在某些数据下会导致coredump。
假设某个小区间，数据分布如下：
数据： 1 1 1 2 1
索引： 0 1 2 3 4
^ ^ ^
p f l按照__move_median_to_first函数中轴点选择法，最终选出的pivot是索引为1处的值，然后索引0、1值互换。
为便于下文分析叙述：pivot简写为p，first简写为f，last简写为l。
case1：比较器符合严格弱序关系
当std::sort传入的比较器Compare符合严格弱序关系，对该数据执行到__unguarded_partition函数时，迭代流程如下：
第一轮迭代后：
数据： 1 1 1 2 1
索引： 0 1 2 3 4
^ ^ ^
p f l第二轮迭代后：
此时last指针，到了first的位置，迭代结束。
数据： 1 1 1 2 1
索引： 0 1 2 3 4
^ ^
p f/l 此时，分割点__cut就是first，其左侧的元素不比pivot大，其右侧不比pivot小。
case 2： 比较器不符合严格弱序关系
当std::sort传入的比较器Compare符合严格弱序关系，即comp(a,a)==true，再执行到__unguarded_partition_pivot函数时，迭代流程如下：
第一轮迭代：
实际上，在第一轮迭代中，last指针就越界了。
因为last在左移的过程中，其取值依次是2、1、1、1，都会使得comp(pivot, last)返回true，进而导致语句 while (__comp(__pivot, __last)) --__last;一直执行，最终就导致last越界。
数据： 1 1 1 2 1
索引： 0 1 2 3 4
^ ^
l p f总结来说，严格弱序关系，能保证 ：
while (__comp(__first, __pivot)) ++__first;在++__first的过程中，不会越界。原理还是上面分析的那样，即使
__first+1、__mid、__last-1三个值都是相等，取得的轴点pivot在弱序关系中，使得comp(__first, __pivot)一直为false，这样while循环就进行不下去。如果没有严格弱序关系保证，则就会越界。
while (__comp(__pivot, __last)) --__last;原理同上。
为了验证上面这个猜想，我自己写了个demo。
在数组vec里全是一样的数字，数组元素个数必须超过_S_threshold阈值（默认值16）才能触发std::sort的快排行为。
注意，代码必须在MSVC下编译运行，因为GCC对于某些越界行为并不报错，不如MSVC严格（没有测试clang）。
#include <vector>
#include <algorithm>
int main(int argc, char const* argv[]) {
std::vector<int> vec{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; // 全是一样的元素，且必须超过16个元素
std::sort(vec.begin(), vec.end(),
[](const int& lhs, const int& rhs)
{
return lhs <= rhs; // BUG，修改为: return lhs < rhs; 才行
});
return 0;
} __depth_limit
好嘞，下面开始讲解第【2】个限制条件__depth_limit。
当快排的递归深度，达到阈值 __depth_limit时，STL使用堆完成当前[__first, __last)区间的排序。下面我们把快排部分去掉，只看堆排序部分，那么 __introsort_loop 函数的while循环可简洁如下：
while (__last - __first > int(_S_threshold)) {
if (__depth_limit == 0) {
std::__partial_sort(__first, __last, __last, __comp);
return;
}
//...
} 显而易见，堆排是由__partial_sort函数完成。
std::__partial_sort
__partial_sort函数，旨在取出 [__first, __last)区间前__middle - _frist个最小元素，并将其按照_Cpmpare比较策略进行排序后，有序存放在 [__first, __middle)区间，其余的节点放在[__middle, __last)区间。
__partial_sort函数实现如下（关于堆的实现，可以参考侯捷老师的《STL源码剖析》书籍）。
// 上层调用
std::__partial_sort(__first, __last, __last, __comp);
// 函数原型
template <typename _RandomAccessIterator, typename _Compare>
inline void
__partial_sort(_RandomAccessIterator __first,
_RandomAccessIterator __middle,
_RandomAccessIterator __last,
_Compare __comp)
{
// 先建堆，并使 [first, middle) 区间存放前 middle-first 个最小值
std::__heap_select(__first, __middle, __last, __comp);
// 对 [first, middle) 区间元素进行排序
std::__sort_heap(__first, __middle, __comp);
} 因此，经过 __partial_sort函数后：
[__first, __middle)区间，有序存储了[__first, __last)区间的前__middle - _frist个最小元素；[__middle, __last)区间，无序存储[__first, __last)区间剩余元素。
在 __introsort_loop 函数中调用 __partial_sort 函数时，__middle参数和__last参数都是__last，因此实现的就是[__first, __last)区间的全排序。
std::__final_insertion_sort
当 __introsort_loop 函数执行完毕，最后一步需要将整个数据变得有序，这由__final_insertion_sort函数完成。
在讨论 __final_insertion_sort之前，先回顾下 __introsort_loop函数，它返回有两种可能：
_S_threshold：递归到某个[__first, __last)区间时，其元素个数__last - __first <= _S_threshold时，结束递归。__introsort_loop函数返回到std::__sort函数时，整个大的区间中还存在一些元素个数不足_S_threshold的小区间仍然是无序的。__depth_limit：递归层次超过限制__depth_limit。
因此，当执行__final_insertion_sort函数时，当前大区间[__first, __last)只存在局部无序，主体上是有序的。这种情况，非常适用于插入排序，此时时间复杂度是O(N)。
为了进一步优化，加速排序的速度，STL针对两种情况分别求解。
template <typename _RandomAccessIterator, typename _Compare>
void
__final_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Compare __comp)
{
// 大数据量
if (__last - __first > int(_S_threshold))
{
std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, __comp);
}
else
// 小数量量直接使用插入排序，不用经过快排、堆排
std::__insertion_sort(__first, __last, __comp);
} std::__insertion_sort
__insertion_sort函数是按照标准的插入排序实现。
插入排序的核心思想：将整个序列视为两个部分，『有序的前缀』和『无序的后缀』，再通过循环迭代，不断地将后缀的首元素转移插入到前缀中，保持前缀仍然有序。当后缀为空，整个序列有序。
时间复杂度：如果当前序列已经完全有序，则插入排序时间复杂度是
O(N)，完全逆序则O(N^2)。
运行到 __insertion_sort时，整个数据规模主体保持有序，局部小区间无序，非常适合使用插入排序，算法步骤如下：
- 初始状态下，前缀序列中只有
__first一个元素，后缀序列则是[__first+1, __last)区间的元素； - 对
[__first+1, __last)区间的元素进行遍历，不断将后缀序列的首元素，插入到前缀序列中。
在 __insertion_sort函数中，对于后缀序列[__first+1, __last)区间的每个元素__i：
先判断
__i位置的元素是否小于__first；如果是，则直接将
[__first, __i)区间的元素整体后移一位，再将__i位置的元素插入到原先__first位置处。这样就避免了从__i位置一路比较到__first位置，才找到__i在前缀序列中的待插入位置，即节省了比较开销。如果否，则需要在
(__first, __i)区间寻找合适的位置__pos，使得*(__pos-1) <= *__i < *__pos这个部分是由
__unguarded_linear_insert函数完成，这个函数前面也有__unguarded前缀，也是没有边界检测的意思。
__insertion_sort函数，整个代码解释如下。
template <typename _RandomAccessIterator, typename _Compare>
void
__insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Compare __comp)
{
if (__first == __last) return;
/*** 下面要将 (fist, last) 区间的每个元素 __i 都插入到前缀序列中 ***/
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
{
/* case 1: *__i < *__first 时，则将 [__first, __i)区间后移，
* 再将 *__i 插入到原先 __first 位置
*/
if (__comp(__i, __first))
{
auto __val = std::move(*__i); // 待插入的值
std::move_backward(__first, __i, __i + 1); // 将 [_first, _i) 区间的元素朝后移动一个位置
*__first = std::move(__val); // 将 __i 位置处的值移动到 __first 处
}
else
{
/* case 2: *__i >= *__fist 时，
* 此时需要在有序前缀 (fist，_i)区间中，寻找合适的位置再插入
*/
std::__unguarded_linear_insert(__i, __gnu_cxx::__ops::__val_comp_iter(__comp));
}
} // for-end
} std::__unguarded_linear_insert
__unguarded_linear_insert函数，在有序前缀(__first, __last)中寻找合适的位置__pos，将__i位置的值插入到__pos处。
那什么叫合适的位置呢？
从__i-1的位置开始遍历，第一个出现逆序对的位置__pos，即：
__pos < __i，且*(__pos-1) <= *__i < *__pos。
当找到这么个位置，需要将[__pos, __i)区间的元素，后移一位，然后将__i位置的元素插入到__pos。为了实现这一步，STL在 __unguarded_linear_insert函数中，边遍历、边把当前位置的元素向后移动。
下面是__unguarded_linear_insert函数的源码分析。
template <typename _RandomAccessIterator, typename _Compare>
void
__unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
{
auto __val = std::move(*__last); // 当前待插入的值 __val
_RandomAccessIterator __next = __last;
--__next; // 需要在有序前缀区间 (first, last)中遍历，因此开始遍历的位置需要 --next
/* __comp(__val, __next) 为false时，表示出现逆序：
* + __next 指向当前遍历位置
* + __last 用于指向 __next 的上一个位置
*/
while (__comp(__val, __next))
{
/** 下面是将当前遍历位置 __next 存储到 __last ***/
*__last = std::move(*__next); // 将当前位置的值后移动一位
__last = __next; // __last 前移
--__next; // __next 前移
}
/* 以上while循环，相当于将 [__last, __i) 区间的元素，后移动了一位，
* 现在找到合适位置，此时：*__next <= val && val < *last
* 因此，将 val 插入到上一个节点位置
*/
*__last = std::move(__val);
} __unguarded_linear_insert 为啥能不用检测是否越界？
因为，之所以能进入__unguarded_linear_insert函数，是因为在__insertion_sort函数中有了 __i >= __first。因此在此函数中，再不济，while(__comp(__val, __next))也会在__first后一个位置停下来，最终插入在___first+1处。
免去边界检测，可以实现一定程度上的优化（STL对性能真的是锱铢必较）。
在这，你可能在想这个 __unguarded_partition函数，会存在之前在 __unguarded_partition中出现的BUG吗？
理论上是应该要出BUG的，这也是符合CPP标准，但是从上面的GCC的源码实现可以看出，GCC下不会出现BUG。下面的代码在MSVC中运行被中止，而GCC的实现却可以正常运行：
#include <vector>
#include <algorithm>
int main(int argc, char const* argv[]) {
std::vector<int> vec{1,1};
std::sort(vec.begin(), vec.end(),
[](const int& lhs, const int& rhs)
{
return lhs <= rhs;
});
return 0;
} 因为，在GCC下，会进入__insertion_sort函数的if (__comp(__i, __first))条件分支中，不断地将[__first, __i]区间元素后移动一位，避免了报错。尽管避免了报错，但实际上却不符合CPP标准。
因此，在书写自定义比较器算法时，要使其符合「严格弱序关系」，代码才具有移植性。
到此，std::sort的整个运行流程大致分析完毕。
附录
题目是leetcode-56。以下是源码：
class Solution {
public:
std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals) {
if(intervals.size() ==1)
return intervals;
std::sort(intervals.begin(), intervals.end(),
[](const std::vector<int> &lhs,const std::vector<int> &rhs)
{
return lhs.at(0) <= rhs.at(0); // BUG
});
std::vector<std::vector<int>> ans;
ans.emplace_back(std::move(intervals[0]));
for(int i=1; i < intervals.size(); ++i) {
auto&& interval = std::move(intervals[i]);
if(interval[0] > ans.back()[1]) {
ans.emplace_back(std::move(interval));
}
else if(interval[1] <= ans.back()[1]) {
continue;
}
else {
ans.back()[1] = std::move(interval[1]);
}
}
return ans;
}
}; 写完这篇blog，脑袋距离小卤蛋又进了一步。
全部评论
(0) 回帖