c++ - c++ std::vector std::sort 无限循环

Question

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

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

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

谁能提供更详细的解释？

score 6 · Accepted Answer

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

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

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

score 6 · Accepted Answer

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

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

score 6 · Accepted Answer

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

score 3 · Accepted Answer

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

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

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

score 2 · Accepted Answer

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

score 0 · Accepted Answer

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

6 回答 6