c++ - 如果我为 float 定义自定义比较函数，std::sort 是否会正常工作？

Question

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

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

然后我对一些 float 数组调用排序。我听说一些错误的比较函数会导致排序错误。我只是想知道 cmp正确工作排序？一方面，cmp满足关联规则。但另一方面，cmp(x - eps, x) == false && cmp(x, x + eps) == false并不意味着 cmp(x - eps, x + eps) == false .

我没有直接对 float 使用排序，因为我要排序的是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，算法可能会进入无限循环。

所以答案是否定的，你不能在 std::sort() 中使用你的函数 cmp() 除非你想冒程序卡住的风险。