6

以下课程是否会破坏严格弱排序（与常规相比std::less（因此忽略诸如 Nan 之类的边缘情况值））

struct LessWithEpsilon
{
    static constexpr double epsilon = some_value;
    bool operator() (double lhs, double rhs) const
    {
        return lhs + epsilon < rhs;
    }
};

LessWithEpsilon lessEps{};
4

2 回答 2

7

来自https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings

  1. 不可比性的传递性：对于所有x, y, zin S, ifx与都不可比y（即既不是x < y也不y < x是true）如果y与 不可比z，则x与 不可比z。

同样，来自https://en.cppreference.com/w/cpp/named_req/Compare

如果equiv(a, b) == true and equiv(b, c) == true，那么equiv(a, c) == true

随着{x, y, z} = {0, epsilon, 2 * epsilon}，该规则被打破：

  • !lessEps(x, y) && !lessEps(y, x) && !lessEps(y, z) && !lessEps(z, y) 但是lessEps(x, z)。
  • equiv(x, y) == true and equiv(y, z) == true但是equiv(x, z) == false（作为x + epsilon < z）

因此，该类打破了严格-弱排序。

于 2021-06-24T10:30:56.353 回答
4

正如 Jarod42 的回答中所解释的那样，LessWithEpsilon确实没有对所有双打的域施加严格的弱顺序。

但是，在某些情况下，输入的值域有限，LessWithEpsilon可以对其施加严格的弱顺序。特别是，如果输入由一组不相交的范围组成，其中每个范围的值彼此相等（在 epsilon 内）并且不等于所有其他范围（范围之间的距离大于 epsilon）。

如果您想知道考虑有限输入域是否合理，请考虑 std::less也不会对所有双精度域施加严格的弱顺序 - 必须排除 NaN。

至于编写比较函数时可能的意图，我建议一个可能的替代方案：转换输入，使每个值四舍五入到最接近的 epslon 倍数。从技术上讲，这将使输入对建议的比较函数有效，但也使其变得不必要，因为我们将使用std::less.

于 2021-06-24T10:47:18.587 回答