转载自沙子泥巴刘的博客
前言
最近被一个在sort自定义排序导致的崩溃问题, 弄得焦头烂额. 后在网上看了这篇文章, 才解决问题, 转载一次.
正文
近期我们开发的一个工具在调用c++ sort函数对数组进行排序时居然会导致进程崩溃,此问题细节我觉得对于类似我这种不常用stl的同学可能不容易觉察,这里简单总结下。
出错代码
因为代码太复杂不好展示,我这里就用下面这个简单的示例来描述。
#include <algorithm>
bool comp(int d1, int d2)
{
return d1 >= d2;
}
const int N = 50;
int main()
{
int d[N];
for(int i = 0; i < N; ++i)
{
d[i] = 20;
}
std::sort(d, d + N, comp);
return 0;
}
不知你是否直觉上也会觉得这段代码没什么问题,但是这段代码运行后会core dump。查看core文件可以看到内存里的栈被写坏了,这说明sort调用导致了内存越界访问,在这么少的代码行下,不难判定应该是comp函数实现可能不符合c++标准库的某种规则(C++ STL是基于concept的设计和实现)。
comp函数应该怎么写
带着这个疑问我去查了下c++ stl手册(http://www.cplusplus.com/reference/algorithm/sort/),发现sort函数对于comp函数还真有一个特殊的要求,叫做“Strict Weak Ordering”。什么意思呢,它大概可以这么解释:如果一个comp函数要满足“Strict Weak Ordering”,意味着它应该满足如下特征(更多细节可以参见SGI版实现相关描述http://www.sgi.com/tech/stl/StrictWeakOrdering.html):
(a) 反自反性:也即comp(x, x)必须是false
(b) 非对称性:也即如果comp(x, y)和comp(y, x)的结果必然相反
(c) 可传递性:也即如果comp(x, y)为true,comp(y, z)为true,那么comp(x, z)必然为true
这么看到,示例代码的comp定义明显违反了(a)(b)两条,所以sort使用它时就可能工作不正常。解决办法也很简单,去掉那个“=”,再对照下”Strict Weak Ordering”的定义,应该是满足了的。
sort调用细节还原
带着好奇心,我还是想弄明白不符合规范的comp到底在sort中哪个环节出了什么问题, stl为什么要求使用者符合“Strict Weak Ordering “规则呢?那就翻看下源代码好好认识下sort函数实现(/usr/include/c++/4.1.2/bits/stl_algo.h)
sort:先看下sort函数,它本身很简单,把整个排序过程分为introsort和insertion_sort两个阶段。
introsort:这个函数的功能是对数组进行排序,思路和普通的quicksort很相似。选个“哨兵“(Pivot,也即下面__cut变量)出来,然后把数组一分为二,接着对分出来的两块递归排序。和普通quicksort不同的是,当输入的数组长度小于16(_S_threshold定义)时,它就不管了(把这个工作丢给了sort函数第二阶段处理,也即__final_insertion_sort函数)。另外,调用方可以通过参数__depth_limit来限制递归和循环深度(我们都知道,快排在worst-cast下性能很差的),一旦发现调用深度达到这个限制,就直接启用堆排序(partial_sort)。Introsort是个有名的算法,大家可以wiki它了解更多设计细节。
上面这个introsort我个人觉得可读性不是很好,原因是它对数组左半部【__first, __cut]部分使用递推(while循环),而对数组右半部分【__cust, __last]采用递归调用,如果写成下面这个样子估计会好懂很多。
__insertion_sort:这也挺好懂,依次遍历a[1]~a[N-1],将它与a[0]比较,如果a[i]应该排在a[0]前(2303行),那么将a[0]~a[i]部分向后移动一格(copy_backward),然后设置a[0] = a[i]。如果a[i]应该排在a[0]后(2383行),那么转入__ungarded_insertion_sort(实际就是将a[i]与a[i-1]比,如果a[i]应该排在a[i-1]前,那么把a[i-1]向后挪一格,然后将a[i]与a[i-2]比…),具体实现细节见后文
__unguarded_insertion_sort:依前文,数组a[16]~a[N]部分交给这个函数处理,它使用的__unguarded_insertion_insert来完成插入排序。
__unguarded_linear_insert: 这函数名起得就感觉不够安全啊。从代码分析来看,就是给定一个指针__last和待插入的值__val,只要通过调用comp函数判断__val应该在__last前,我们就将__last向后搬动一格(2253~2255行),当其停止时就将__val插入在停止的位置
这时再看看我们提供的comp函数,当输入数组全部相同时,comp调用永远都返回true,也即2251行肯定会跑出数组范围(内存越界),并且一路改写(2253行),直到碰到一个内存值恰巧使得2251行停下来。
把前面的代码综合来看,sort函数设计思路大概是这样的:
首先,它通过introsort把数组分作几个段(段的长度不超过_S_threshold,即16),一个段内可以是无序的,但是段与段之间是有序的(例如,第二段的数据一定都排在第一段数据后面)。然后,对于第二段之后的数据,就使用_unguarded_linear_insert来一个一个插入排序。
那么我们函数错哪儿了呢?按设计思路,经过introsort后,第二段任意数据d2和第一段任意数据d1,comp(d2, d1)结果一定是false(false表示d2应该在d1后面),这就是2251行代码退出的保障,但是我们提供的函数返回的却是true。这就导致代码行2251~2256在寻找插入的位置时会越界访问。
小结:翻看下stl其它函数需提供comp的函数,基本都要求满足Strict Weak Ordering,可见理解该概念对于用好stl还是挺重要的。
欢迎大家订阅雀观代码, 我将给你讲述, 中小企业程序员, 淘金路上的故事.