Блог

Рассмотрим упорядоченные и неупорядоченные ассоциативные контейнеры в 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.

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

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

Для (упорядоченных) ассоциативных контейнеров определение строгого слабого порядка (25.4 / 4) гласит:

Если мы определяем equiv(a, b) как !comp(a, b) amp;amp; !comp(b, a) , то требования таковы, что comp и equiv оба являются транзитивными отношениями … equiv(a, b) amp;amp; 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) равно false, поэтому equal_to<double>() не является отношением эквивалентности.

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

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

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

Несколько быстрых экспериментов в 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
  

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

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

NaN s могут храниться внутри map — а именно, они могут быть скопированы и менее сопоставимы. std::less for doubles не соответствует требованиям map к строгому слабому упорядочению, поэтому технически у вас здесь неопределенное поведение. Однако поведение легко объясняется, даже если это не требуется стандартом. Map использует эквивалентность, а не равенство, чтобы определить, является ли элемент дубликатом. Сравнение двух NAN эквивалентно, но не равно. Однако в некоторых случаях это не работает. Например, если вы попытаетесь вставить что-то, отличное от NaN, в эту карту, это будет рассматриваться как эквивалентное NaN, и вы не получите insert. Попробуйте добавить несколько действительных чисел в дополнение к NAN, и вы увидите, что карта тоже разбивается.

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