Are Ieee Floats Valid Key Types for Std::Map and Std::Set

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

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.

Floating point keys in std:map

You could implement own compare function.

#include <functional>

class own_double_less : public std::binary_function<double,double,bool>
{
public:
  own_double_less( double arg_ = 1e-7 ) : epsilon(arg_) {}
  bool operator()( const double &left, const double &right  ) const
  {
    // you can choose other way to make decision
    // (The original version is: return left < right;) 
    return (abs(left - right) > epsilon) && (left < right);
  }
  double epsilon;
};
// your map:
map<double,double,own_double_less> mymap;

Updated: see Item 40 in Effective STL!
Updated based on suggestions.

Inhowfar do IEEE754 floats satisfy LessThanComparable?

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.

Is NaN a valid key value for associative containers?

They are both forbidden by the standard.

For the (ordered) associative containers, the definition of strict weak order (25.4/4) says:

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>()

For the unordered containers, 23.2.5/3 says that the equality predicate Pred "induces an equivalence relation on values of type Key". Equivalence relations are reflexive, and std::equal_to<double>()(NaN,NaN) is false, so equal_to<double>() is not an equivalence relation.

By the way, keying containers on a double is slightly scary in the same way that comparing doubles for equality is always slightly scary. You never know what you're going to get in the least significant bit.

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. In practice, though, an implementation of std::map cannot somehow conjure a NaN out of its back pocket and try to compare it, it only ever compares key values passed to the instance. So it should be OK (if slightly scary) provided you avoid adding NaNs.

I'd be very grateful for comments on how other languages handle
floating point keys in associative containers

A few quick experiments in Python (where set and dict are unordered associative containers which hold keys and values by reference) suggest that NaNs are treated as objects that are unequal in value even if they're "the same NaN", but the same nan object can be found again by identity. As far as I've seen, the containers don't seem to be disturbed by containing multiple nans, or a mixture of nans and other values:

>>> thing = set()
>>> nan = float('nan')
>>> nan
nan
>>> thing.add(nan)
>>> thing.add(nan)
>>> thing
set([nan])

>>> thing = dict()
>>> thing[nan] = 1
>>> thing[nan] = 2
>>> thing[nan]
2
>>> nan2 = float('nan')
>>> thing[nan2] = 3
>>> thing
{nan: 2, nan: 3}

>>> thing = set()
>>> thing.add(nan)
>>> thing.add(nan2)
>>> thing
set([nan, nan])

>>> thing = dict()
>>> thing[nan] = 1
>>> thing[nan2] = 2
>>> thing[0] = 3
>>> thing
{nan: 1, nan: 2, 0: 3}
>>> thing.keys()
[nan, nan, 0]
>>> thing.values()
[1, 2, 3]
>>> thing[0]
3
>>> thing[1]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 1

std::map, custom comparator's design constraints

You cannot rely on self consistent equals or not equals because these do not establish a strict weak ordering. The comparator return value should change if you switch the left and right arguments. It is essential for the map to be able to establish an ordering of elements, not just be able to distinguish whether two elements are equal.

It is very important that, is A < B is true, then B < A is false. Furthermore, if A < B and B < C are both true, then A < C is also true.

If you do not want to or cannot establish a strict weak ordering for your types, then, then you could use a map that doesn't require it: std::unordered_map¹, which is a hash map. However, this will require that you provide a hashing function and an equality comparison. It also requires that your compiler have C++11 support.

¹ As @JohnDibling points out in comments, std::unordered_map is unfortunately named. It should have been std::hash_map but apparently that name could have clashed with hash_maps from other libraries. In any case, the intent is not to have a map that is not ordered, but to have one with constant time look-up.

---

Related Topics