std::sort底层比较器与严格弱序的陷阱
什么是严格弱序(Strict Weak Ordering)？为什么std::sort要求比较器必须满足严格弱序？违反会导致什么后果？常见的<=比较为什么是错误的？
回答
屠龙少年
严格弱序是数学上的偏序关系，要求：①反自反性：comp(a,a)必须为false；②非对称性：若comp(a,b)为true则comp(b,a)为false；③传递性：若comp(a,b)且comp(b,c)则comp(a,c)；④等价可传递：若!comp(a,b)&&!comp(b,a)(等价)且!comp(b,c)&&!comp(c,b)则!comp(a,c)&&!comp(c,a)。为什么用<=是错的：a <= a返回true→违反反自反性，导致排序算法产生未定义行为(可能崩溃、无限循环或错误排序)。常见错误：①比较器内修改比较对象；②浮点数NaN的比较(NaN与任何值比较都返回false)；③指针比较不考虑同一个容器的不同子对象。正确做法：用<(less)，等价于!(a<b) && !(b<a)。C++20的<=>三路比较自动生成严格弱序。