5

TL;DR Do the IEEE754 floating point values including NaN satisfy LessThanComparable?

Specifically, question "Why does Release/Debug have a different result for std::min?" got me looking up LessThanComparable:

The type must work with < operator and the result should have standard semantics.

Requirements

The type T satisfies LessThanComparable if

Given

  • a, b, and c, expressions of type T or const T

The following expressions must be valid and have their specified effects

Establishes strict weak ordering relation with the following properties (...)

I double checked it in the standard and it seems it states basically the same there, and I looked at the Wikipedia def of strict weak ordering.

Some think that the set of IEEE floating point vales that includes NaN does not satisfy this concept: Any comparison with NaN on either side will always yield false, but I have been looking at the definitions, and it is not at all apparent to me whether the presence of NaN breaks strict weak ordering:

For the list given at Wikipedia:

  • For all x in S, it is not the case that x < x (irreflexivity).
  • For all x, y in S, if x < y then it is not the case that y < x (asymmetry). see below
  • For all x, y, z in S, if x < y and y < z then x < z (transitivity).
  • For all x, y, z in S, if x is incomparable with y (neither x < y nor y < x hold), and y is incomparable with z, then x is incomparable with z (transitivity of incomparability).

It seems that the strict weak ordering axiom as defined on Wikipedia explicitly calls out possible incomparable values: NaN seems a good candidate here?

On the other hand, the standard says: (25.5/4)

If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations:

(4.1) — comp(a, b) && comp(b, c) implies comp(a, c)

(4.2) — equiv(a, b) && equiv(b, c) implies equiv(a, c)

With these definitions, equiv(x, NaN) is always true (because !comp(a, NaN)==true and !comp(Nan, a)==true: comparison with Nan yields false, negation then yields true)

But clearly (4.2) is not satisfied, e.g:

 equiv(3.0, NaN) && equiv(NaN, 7.0) **does not** imply equiv(3.0, 7.0)

So is what the standard defines not a Strict Weak Ordering, or -- more likely indeed -- am I missing something here?

Community
  • 1
  • 1
Martin Ba
  • 37,187
  • 33
  • 183
  • 337

3 Answers3

8

Strict weak ordering requires that strongly-ordered equivalence classes exist. This is not true of IEEE754.

The problem isn't that there exist multiple NaN values which are equivalent to each other, but that the entire class of NaNs is unordered with respect to the real line.

The violation of (4.2) causes the test in the fourth bullet point you quoted from Wikipedia to also fail (let y be a NaN).

For an example of incomparability that is allowed in a strict weak ordering, consider sign-magnitude integers. Then:

-4 < -3 < -2 < -1 < { -0, +0 } < +1 < +2 < +3 < +4

Neither -0 < +0 nor +0 < -0 is true, so the ordering is weak. But the class formed by these equivalent values is strongly ordered with respect to all others.

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
  • Another way of expressing your first sentence would be to say that if items x and y are unordered with respect to each other, then comparing y with z must yield the same result as comparing x with z. – supercat Dec 23 '16 at 23:35
2

IEEE754 floating point values including NaN do not satisfy LessThanComparable.

If you take the 4th bullet point from Wikipedia and replace uncomparable with equiv you have the same condition as in the std.

Here's a good answer that essentially answers all my C++ish doubts wrt. this:

https://stackoverflow.com/a/8097097/321013

it even quotes the same paragraph from the std as I did at the end in the question above:

If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations ... equiv(a, b) && equiv(b, c) implies equiv(a, c)

This fails for a = 0.0, b = NaN, c = 1.0, comp = std::less<double>()

It also addresses an interesting point wrt. the requirement:

Something I've always considered a little odd is that the standard expresses the requirements in terms of the key type, not in terms of the actual key values added to the container. I believe you could choose to read this as not guaranteeing that map<double, int> has defined behaviour at all if the implementation supports NaNs, regardless of whether you actually add a NaN to an instance or not.

Community
  • 1
  • 1
Martin Ba
  • 37,187
  • 33
  • 183
  • 337
  • With this in mind, is there a standard or a Boost function object that can be used in place of `std::less` or is the recommended solution to roll our own? – Ben Apr 23 '19 at 12:07
1

You appear to be saying that Wikipedia's definition allows NaNs, but the standard's definition does not. I don't think you're right. From Wikipedia's definition:

For all x, y, z in S, if x is incomparable with y (neither x < y nor y < x hold), and y is incomparable with z, then x is incomparable with z (transitivity of incomparability).

Suppose x is 3.0, y is NaN, z is 7.0. x is incomparable with y. y is incomparable with z. x is not incomparable with z.