6

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{};
Jarod42
  • 203,559
  • 14
  • 181
  • 302
  • even a simple `return lhs < rhs;` breaks strict-weak-ordering when the numbers can be NaN – phuclv Jun 24 '21 at 10:46
  • @phuclv: I wanted to cover that concern by *"in comparison to regular `std::less`"* :-) – Jarod42 Jun 24 '21 at 10:58
  • Related to [floating-point-keys-in-stdmap](https://stackoverflow.com/questions/6684573/floating-point-keys-in-stdmap) – Jarod42 Jan 14 '22 at 11:49

2 Answers2

7

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:

  • !lessEps(x, y) && !lessEps(y, x) && !lessEps(y, z) && !lessEps(z, y) but lessEps(x, z).
  • equiv(x, y) == true and equiv(y, z) == true but equiv(x, z) == false (as x + epsilon < z)

So, that class breaks strict-weak-ordering.

Jarod42
  • 203,559
  • 14
  • 181
  • 302
  • Note that the question specifies `< epsilon`, not `<=`. Trivial fix : `{x,y,z}={0,epsilon/2, epsilon}`. – MSalters Jun 24 '21 at 11:05
  • @MSalters: 0 and epsilon are actually equivalent. class is Less, not Equal. – Jarod42 Jun 24 '21 at 11:07
  • Why asking question if you were able to provide answer in exact same time (less then minute difference)? – Marek R Jun 24 '21 at 11:10
  • @MarekR I believe there is an "answer your own question" checkbox under the question draft that allows you to write an answer before posting the question, so both question and answer get posted at the same time (I've never personally tried it though, so I might be wrong about something). – mediocrevegetable1 Jun 24 '21 at 11:19
  • @mediocrevegetable1 you missed the point. I'm not asking about SO features, but it is strange to ask for help which is not needed, state question when answer is known ahead. Is this some kind of documenting real word question for example from lectures in collage? – Marek R Jun 24 '21 at 11:23
  • 3
    @MarekR: During review, I saw that problem. My coworker asked for reference, and I didn't find direct answer for that, So I create that answer (which I think might help others). – Jarod42 Jun 24 '21 at 12:11
4

It is true that LessWithEpsilon does not impose a strict weak order for the domain of all doubles, as explained in Jarod42's answer.

However, there can be cases where the input has a limited domain of values for which LessWithEpsilon can impose a strict weak order. In particular, if the input consists of set of disjoint ranges where values of each range are equal to each other (within epsilon) and unequal to all other ranges (distance between ranges greater than epsilon).

In case you're wondering whether it is reasonable to consider limited input domains, consider that std::less also doesn't impose a strict weak order for domain of all doubles - NaN must be excluded.

As for what may have been the intention when writing the comparison function, I suggest a possible alternative: Transform the inputs such that each value is rounded to nearest multiple of epslon. This would technically make the input valid for the suggested comparison function, but it also makes it unnecessary because we would get same result using std::less.

eerorika
  • 232,697
  • 12
  • 197
  • 326
  • In which domain `LessWithEpsilon` would be usable? One from which `x + epsilon == x`, (so regular `std::less` is still preferable). – Jarod42 Jun 24 '21 at 10:56
  • @Jarod42 Consider for example set of values 1, 1.5000001, 1.5 and epsilon of 0.1. First would compare less to the last two which compare equal. The elements are in a strictly weak order. – eerorika Jun 24 '21 at 10:59
  • By *"Domain"*, I understood ranges, not subset of points :-) – Jarod42 Jun 24 '21 at 11:03
  • @Jarod42 yeah, it has to be a set of ranges. Each disjoint range has to compare equal within the range, and has to compare unequal to other ranges in order to be orderable by that function. – eerorika Jun 24 '21 at 11:06
  • Are you proposing something like `std::make_tuple(std::is_nan(lhs), std::isfinite(lhs) ? std::fmod(lhs, eps) : lhs) < std::make_tuple(std::is_nan(rhs), std::isfinite(rhs) ? std::fmod(rhs, eps) : rhs)`? – Caleth Jun 24 '21 at 11:59
  • @Caleth I didn't actually have a suggestion of what to use, but I think I will. – eerorika Jun 24 '21 at 12:12
  • @Caleth I've added a proposal for what to use. – eerorika Jun 24 '21 at 12:19