3

每当我尝试对导致无限循环的对象向量进行排序时,我都会遇到一个问题。我正在使用我传递给排序函数的自定义比较函数。

当两个对象相等而不是 true 时,我可以通过返回 false 来解决此问题,但我并不完全理解解决方案。我认为这是因为我的比较功能违反了 cplusplus.com 上概述的这条规则:

比较函数对象,它采用与范围中包含的相同类型的两个值,如果第一个参数在其定义的特定严格弱排序中位于第二个参数之前,则返回 true,否则返回 false。

谁能提供更详细的解释?

4

6 回答 6

6

正如其他人指出的那样,正确的答案是了解什么是“严格的弱排序”。特别是,如果comp(x,y)为真,则comp(y,x)必须为假。(请注意,这意味着这comp(x,x)是错误的。)

这就是您纠正问题所需要知道的一切。如果您的比较函数违反规则,该sort算法根本不会做出任何承诺。

如果您好奇到底出了什么问题,您的库的sort例程可能在内部使用了快速排序。快速排序通过在序列中重复查找一对“乱序”元素并交换它们来工作。如果您的比较告诉算法 a,b 是“乱序的”,并且它还告诉算法 b,a 是“乱序的”,那么算法最终可以永远地来回交换它们。

于 2011-06-02T18:29:07.073 回答
6

如果您正在寻找“严格弱排序”的详细解释,这里有一些很好的阅读材料:我说的命令!

如果您正在寻求修复比较函子的帮助,则需要实际发布它。

于 2011-06-02T18:22:11.160 回答
6

如果项目相同,则一个不会先于另一个。文档非常清楚地说明您应该false在这种情况下返回。

于 2011-06-02T18:22:32.623 回答
3

实际规则在 C++ 标准中指定,在25.3[lib.alg.sorting]/2

Compare用作函数对象,true如果第一个参数小于第二个参数,则返回,false否则返回。

参数相等的情况属于“否则”。

于 2011-06-02T18:25:13.230 回答
2

排序算法很容易循环,因为您说 A < B AND B < A 当它们相等时。因此,该算法可能会无限尝试交换元素 A 和 B,试图让它们以正确的顺序排列。

于 2011-06-02T18:23:58.973 回答
0

严格的弱排序意味着 a < b == true 并且当您为相等返回 true 时,它​​的 a <= b == true。不同排序算法的最优性需要此要求。

于 2011-06-02T18:22:17.693 回答