红火恍惚cxy @ 2023-07-11 17:00:10
我在写 KDT 用 nth_element 进行排序时，定义了 cmp 函数，却因为将
具体来说，我把
inline bool cmpx(qwq x,qwq y){
return x.x<y.x;
}写成了
inline bool cmpx(qwq x,qwq y){
return x.x<=y.x;
}这导致了排序出现错误。
使用 nth_element 时如下：
nth_element(trr.begin()+l,trr.begin()+mid,trr.begin()+r+1,(((dep&1)==1)?cmpx:cmpy));如果需要的话，完整代码
请问各位大佬这是什么原因导致的？
我一直不太清楚 cmp 函数在 STL 中的实现是什么样的，所以如果可以的话想麻烦各位大佬解释一下 qwq。
我已经不止一次栽到这个地方了……
by Accelessar @ 2023-07-11 17:01:47
就是说，不允许出现 cmp(x,y)=cmp(y,x) 的情况。
by liangbowen @ 2023-07-11 17:04:05
好像是算 UB 的吧，重载之类的东西必须保证 x<y 和 x>y 一真一假。
by WsW_ @ 2023-07-11 17:04:52
@红火恍惚cxy 我来给你猜测一下叭
显然
但是没有定义等于号，怎样判定呢？
如果
但是按你这样定义，两者都成立，就会炸qwq
by WsW_ @ 2023-07-11 17:05:34
@WsW_ sort也是这样，之前打 CF 炸过 QAQ
by Accelessar @ 2023-07-11 17:05:41
link
by Tibrella @ 2023-07-11 17:10:23
@红火恍惚cxy 不稳定排序特性
by 红火恍惚cxy @ 2023-07-11 17:10:57
@WsW_ @AZN_0975 @liangbowen 谢了 orz
我考虑过类似的情况，但是一直找不到比较官方可靠的解释。
谢谢 @AZN_0975 给的链接，我真忘了可以去官方文档里找这个（。
谢谢 @WsW_ @liangbowen 的例子，我之前没有考虑过这个相等的问题。
by 红火恍惚cxy @ 2023-07-11 17:12:25
@Tibrella 懂了，感谢！
by Tibrella @ 2023-07-11 17:13:19
@liangbowen stable_sort 可以不严格弱徐
by ud2_ @ 2023-07-11 17:32:04
@Tibrella [alg.sorting.general] 是这样写的，“对于除 [alg.binary.search] 外描述的算法，comp 应当在值上引入严格弱序”。stable_sort 在 [alg.sort] 而非 [alg.binary.search]。