当参数相等时，为什么std :: sort compare函数必须返回false? [英] Why must std::sort compare function return false when arguments are equal?

问题描述

在std :: sort中，您可以提供第三个参数，这是它对列表进行排序的基础.如果希望第一个参数排在最前面，则返回true.如果希望第二个参数优先出现，则返回false.我遇到了一个问题，即我的谓词函数应该是无效的比较器"，并且将其范围缩小到它不能满足以下要求的事实:

if arg1 == arg2, compare function MUST return false.

我见过一些术语，例如std :: sort需要严格弱排序".除了2个地方之外，我获得的有关这些主题的所有其他页面似乎都是技术论文，我听不懂.我能理解的是:

In weak ordering some elements "may be tied" with each other.

但是对我来说，这也是部分有序集"的含义，即:

"there may be pairs of elements for which neither element precedes the other"

此外，我不明白其中的严格"含义是什么.

撇开我对顺序理论术语的困惑，我的问题是比较函数中的参数1和参数2是否相等，在这种情况下，我不在乎哪个先于另一个(哪个先于我就可以使我开心)，为什么我不能返回true来让参数1首先出现?

我还想问我的程序如何实际上知道它是一个无效的比较器，但后来我认为它可能只是在比较函数返回true时检查arg1和arg2是否相等.

解决方案

compare函数只是对小于"运算符进行建模.考虑<运算符如何处理像int这样的原始类型:

int a = 1, b = 2;     a < b == true      a is less than b
int a = 2, b = 1;     a < b == false     a is not less than b, because a is greater than b
int a = 1, b = 1;     a < b == false     a is not less than b, because a equals b

返回true表示您希望在b之前订购a.因此，如果不是这种情况，请返回false，这是因为您希望在a之前对b进行排序，或者因为它们的顺序无关紧要.

如果在参数相等时返回true，则表示您希望a在b之前，并且希望b在a之前，这是矛盾的./p>

In std::sort you can supply a third argument which is the basis for how it sorts a list. If you want the first argument to come first, then you return true. If you want the second argument to come first you return false. I have come across the problem that my predicate function supposedly is an "invalid comparator", and I have narrowed it down to the fact that it does not fulfil the following requirement:

if arg1 == arg2, compare function MUST return false.

There have been some terms I have seen such as that std::sort requires "strict weak ordering". Apart from 2 places, all the other pages I get about these topics seem to be technical papers, and I can't understand it. What I can understand of it is that:

In weak ordering some elements "may be tied" with each other.

But to me this is also the meaning of a "partially ordered set", which is:

"there may be pairs of elements for which neither element precedes the other"

Furthermore, I can't understand what the "strict" implies in either of them.

Leaving aside my confusion about order theory terminology, my question is if in the compare function argument 1 and argument 2 are equal, and in which case I don't care which comes before the other (either one coming before would make me happy), why can't I return true to have argument 1 come first?

I was also going to ask how my program actually knows it's an invalid comparator but then I thought it probably just checks to see if arg1 and arg2 are equal when the compare function returns true.

解决方案

The compare function simply models a "less than" operator. Consider how the < operator works for primitive types like int:

int a = 1, b = 2;     a < b == true      a is less than b
int a = 2, b = 1;     a < b == false     a is not less than b, because a is greater than b
int a = 1, b = 1;     a < b == false     a is not less than b, because a equals b

Returning true means you want a to be ordered before b. So return false if that is not the case, either because you want b to be ordered before a, or because their order doesn't matter.

If you return true when the arguments are equal, then you are saying that you want a to come before b and you want b to come before a, which is a contradiction.

这篇关于当参数相等时，为什么std :: sort compare函数必须返回false?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！