Is NaN a valid key value for associative containers?

Question

Consider the ordered and unordered associative containers in C++ keyed on double.

Is NaN a valid key type?

With ordered containers, I should say "no", because it does not respect the strict weak ordering.

With unordered containers, I have no idea.

Here's what happens in GCC 4.6.2:

#include <map> #include <unordered_map>  #include <cmath>  #include <iostream> #include <prettyprint.hpp>  int main() {   typedef std::map<double, int> map_type; // replace by "unorderd_map"    map_type dm;   double d = std::acos(5); // a good nan    dm[d] = 2;   dm[d] = 5;   dm[d] = 7;    std::cout << "dm[NaN] = " << dm[d] << ", dm = " << dm << std::endl; } 

For the ordered map, I get:

dm[NaN] = 7, dm = [(nan, 7)] 

For the unordered map, I get:

dm[NaN] = 0, dm = [(nan, 0), (nan, 7), (nan, 5), (nan, 2)] 

So in the ordered map, all NaNs are treated the same, which is what I expect, although it seemed like NaN would violate the requirements. For the unordered map, however, I can never retrieve an element again, and all NaNs are different. This is also not what I would expect.

Does the standard have to say anything on this matter?

Update: Thanks to the great answers below, note that the std::map will break if you insert anything else into it once a NaN is in it.

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

Answer 1

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 

Answer 2

This is because

std::less<double>(NaN, NaN) == false 

Like you said, the weak total ordering (required for std::map<>) is ok, the equality (or equivalence, extra requirement for any hash-based container) isn't ok to satisfy the key requirements for the hash (unordered) map

Irreflexivity   f(x, x) must be false.   Antisymmetry   f(x, y) implies !f(y, x)   Transitivity   f(x, y) and f(y, z) imply f(x, z).   Transitivity of equivalence                Equivalence (as defined above) is transitive: if x           is equivalent to y and y is equivalent to z, then x is           equivalent to z. (This     implies that equivalence does           in fact satisfy the mathematical definition of an equivalence           relation.) 

Seeing that for std::map, equivalence is when !less(a,b) && !less(b,a), I'd say all constraints are met.