std::sort coredump 说起
std::sort coredump 说起
@(c++)
core 的原因
c++ 标准库 sort() 默认采用 < 这个 operator 来排序的, 另个一个重载函数增加第三个参数，指定一个比较的函数，函数接受两个参数。 对于基础类型（int，float..），直接调用 sort(start,end) 即可，对于非基础类型的结构体，可以通过重载对象的 < 运算符或者提供一个比较函数。 详见
本文从一个 core 说起 相信很多人在编写使用 sort 都在这个地方翻车，
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class CompareGreater {
public:
bool operator()(const int* left, const int* right)
{
return *left >= *right;
}
};
int main(int argc, char *argv[])
{
vector<int *> verPInt;
for (int i = 0; i < 18; i++) { // will coredump
int *pInt = new int;
if (pInt == NULL) {
cout << "new faile" << endl;
goto final;
}
*pInt = 1;
verPInt.push_back(pInt);
}
sort(verPInt.begin(), verPInt.end(), CompareGreater());
for (vector<int *>::iterator iter = verPInt.begin(); iter != verPInt.end(); ++iter) {
cout << **iter;
}
cout << endl;
final:
for (vector<int *>::iterator iter = verPInt.begin(); iter != verPInt.end(); ++iter) {
delete *iter;
*iter = NULL;
}
return 0;
}gdb 查看堆栈，发现是 core 在比较函数里面。
Program terminated with signal SIGSEGV, Segmentation fault.
#0 0x000055e88121e00c in CompareGreater::operator()(int const*, int const*) ()上述代码，所有元素值相同，当个数大于等于 16个 的时候就会 coredump，查看说明，core 的原因是 ：
<font color=#0099ff size=5>std::sort()在排序时，比较函数对相等的元素应该返回 false！如果返回 true，会导致程序coredump</font>
因为定义 cmp(x,x) 返回 true 不符合 Strict_weak_orderings，标准库算法里面很多都要求满足 Strict_weak_orderings，使用时需要格外注意，避免翻车。
上述例子代码只需修改比较函数中，将 >= 改为 >即可修复。
为什么是元素个数大于等于 16个 呢，从 STL 源码可以发现，由于 std::sort() 的排序分2种，当元素个数 >16 <font color=#0099ff>(_S_threshold = 16)</font> 时选择快速排序，<=16 个则选择插入排序 (对象少时快排性能不理想)。按照快排原理，每次都是遍历所有值和一个中间值比较，小的放左边，大的放右边。从STL源代码可看出，std::sort() 在遍历比较时，是没有加边界保护的。如果比较相等的元素返回真，则在极端情况下 (如所有元素值相等时) __first 会出现访问越界，导致coredump。
STL 源码 : /usr/include/c++/7/bits/stl_algo.h（具体目录）
深层次的坑
写测试代码时候，发现比较元素从 vector<int *> 改为 vector<int>，比较函数同样错误的写为 >=，运行程序并不会 core，但是打印比较好的数据，发现数据错了！！坑爹啊，这样的坑更深沉。