c++ - NaN 是关联容器的有效键值吗？

Question

考虑 C++ 中以 double 为键的有序和无序关联容器。

NaN 是有效的键类型吗？

对于有序容器，我应该说“不”，因为它不尊重严格的弱排序。

对于无序容器，我不知道。

以下是 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;
}

对于有序 map ，我得到:

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

对于无序 map ，我得到:

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

所以在有序映射中，所有 NaN 都被同等对待，这是我所期望的，尽管 NaN 似乎会违反要求。然而，对于无序映射，我永远无法再次检索元素，并且所有 NaN 都是不同的。这也不是我所期望的。

标准对这个问题有什么要说的吗？

更新:感谢下面的出色答案，请注意，如果您将 anything else 插入其中一次，std::map 将会中断里面有一个 NaN。

(对于其他语言如何处理关联容器中的浮点键的评论，我将不胜感激。)

Answer 1

它们都被标准禁止。

对于(有序的)关联容器，严格弱序的定义(25.4/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 ... equiv(a, b) && equiv(b, c) implies equiv(a, c)

这对于 a = 0.0、b = NaN、c = 1.0、comp = std::less<double>() 会失败

对于无序容器，23.2.5/3 表示相等谓词 Pred “在 Key 类型的值上引入等价关系”。等价关系是自反的，std::equal_to<double>()(NaN,NaN)是假的，所以 equal_to<double>()不是等价关系。

顺便说一句，在 double 上键入容器有点可怕，就像比较 double 是否相等总是有点可怕一样。你永远不知道你会在最不重要的位中得到什么。

我一直认为有点奇怪的是，该标准根据键 type 来表达要求，而不是根据添加到容器中的实际键值来表达要求。我相信您可以选择阅读本文，因为不保证 map<double, int>如果实现支持 NaN，则完全定义了行为，无论您是否实际将 NaN 添加到实例。但在实践中，std::map 的实现无法以某种方式变出 NaN从它的后兜里拿出来并尝试比较它，它只比较传递给实例的键值。因此，如果您避免添加 NaN，应该没问题(如果有点吓人的话)。

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

在 Python 中的一些快速实验(其中 set 和 dict 是通过引用保存键和值的无序关联容器)表明 NaN 被视为值不相等的对象，即使它们“相同” NaN”，但同样的 nan object 可以通过身份再次找到。据我所见，容器似乎不会因包含多个 nan 或 nan 和其他值的混合而受到干扰:

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