LeetCode合并区间自定义sort比较器触发空指针错误原因解析
运行时错误的根本原因
错误本质是自定义排序比较器违反了C++标准对std::sort的强制约束,触发了未定义行为。
标准对排序比较器的核心要求
C++标准规定,传入std::sort的比较器必须满足**严格弱序(Strict Weak Ordering)**规则,最关键的约束是:
- 对任意两个待比较的元素a、b,不允许同时出现
comp(a, b) == true和comp(b, a) == true的结果。
所有违反该规则的比较器都会让排序算法进入未定义状态,LeetCode启用的未定义行为检测工具会捕获这类问题,抛出你看到的空指针绑定类报错。
错误版本比较器的问题
你最初写的比较器,在区间左端点相等的分支里,使用了e1[1] <= e2[1]作为返回判断:
// 错误的左端点相等分支 if (e1[0] == e2[0]) { return e1[1] <= e2[1]; }
举个直接的触发场景:当两个完全相同的区间,比如[1,3]和[1,3]进入比较逻辑时:
- 比较顺序为a在前、b在后时,满足
e1[1] == e2[1],e1[1] <= e2[1]返回true - 比较顺序反过来,b在前、a在后时,同样满足相等条件,逻辑还是返回
true
这就直接打破了严格弱序的核心约束——比较器同时认为a应该排在b前面、b也应该排在a前面。std::sort的底层分区、交换逻辑在这种自相矛盾的比较结果下,会出现访问越界、定位到无效内存的问题,最终触发运行时崩溃。
修改后版本正常的原因
把判断逻辑从<=换成<之后:
// 符合要求的比较逻辑 if (e1[0] == e2[0]) { return e1[1] < e2[1]; }
当两个元素完全相等时,不管比较顺序怎么换,两个方向的比较都会返回false,完全符合严格弱序的要求——相等元素不强制排序先后,排序逻辑可以稳定运行。
小补充
实际上在合并区间这个场景里,左端点相等的区间谁在前谁在后完全不影响后续合并逻辑,甚至可以省略左端点相等时的内层比较分支,但无论怎么简化比较逻辑,都必须保持“严格小于”的语义,绝对不能在返回判断里带上等号。
内容的提问来源于stack exchange,提问作者Yves
相关产品推荐
相关产品推荐

