Является ли NaN допустимым значением ключа для ассоциативных контейнеров?

Ответ 1

Они оба запрещены стандартом.

Для (упорядоченных) ассоциативных контейнеров определение строгого слабого порядка (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>() не является отношением эквивалентности.

Кстати, манипулирование контейнерами на двойнике немного пугает так же, что сравнение двойников для равенства всегда немного страшно. Вы никогда не знаете, что получите в младшем значении.

Что-то, что я всегда считал немного странным, заключается в том, что стандарт выражает требования в терминах типа ключа, а не в терминах фактических значений ключа, добавленных в контейнер. Я считаю, что вы могли бы прочитать это как не гарантирующее, что map<double, int> вообще определит поведение, если реализация поддерживает NaN, независимо от того, действительно ли вы добавляете NaN к экземпляру или нет. На практике, однако, реализация std::map не может каким-либо образом вызывать NaN из своего заднего кармана и попытаться сравнить его, он только когда-либо сравнивает значения ключа, переданные экземпляру. Так что это должно быть хорошо (если немного страшно), если вы избегаете добавления NaN.

Я был бы очень благодарен за комментарии о том, как справляются другие языки ключи с плавающей запятой в ассоциативных контейнерах

Несколько быстрых экспериментов на Python (где set и dict являются неупорядоченными ассоциативными контейнерами, в которых хранятся ключи и значения по ссылке) показывают, что NaN рассматриваются как объекты, которые не равны по стоимости, даже если они "одинаковы" NaN ", но тот же наном объект снова можно найти по идентичности. Насколько я видел, контейнеры, похоже, не беспокоят, если содержать несколько nans или смесь nans и других значений:

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

Ответ 2

Это потому, что

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 эквивалентность есть, когда !less(a,b) && !less(b,a), я бы сказал, что все ограничения выполнены.

Ответ 3

NaN могут храниться внутри карты, а именно: они копируются и менее сопоставимы. std::less для двойников не соответствует требованиям к карте для строгого слабого упорядочения, поэтому вы технически получили undefined поведение здесь. Однако поведение легко объясняется, даже если это не требуется стандартом. Для определения того, является ли элемент дубликат, для карты используется эквивалентность, а не равенство. Два NaN сравнивают эквивалент, но не равны. Однако в некоторых случаях это разваливается. Например, если вы попытались вставить что-то, отличное от NaN, в эту карту, оно будет рассматриваться как эквивалентное NaN, и вы не получите никакой вставки. Попробуйте добавить некоторые реальные числа в дополнение к NaN, и вы также можете увидеть разрывы карт.

Ожидается, что поведение хэша ожидается, но не определено для хеш-таблицы. Хэш-таблицы требуют, чтобы их содержимое копировалось конструктивно и сопоставимо равенство. Хэши нескольких NaN сравниваются равными, поэтому все они собираются войти в одно и то же ведро, но хеш-таблица использует сравнение равенства, а не сравнение (равенство, а не эквивалентность). Поэтому ни одно из NaNs не сравнится друг с другом, и вы получаете несколько вложений для этого ключа. Это связано с тем, что NaN нарушает сопоставимое требование равенства хэш-таблицы, а именно, инвариант, что std:: equal_to (x, x) true.