C++ sort和set的comp函数注意事项

"Strict Weak Ordering"概念

Binary function that accepts two elements in the range as arguments,
and returns a value convertible to bool. The value returned indicates
whether the element passed as first argument is considered to go before
the second in the specific strict weak ordering it defines.

里面提到了"Strict Weak Ordering"的概念,它要求必须满足以下的条件:
std::sort、std::stable_sort、set红黑树等都需要满足这个特性。

(1)反自反性:即comp(x, x)必须是false
(2)非对称性:即若comp(x, y)和comp(y, x),其结果必然相反
(3)可传递性:即若comp(x, y)为true, comp(y, z)为true,那么comp(x, z)必然为true

违反的后果

1.std::sort

分区逻辑崩溃:快速排序的边界失效
std::sort 底层采用 内省排序(Introsort),结合快速排序、堆排序和插入排序。其分区逻辑依赖比较函数的严格性:

快速排序分区:以基准值(pivot)划分区间,要求 comp 能明确区分“小于”和“大于”关系。
错误触发场景:
若 a == b 时返回 true,分区函数可能将元素错误归类到“小于”或“大于”区间,导致分区点计算错误。
分区指针越界,写入或读取无效内存(如 vector 边界外),破坏容器内存结构。
典型现象:
排序后 vector 内存数据被篡改(如 0x55555576df30 地址的 1,1,1,1 被改为 1,0,1,1)。
析构时触发 double free 或 corruption 错误。

2.std::stable_sort

当 a.num == b.num 时,函数返回 true,算法可能反转相等元素的原始顺序。
结果:本应稳定的排序变为不稳定,且可能引发未定义行为。

3.std::set

关联容器的等价性判断失效
关联容器(如 std::set)同样依赖严格弱序判断元素等价性:
等价性定义:!(comp(a, b)) && !(comp(b, a)) 为 true 时,a 与 b 等价。
错误影响:
若 a == b 时 comp(a, b) 返回 true,则等价性判断恒为 false,容器误判为不等价元素,破坏唯一性。
内部红黑树结构可能因节点重复插入而失衡,导致未定义行为。

参考

csdn,
https://zhuanlan.zhihu.com/p/401616141
cplusplus, https://www.cplusplus.com/reference/algorithm/stable_sort/
《Effective STL》 条款21: 永远让比较函数对相等的值返回false
SGI-STL, http://www.sgi.com/tech/stl/StrictWeakOrdering.html

发表评论

您的邮箱地址不会被公开。 必填项已用 * 标注

Contents
滚动至顶部