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

by

I suspect the restrictions should be taken as referring to the relation’s behavior on the values actually used as keys, not necessarily on all values of the type. Don’t have time at the moment to go through the standard looking for “smoking gun” language that refers to actual container elements rather than all values of the type.

Similar case: what if a comparator (for a container of pointers or smart pointers) calls a virtual function, and somebody links a derived class of the type it compares, which overrides the virtual function in a way that makes the comparator not a strict weak order? Does the program become undefined even if nobody ever actually uses that derived class?

If in doubt, you can support NaN with a comparator that is a strict weak order:

bool operator()(double a, double b) {
    if ((a == a) && (b == b)) {
        return a < b;
    }
    if ((a != a) && (b != b)) return false;
    // We have one NaN and one non-NaN.
    // Let's say NaN is less than everything
    return (a != a)
}

The last two lines “optimize” to return (b == b);, although I’m not sure the comment optimizes with it.

I think Tomalak has convinced me the language does say the whole type needs to be ordered.

This makes little sense, since a map doesn’t conjure values out of nowhere, it only uses values that it’s given (and copies of them), but the question is about the rules, and them’s the rules as far as I know. C++0x is the same. I wonder if there’s a defect report, or any point submitting one.

It’s also annoying in that on (very rare) systems where std::less is slow for pointers, you can’t use < as the comparator in a map of pointers, even if you know that the pointers are all to elements of the same array. Shame.

Another option is to use the following class as the key type, so keys are checked for NaN only on entry to the map, not on every comparison as above.

struct SaneDouble {
    double value;
    SaneDouble (double d) : value(d) {
        if (d != d) throw std::logic_error();
    }
    static friend bool operator<(SaneDouble lhs, SaneDouble rhs) {
        return lhs.value < rhs.value;
    }
    // possibly a conversion to double
};

This raises another question – clearly someone could create a SaneDouble and then set its value to NaN (assuming the implementation lets them get one from somewhere without crashing). So are “elements of SaneDouble” strict-weak-ordered or not? Does my half-hearted attempt to create a class invariant in the constructor make my program undefined even if nobody actually breaks the invariant, simply because they could and therefore the results of doing so are “elements of SaneDouble”? Is it really the intention of the standard that the program’s behavior is defined if and only if value is marked private? Does the standard actually define anywhere what “the elements” of a type are?

I wonder whether we should interpret “elements of Key” to mean that the comparator induces a strict weak order on some elements of Key. Presumably including the ones actually used. “I have doughnuts” doesn’t mean I have every doughnut. It’s a stretch, though.

More Related Contents:

  1. Map C++ Sort and Insert elements by value
  2. How can I use std::maps with user-defined types as key?
  3. Why can’t I compile an unordered_map with a pair as key?
  4. How can I loop through a C++ map of maps?
  5. How to retrieve all keys (or values) from a std::map and put them into a vector?
  6. Deleting elements from std::set while iterating
  7. Const map element access
  8. How to find if a given key exists in a C++ std::map
  9. 32-bit to 16-bit Floating Point Conversion
  10. How to use range-based for() loop with std::map?
  11. How to check if C++ compiler uses IEEE 754 floating point standard
  12. std::map emplace without copying value
  13. Floating point comparison revisited
  14. How can I sort a std::map first by value, then by key?
  15. How can I modify values in a map using range based for loop?
  16. insert vs emplace vs operator[] in c++ map
  17. What is the fastest way to change a key of an element inside std::map
  18. How to change a set element?
  19. How to check that an element is in a std::set?
  20. Translating python dictionary to C++
  21. How to iterate std::set?
  22. converting a variable name to a string in C++
  23. how do you make a heterogeneous boost::map?
  24. Uses for negative zero floating point value?
  25. std::map thread-safety
  26. How can I copy one map into another using std::copy?
  27. Compile-time map and inverse map values
  28. map with incomplete value type
  29. C++ “error: passing ‘const std::map’ as ‘this’ argument of …”
  30. C++ inserting unique_ptr in map

Leave a Comment