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 が異なります。これも私が期待するものではありません。

規格はこの問題について何か言う必要がありますか?

更新:以下の優れた回答のおかげで、 NaN が含まれているときに何か他std::mapのものを挿入すると壊れることに注意してください。

(他の言語が連想コンテナー内の浮動小数点キーをどのように処理するかについて、コメントをいただければ幸いです。)

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 が等しいかどうかを比較するのが常に少し怖いのと同じように、少し怖いです。最下位ビットで何が得られるかは決してわかりません。

私が常に少し奇妙だと思っていたのは、標準では、コンテナに追加された実際のキー値ではなく、キータイプの観点から要件が表現されていることです。map<double, int>実際に NaN をインスタンスに追加するかどうかに関係なく、実装が NaN をサポートしている場合、動作がまったく定義されていることを保証しないものとして、これを読むことを選択できると思います。ただし、実際には、 の実装はstd::map何らかの形NaNでバックポケットから を呼び出してそれを比較しようとすることはできず、インスタンスに渡されたキー値のみを比較します。したがって、NaN を追加しないようにすれば、(少し怖い場合でも) 問題ありません。

他の言語が連想コンテナー内の浮動小数点キーをどのように処理するかについてコメントをいただければ幸いです。

Python でのいくつかの簡単な実験 (setとdictは参照によってキーと値を保持する順序付けられていない連想コンテナーです) は、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 は、アイテムが重複しているかどうかを判断するために、等価ではなく等価を使用します。2 つの NaN を比較すると同等ですが、等しくありません。ただし、場合によってはそれが崩れます。たとえば、そのマップに NaN以外のものを挿入しようとすると、NaN と同等のものとして扱われ、挿入されません。NaN に加えていくつかの実数を追加してみてください。マップが壊れていることもわかります。

ハッシュの動作は想定されていますが、ハッシュ テーブルについても定義されていません。ハッシュ テーブルでは、その内容がコピーで構成可能であり、等価性が比較可能である必要があります。複数の NaN のハッシュは比較すると等しいため、すべて同じバケットに入れられますが、ハッシュ テーブルでは比較未満ではなく等値比較 (同等ではなく等値) が使用されます。したがって、互いに等しい NaN はなく、そのキーに対して複数の挿入が行われます。これは、NaN がハッシュ テーブルの等値比較要件、つまり std::equal_to(x, x) が真であるという不変条件を破るためです。

于 2011-11-11T16:21:24.257 に答える