Является ли 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;
}

Дляупорядоченная карта, я получаю:

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

Для неупорядоченной карты я получаю:

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

Так что в упорядоченной карте все NaN обрабатываются одинаково, что я иожидать, хотя казалось, что NaN будет нарушать требования.Однако для неупорядоченной карты я больше никогда не смогу получить элемент, и все NaN различны.Это также не то, что я ожидаю.

Должен ли стандарт что-либо говорить по этому вопросу?

Обновление: Благодаря замечательным ответам ниже, обратите внимание, чтоstd::map сломается, если вы вставите в него что-нибудь еще , как только в нем появится NaN.

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

Answer 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>() не является отношением эквивалентности.

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

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

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

Несколько быстрых экспериментов в Python (где set и dict являются неупорядоченными ассоциативными контейнерами, которые содержат ключи и значения по ссылке) предполагают, что NaN обрабатываются как объекты, которые имеют неравные значения, даже если они "одинаковы" 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

Answer 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), я бы сказал, что все ограничения соблюдены.

Answer 3

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

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