c ++ std :: vector std :: sort infinite loop [英] c++ std::vector std::sort infinite loop

问题描述

每当我试图排序一个对象的向量，导致一个无限循环，我遇到了一个问题。我使用我传递到排序函数的自定义比较函数。

I ran across an issue whenever I was trying to sort a vector of objects that was resulting in an infinite loop. I am using a custom compare function that I passed in to the sort function.

我能够解决这个问题，当两个对象相等而不是真，但我不完全理解的解决方案时返回false。我认为这是因为我的比较函数违反了cplusplus.com上概述的这条规则：

I was able to fix the issue by returning false when two objects were equal instead of true but I don't fully understand the solution. I think it's because my compare function was violating this rule as outlined on cplusplus.com:

比较函数对象，
如果第一个参数
在
中的第二个参数之前，那么
将返回true特定的严格弱序列
b定义，否则为false。

Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

任何人都可以提供更详细的解释？

Can anyone provide a more detailed explanation?

推荐答案

正如其他人所指出的，正确的答案是学习一个严格的弱排序。特别是，如果 comp（x，y）为真，则 comp（y，x）必须为false 。 （注意，这意味着 comp（x，x）是false。）

The correct answer, as others have pointed out, is to learn what a "strict weak ordering" is. In particular, if comp(x,y) is true, then comp(y,x) has to be false. (Note that this implies that comp(x,x) is false.)

知道纠正你的问题。如果你的比较函数违反规则， sort 算法根本没有承诺。

That is all you need to know to correct your problem. The sort algorithm makes no promises at all if your comparison function breaks the rules.

错误，您的库的 sort 例程可能在内部使用quicksort。快速排序通过重复查找序列中的一对无序元素并交换它们来工作。如果你的比较告诉算法a，b是乱序的，并且它也告诉算法b，a是无序的，那么算法可以卷起来永远交换他们来回。

If you are curious what actually went wrong, your library's sort routine probably uses quicksort internally. Quicksort works by repeatedly finding a pair of "out of order" elements in the sequence and swapping them. If your comparison tells the algorithm that a,b is "out of order", and it also tells the algorithm that b,a is "out of order", then the algorithm can wind up swapping them back and forth over and over forever.

这篇关于c ++ std :: vector std :: sort infinite loop的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！