c++floating-pointepsilonstrict-weak-ordering

Does using epsilon in comparison of floating-point break strict-weak-ordering?


Does following class breaks strict-weak-ordering (in comparison to regular std::less (So ignoring edge case values such as Nan))

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

LessWithEpsilon lessEps{};

Solution

  • From https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings

    1. Transitivity of incomparability: For all x,y,z in S, if x is incomparable with y (meaning that neither x < y nor y < x is true) and if y is incomparable with z, then x is incomparable with z.

    Similarly, from https://en.cppreference.com/w/cpp/named_req/Compare

    If equiv(a, b) == true and equiv(b, c) == true, then equiv(a, c) == true

    With {x, y, z} = {0, epsilon, 2 * epsilon}, that rule is broken:

    So, that class breaks strict-weak-ordering.