Alex Rivera | Logout

Are IEEE floats valid key types for std::map and std::set?

Asked 2011-01-27T12:14:54.093
24

Background

The requirement for a comparator on the key type of an associative container (for example std::map) is that it imposes a strict weak order on the elements of the key type.

For a given comparator comp(x, y) we define equiv(x, y) = !comp(x, y) && !comp(y, x).
The requirements for comp(x, y) being a strict weak order are

  1. Irreflexibility (!comp(x, x) for all x)
  2. Transitivity of the ordering (if comp(a, b) and comp(b, c) then comp(a, c)).
  3. Transitivity of equivalence (if equiv(a, b) and equiv(b, c) then equiv(a, c))

std::less<float> (the default comparator) uses operator<, which does not create a strict weak order because of NaN. Because x < NaN and NaN < x are false for all x, NaN is equivalent to all floats under this comparator, this breaks condition #3: equiv(1.0, NaN) and equiv(NaN, 2.0) but not equiv(1.0, 2.0). For IEEE floats except NaN, it is a strict weak order (where each number has its own equivalence class except for 0 and -0).

The question

Does this mean that one is not allowed by the C++ standard to use IEEE floats (and (long) doubles) as a key type in an associative container because of the above issue, even if I make sure that NaN never gets inserted into the container? I'm not quite sure about the "elements of Key" wording in the standard—if it means all possible elements or just the elements that end up in the container.

Note: The question is not about issues wrt. truncation/rounding, I'll likely post a different question regarding that soon.

Update:

Sigh. I should've posed the question witho

Edit
Report

1 Answer

2

In short: this is fine (in the sense that your question is about).

If you prevent the values (i.e. NaN) that wouldn't satisfy the ordering requirements, then the behaviour is entirely defined.

answered 2011-01-27T12:17:47.963

Your Answer