使用“<=" sign instead of a "<" sign in the compare function of an STL in C++? [duplicate]

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 比较函数必须返回 false。

Answer 2

在排序中，

最后一个论点：

comp - 比较函数对象（即满足Compare要求的对象） ....

比较

comp（a，b）

建立严格的弱序关系，具有以下性质：

对于所有 a，comp(a,a)==false

....

所以

if(a<=b) 
    return false;

有效，同时

if(a<b)
    return false;

没有。

Answer 3

std::sort

的比较函数返回一个值，该值指示作为第一个参数传递的元素是否被视为在它定义的特定严格弱排序中位于第二个参数之前。

这是来自sgi

的严格弱排序的定义

严格弱排序是一个比较两个谓词的二元谓词 对象，如果第一个在第二个之前，则返回 true。这 谓词必须满足 a 的标准数学定义 严格的弱排序。具体要求如下所述，但是什么 他们的粗略意思是严格弱排序必须以这种方式表现 “小于”的行为：

• 如果a小于b则b不小于a，
• 如果 a 小于 b 并且 b 小于 c，则 a 小于 c， 等等。

Answer 4

根据比较函数的文档：

建立严格的弱序关系

因此，函数

comp

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

1)

comp(x, x)

对于所有

x

都是假的（无反条件）

2) 如果

comp(x, y)

那么

!comp(x, y)

（不对称条件）

3) 如果

comp(x, y)

和

comp(y, z)

那么

comp(x, z)

（传递性条件）

很容易看出，

cmp

函数的第一个示例不满足非自反性条件，因此它不能用作

comp

的

std::sort

参数传递。同样清楚的是，在

cmp

情况下的第二个

x, y

示例是数字满足所有三个条件，因此它可以作为

comp

参数传递给 std::sort。

Answer 5

如果第一个参数按要求的顺序位于第二个参数之前，则提供给

std::sort

的比较函数必须返回 true，否则返回 false。

因此，对于 降序 排序，您应该使用

>

运算符>，对于

int

s，它返回

<=

运算符返回的补集（您用来实现比较）。最好使用

std::greater<int>

来避免此类陷阱。