为何C++排序函数仅支持Strict Weak Ordering（严格弱序）？

问题描述 #

严格弱序（SWO，例如std::less、std::greater）和非严格弱序（NSWO，例如std::less_equal、std::greater_equal）都能完成元素排序与等价元素查找的工作，这对实现set、map这类关联容器至关重要。但实际使用中，即使将NSWO比较器传入std::sort，似乎也能正常完成排序。那么为什么C++标准要求排序函数的比较器必须遵循严格弱序？使用NSWO作为排序比较器存在哪些隐患？

核心解答 #

一、标准要求严格弱序的本质原因：算法逻辑依赖SWO的规则 #

C++的排序算法（如std::sort）、关联容器（set/map）的内部实现，核心依赖严格弱序定义的等价关系——它们默认通过!comp(a,b) && !comp(b,a)来判断两个元素等价。

严格弱序必须满足四个核心规则：

• 非自反性：comp(a,a)必须返回false
• 不对称性：若comp(a,b)为true，则comp(b,a)必须为false
• 传递性：若comp(a,b)和comp(b,c)都为true，则comp(a,c)必须为true
• 等价传递性：若a与b等价、b与c等价，则a与c也等价

而NSWO（比如std::less_equal）直接打破了非自反性（comp(a,a)返回true），这会让所有依赖等价判断的逻辑彻底失效：

• 关联容器会无法识别相同元素，导致重复插入、查找失败；
• 排序算法的内部分区、交换逻辑是基于SWO设计的，NSWO会触发未定义行为。

二、使用NSWO作为排序比较器的隐患 #

• 未定义行为风险：C++标准明确规定，若比较器不满足SWO，算法行为是未定义的。这意味着当前测试正常的代码，换编译器、平台或数据规模后，可能出现崩溃、死循环、排序结果错误等问题。
• 等价判断混乱：处理重复元素时，NSWO会让comp(a,b)和comp(b,a)同时为true，算法无法正确识别等价元素，导致无意义的交换操作，降低排序效率，甚至破坏std::stable_sort的稳定性。
• 关联容器彻底失效：若将NSWO传入std::set或std::map，内部平衡树的结构会因等价判断错误被破坏，插入、删除、查找操作都会出现逻辑错误，比如无法去重、查找不到已存在元素、遍历结果乱序等。

三、为何有时NSWO看起来能正常排序？ #

这只是巧合：当测试数据集元素全不重复时，NSWO的行为和SWO几乎一致；或者编译器的std::sort实现刚好能“容错”这种违规用法。但只要出现重复元素，或更换实现环境，问题就会立刻暴露。

内容的提问来源于stack exchange，提问作者Sourav Kannantha B