27

考虑 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;
}

对于有序地图，我得到：

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

对于无序地图，我得到：

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

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

标准是否必须在这件事上说什么？

更新：感谢下面的出色答案，请注意，std::map如果您在其中插入任何其他内容，则会中断NaN 。

（我将非常感谢有关其他语言如何处理关联容器中的浮点键的评论。）

4

3 回答 3

18

它们都被标准禁止。

对于（有序）关联容器，严格弱序（25.4/4）的定义说：

如果我们定义equiv(a, b)为!comp(a, b) && !comp(b, a)，那么要求是comp并且equiv都是传递关系 equiv(a, b) && equiv(b, c)...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 是否相等总是有点可怕一样。你永远不知道你会在最不重要的位中得到什么。

我一直认为有点奇怪的是，该标准根据键类型表达了要求，而不是根据添加到容器中的实际键值。我相信如果实现支持 NaN，您可以选择将其解读为根本不保证map<double, int>已定义行为，无论您是否实际将 NaN 添加到实例中。然而，在实践中，一个实现std::map不能以某种方式NaN从它的后袋中变出一个并尝试比较它，它只比较传递给实例的键值。因此，只要您避免添加 NaN，它应该没问题（如果有点吓人）。

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

Python 中的一些快速实验（其中set和dict是通过引用保存键和值的无序关联容器）表明 NaN 被视为值不相等的对象，即使它们是“相同的 NaN”，但相同的 nan对象可以被身份再次发现。据我所见，容器似乎不会因包含多个 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
于 2011-11-11T16:38:34.397 回答
5

这是因为

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

就像你说的，弱总排序（std::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.)

看到 std::map 的等价性是 when !less(a,b) && !less(b,a)，我会说满足所有约束。

于 2011-11-11T16:16:55.853 回答
3

NaNs 可以存储在地图中——也就是说，它们是可复制的，并且不可比较。std::lessfor doubles 不符合 map 对严格弱排序的要求，因此从技术上讲，您在这里遇到了未定义的行为。但是，即使标准没有要求，这种行为也很容易解释。Map 使用等价而不是相等来确定一个项目是否是重复的。两个 NaN 比较相等，但不相等。但是，这在某些情况下会分崩离析。例如，如果您尝试在该映射中插入除NaN 之外的其他内容，则它将被视为等同于 NaN，并且您不会得到任何插入。尝试在 NaN 之外添加一些实数，您也会看到地图出现故障。

散列行为是预期的，但也没有为散列表定义——散列表要求它们的内容是可复制构造的并且相等性可比较。多个 NaN 的哈希比较相等，因此它们都将进入同一个存储桶，但哈希表使用相等比较而不是小于比较（相等而不是等价）。因此，没有一个 NaN 比较彼此相等，并且您会为该键获得多个插入。这是因为 NaN 打破了哈希表的等式可比要求——即 std::equal_to(x, x) 为真的不变量。

于 2011-11-11T16:21:24.257 回答