C++ std::sort 的比较器 ＜= 和 ＜ 只差一个字符，行为却天差地别

C std::sort 的比较器和只差一个字符行为却天差地别flyfishC 排序代码能编译、能运行、大多数时候结果还是对的但一旦数据里出现相等元素它就会以各种诡异的方式出错。一、先说一个场景假设在维护一段视频流处理的代码里面有一个按时间戳排序的函数autometaDataSortFunc[](constautoa,constautob){returna.secondb.second;// 按时间戳排序两个时间戳相等时返回 true};这段代码某天出现了一条报错排序结果错乱某些帧的元数据顺序不对。和只差一个字符行为却天差地别。前者让整个 std::sort 进入未定义行为程序的所有异常表现都是它的直接后果。二、一段看起来没问题的代码先看一段典型的错误写法#includealgorithm#includeiostream#includeutility#includevectorintmain(){std::vectorstd::pairstd::string,intv{{b,2},{a,1},{c,3},{a,1}};autobadCmp[](std::pairstd::string,inta,std::pairstd::string,intb){returna.secondb.second;// 错误应为 };std::cout[sort] sorting with invalid comparator (UB)...\n;std::sort(v.begin(),v.end(),badCmp);for(autop:v)std::coutp.first:p.second ;std::cout\n[sort] done\n;return0;}注意数据里的两个元素 {“a”, 1} 和 {“a”, 1}它们的 second 都是 1。这是触发缺陷的关键。运行这段代码在 MSVC 的 Debug 配置下程序会直接触发断言并终止输出 invalid comparator 的报错信息。templateclass_Pr,class_Ty1,class_Ty2_NODISCARDconstexprbool_Debug_lt_pred(_Pr_Pred,_Ty1_Left,_Ty2_Right)noexcept(noexcept(_Pred(_Left,_Right))_Debug_lt_pred_order_check_noexcept_Pr,_Ty1,_Ty2){constauto_Resultstatic_castbool(_Pred(_Left,_Right));ifconstexpr(_Enable_debug_lt_pred_order_check_Pr,_Ty1,_Ty2){if(_Result){_STL_VERIFY(!_Pred(_Right,_Left),invalid comparator);}}return_Result;}在 Release 配置下结果不确定我的测试是没有返回任何错误通过了编译运行[sort]sorting with invalidcomparator(UB)...a:1a:1b:2c:3[sort]done为什么结果不确定因为标准库对这个场景没有任何承诺。传入非法比较器调用 std::sort属于未定义行为。三、比较器到底在回答什么问题std::sort 接受一个可调用对象 comp它的语义是comp(a, b) 返回 true表示a 排在 b 前面或者说a 严格小于 b。这里的关键词是严格。严格小于意味着a 和 b 相等时comp(a, b) 必须返回 false因为 a 并不严格小于 b。a 和 b 相等时comp(b, a) 也必须返回 false理由相同。的问题就在这里。a 和 b 相等时a b 为 trueb a 也为 true。两个方向同时成立等于同时宣称a 在 b 前面和b 在 a 前面排序算法面对这种自相矛盾的答案行为没有任何保证。四、严格弱序仿照小于制定的检查清单严格弱序是一个数学概念C 标准借用了它。要理解它先想清楚我们熟悉的小于关系。在自然数上1 小于 22 小于 33 不小于 3。这些性质看起来不言而喻但小于之所以可靠是因为它恰好满足以下四条规则。严格弱序就是把这四条规则抽出来作为任何比较器都必须通过的检查清单。规则一非自反性任何元素都不能严格小于自身。comp(a, a) 必须为 false。3 不小于 3。如果比较器是comp(3, 3) 等于 3 3为 true这一条直接不合格。规则二反对称性两个方向不能同时成立。若 comp(a, b) 为 true则 comp(b, a) 必须为 false。1 小于 2 成立2 小于 1 就不允许成立。否则排序算法会在同一个元素对上得到互相矛盾的答案。规则三传递性小于可以接力。若 comp(a, b) 为 true 且 comp(b, c) 为 true则 comp(a, c) 必须为 true。1 小于 22 小于 3那么 1 必须小于 3。这条规则保证排序结果不会出现环路比如 a 排在 b 前、b 排在 c 前、c 又排在 a 前。规则四等价的传递性先定义什么叫等价comp(a, b) 为 false 且 comp(b, a) 为 false也就是 a 不小于 b、b 也不小于 a此时称 a 与 b 等价意思是排序意义上分不出先后。这条规则要求等价关系本身也满足传递性a 与 b 等价b 与 c 等价那么 a 与 c 必须等价。为什么需要这条因为排序算法会把等价的元素视为可互换。如果等价不传递可能出现 a 和 b 等价、b 和 c 等价、但 a 和 c 却分出了先后排序结果自相矛盾。四条规则对照表规则数学表述通俗含义是否满足非自反性comp(a, a) 恒为 false元素不小于自己不满足comp(a,a) 恒为 true反对称性comp(a, b) 为 true 时 comp(b, a) 必为 false大小方向互斥不满足相等时双向都 true传递性comp(a,b) 且 comp(b,c) 为 true 时 comp(a,c) 为 true小于可接力满足等价传递性等价关系必须传递分不出先后也要一致满足五、弱字的含义允许等价类存在严格弱序允许出现等价类一批元素两两等价排序时它们可以任意挨在一起谁前谁后都合法。举例。按身高给一群人排队三个身高都是 170 厘米的人两两之间都是甲不低于乙、乙不低于甲他们构成一个等价类。排序只保证这个等价类整体排在 165 的人后面、175 的人前面等价类内部谁先谁后排序不承诺你也不关心。这就是弱字的由来它比全序弱。全序要求任意两个元素必须分出大小比如实数上的小于严格弱序不要求分出大小只要求给出明确答复而等价本身就是一种明确答复。标准库很多组件都依赖等价类概念。std::set 和 std::map 用等价判断两个键是否重复std::lower_bound 和 std::upper_bound 用不小于定位边界。所以比较器不仅影响排序还影响整个标准库对元素的统一理解。六、排序算法为什么依赖这套规则std::sort 的主流实现libstdc、MSVC 等采用内省排序 introsort本质是快速排序数据接近有序时退化为堆排序兜底。快速排序的核心操作是分区选一个枢轴把比它小的放左边比它大的放右边。这个操作依赖一个前提任意两个元素在比较器下的关系必须互斥且确定。违反非自反性时元素与自身比较返回 true。分区过程可能永远无法收敛最典型的后果是死循环。违反反对称性时同一个元素可能被同时归入左右两个分区导致元素丢失、重复、错序甚至让算法内部迭代器越过容器边界。违反传递性时排序结果可能出现逻辑上不可能的环路。还有一个容易忽略的细节introsort 在选取枢轴时会做三数取中也就是比较区间首、中、尾三个元素。这三个比较同样依赖比较器的一致性一旦比较器自相矛盾取中逻辑也跟着错。某流处理模块的元数据排序函数// 修复前BUGautometaDataSortFunc[](constautopair1,constautopair2){returnpair1.secondpair2.second;};// 修复后autometaDataSortFunc[](constautopair1,constautopair2){returnpair1.secondpair2.second;};一行之差。但修复前一旦存在两条元数据时间戳相同整个排序就是未定义行为修复后时间戳相同的元素被视为等价排序结果确定且稳定。如果业务需要以 first 作为次级排序键应当显式写出 tie-breaker而不是依赖的相等分支autometaDataSortFunc[](constautopair1,constautopair2){if(pair1.second!pair2.second)returnpair1.secondpair2.second;returnpair1.firstpair2.first;};这样写等价类的定义完全明确second 相同再比 firstfirst 也相同才真正等价。七、正确写法准则一只写严格比较比较器里只允许出现或禁止和。这是最容易执行的一条纪律。准则二按 const 引用接收参数上面的 lambda 按值接收 pair每次比较产生两次拷贝大数据量排序开销可观autobadCmp[](std::pairstd::string,inta,std::pairstd::string,intb){returna.secondb.second;// 功能正确但每次比较拷贝两次};autogoodCmp[](conststd::pairstd::string,inta,conststd::pairstd::string,intb){returna.secondb.second;// 零拷贝};准则三复合排序键显式写 tie-breaker按多个字段排序时逐层比较遇到相等的字段再比下一个autocmp[](constRecorda,constRecordb){if(a.score!b.score)returna.scoreb.score;// 主键if(a.name!b.name)returna.nameb.name;// 次级键returna.idb.id;// 末级键};准则四自定义类型重载 operator为自定义类型实现排序时优先重载 operator并保证它与 std::less 的语义一致。operator 只需要满足严格弱序不需要实现其他比较运算符标准库会自动组合出等价判断。准则五浮点比较要格外小心NaN 与任何值比较都返回 false包括与自身。如果数据里可能出现 NaN浮点比较器会违反严格弱序。处理方式是先过滤或特殊标记 NaN再参与排序。准则六不要用减法返回真值初学者常写 return a - b 期望得到负数但比较器要求返回 boola - b 会被隐式转换为 bool任何非零值都变成 true。这是另一类经典错误与严格弱序无关但同属比较器误用。参考https://en.cppreference.com/cpp/named_req/Compare缩写 全称 含义 UB Undefined Behavior 未定义行为后果无任何保证 IMPL-DEF Implementation-Defined Behavior 实现定义行为后果由具体编译器决定但必须文档化如 sizeof(int)US Unspecified Behavior 未指定行为后果未规定但程序仍有效如表达式求值顺序 IF-NDR Ill-formed, No Diagnostic Required 病态程序且无需诊断程序无效但编译器可不报错如违反单一定义规则