如果我为浮点数定义了自定义比较函数,std :: sort会正常工作吗？

Question

对于浮点精度的问题,我为浮点数定义了自定义比较函数:

bool cmp(double a, double b)
{
    if(abs(a - b) <= eps) return false;
    return a < b;
}

然后我在一些浮点数上调用sort.我听说一些不好的比较函数会导致排序错误.我只是想知道它能cmp正常排序吗？一方面,cmp满足了关联规则.但另一方面,cmp(x - eps, x) == false&& cmp(x, x + eps) == false并不意味着cmp(x - eps, x + eps) == false.

我没有直接在浮动数字上使用sort,因为我想要排序的是pair<double, double>.例如:

(1,2), (2,1), (2.000000001, 0)

我想将2和2.000000001视为相同,并期望结果如下:

(1,2), (2.000000001, 0), (2,1)

Answer 1

std::sort需要一个定义严格弱排序的比较器.这意味着,除其他外,必须满足以下条件:

• 我们定义两个项目,a并且b,是相当于(a === b)如果!cmp(a, b) && !cmp(b, a)
• 等价是传递的:a === b&& b === c=>a === c

正如您在问题中已经说过的,您的功能cmp()不符合这些条件,因此您无法使用您的功能std::sort().不仅算法的结果是不可预测的,这是不好的,除非你实际上正在寻找这种不可预测性(参见randomize):如果你有一些彼此非常接近的值,那么它们中的任何一个都true与一些相比,但是false对于其他一些算法,算法可能会进入无限循环.

所以答案是否定的,你不能使用你的函数cmp(),std::sort()除非你想冒风险程序冻结.