C++ sort自定义比较函数触发std::bad_alloc崩溃原因咨询
问题现象
运行C++学生成绩排序代码处理对应输入时,程序异常崩溃,抛出如下错误:
terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc signal: aborted (core dumped)
两版自定义比较函数的预期排序逻辑完全一致:按成绩降序排列,成绩相同时按姓名字典序升序排列,但只有替换比较函数后程序才能正常运行。
存在缺陷的原始代码
#include <iostream> #include <vector> #include <algorithm> using namespace std; bool func(pair<string, int> a, pair<string, int> b) { if(a.second > b.second) { return true; } else if (a.second == b.second) { if(a.first > b.first) { return false; } return true; } return false; } vector<pair<string, int>> sortMarks(vector<pair<string, int>> v, int N){ sort(v.begin(), v.end(), func); return v; } // Driver code int main() { int testcase = 1; while(testcase--){ int N; cin >> N; // Declaring vector vector<pair<string, int>> v; // Taking input to vector for(int i = 0;i<N;i++){ string s; cin >> s; int k; cin >> k; v.push_back(make_pair(s, k)); } v = sortMarks(v, N); // Printing student name with their marks for(auto it = v.begin(); it!=v.end();it++){ cout << it->first << " " << it->second << endl; } } return 0; }
可正常运行的比较函数实现
bool func(pair<string, int> p1, pair<string, int> p2){ if(p1.second == p2.second){ return p1.first < p2.first; } else return p1.second > p2.second; }
崩溃根本原因
C++标准库的std::sort要求传入的自定义比较函数必须满足严格弱序规则,其中最基础的一条要求是反自反性:对于任意元素x,comp(x, x)必须返回false,也就是元素不能排在自身前面。
- 第一版比较函数违反了该规则:当两个待比较元素完全相等(成绩相同、姓名也相同)时,代码进入成绩相等的分支后,判断
a.first > b.first结果为false,最终会返回true,等价于判定「元素a应该排在a自身前面」,属于非法的比较逻辑。 - 传入不满足严格弱序的比较器时,
std::sort的执行会触发未定义行为。std::sort底层通常是结合快排、插入排序、堆排序的内省排序实现,非法比较器会导致排序过程中出现数组越界、递归深度失控、内存大小计算错误等问题,本次报错的std::bad_alloc就是未定义行为的具体表现——排序逻辑错误后程序误申请了远超系统可用上限的内存空间,触发内存分配失败异常,最终崩溃。 - 第二版比较函数完全符合严格弱序要求:当两个元素完全相等时,不管是成绩相等分支下的
p1.first < p2.first,还是成绩不等分支的判断,都会返回false,比较逻辑合法,因此排序可以正常执行。
内容的提问来源于stack exchange,提问作者CuddlyTriangle
相关产品推荐
相关产品推荐

