在 C++ 中的 STL 比较函数中使用“<=”符号而不是“<”符号有什么区别？

Question

我必须在 sort() 函数中实现第三个参数 cmp，用于对 整数数组 降序排序 .

问题是这个定义不能正常工作，

bool cmp (int a, int b)
{
    if(a<b)
        return false;
    else
        return true;
}

但是，这

bool cmp (int a, int b)
{
    if(a<=b)
        return false;
    else
        return true;
}

在 main() 函数中，我使用

sort(Arr,Arr+n,cmp);

请注意，我声称第一个代码无法正常工作，因为我对 Codechef 上的问题的解决方案在我使用第二个时被接受，但在第一个中不被接受。

Answer 1

如果两个值相等，STL 比较函数必须 return 为假。

Answer 2

提供给 std::sort 的比较函数必须 return 如果其第一个参数按要求的顺序位于第二个参数之前则为真，否则为假。

因此，对于 descending 排序，您应该使用 > 运算符>，对于 ints returns 什么的补充<= 运算符 returns（您用来实现比较的）。最好使用 std::greater<int> 来避免此类陷阱。

Answer 3

在sort、

最后一个参数：

comp - comparison function object (i.e. an object that satisfies the requirements of Compare) ....

Compare

comp(a, b)

Establishes strict weak ordering relation with the following properties:

For all a, comp(a,a)==false

....

这就是为什么

if(a<=b) 
    return false;

有效，而

if(a<b)
    return false;

没有。

Answer 4

std::sort 的比较函数 returns 一个值，指示作为第一个参数传递的元素是否被认为在特定 严格弱排序 它定义了。

这里是来自sgi

的严格弱排序的定义

A Strict Weak Ordering is a binary predicate that compares two objects, returning true if the first precedes the second. This predicate must satisfy the standard mathematical definition of a strict weak ordering. The precise requirements are stated below, but what they roughly mean is that a Strict Weak Ordering has to behave the way that "less than" behaves:

if a is less than b then b is not less than a,

if a is less than b and b is less than c then a is less than c, and so on.

Answer 5

根据 documentation 的比较函数：

Establishes strict weak ordering relation

所以，函数comp必须定义严格的弱排序。根据定义，它必须满足三个条件：

1) comp(x, x) 对所有 x 都是假的（非自反性条件）

2) If comp(x, y) then !comp(x, y) (不对称条件)

3) If comp(x, y) and comp(y, z) then comp(x, z) (transitivity condition)

很容易看出cmp函数的第一个例子不满足自反性条件，因此不能作为std::sort的comp参数传递。同样清楚的是，在 x, y 的情况下，第二个 cmp 示例是满足所有三个条件的数字，因此它可以作为 comp 参数传递给 std::sort.

在 C++ 中的 STL 比较函数中使用“<=”符号而不是“<”符号有什么区别？

What is the difference between using a "<=" sign instead of a "<" sign in the compare function of an STL in C++?

c++

stl