¿Es NaN un valor clave válido para contenedores asociativos?

Question

¿Es NaN un valor clave válido para contenedores asociativos?

Considere los contenedores asociativos ordenados y desordenados en C++ tecleados en double.

¿Es NaN un tipo de clave válido?

Con los contenedores ordenados, debo decir "no", porque no respeta el estricto pedido débil.

Con contenedores desordenados, no tengo idea.

Esto es lo que sucede en 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;
}

Para el mapa ordenado, obtengo:

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

Para el mapa desordenado, obtengo:

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

Así que en el mapa ordenado, todos los NAN son tratados lo mismo, que es lo que espero, aunque parecía que NaN violaría los requisitos. Para el mapa desordenado, sin embargo, nunca puedo recuperar un elemento de nuevo, y todos los NAN son diferentes. Esto tampoco es lo que esperaría.

¿Tiene la norma que decir algo sobre este asunto?

Actualización: Gracias a las grandes respuestas a continuación, tenga en cuenta que el std::map se romperá si inserta cualquier otra en él una vez que una NaN está en él.

(Estaría muy agradecido por comentarios sobre cómo otros lenguajes manejan claves de coma flotante en contenedores asociativos.)

23

c++map nan unordered-map

Author: Kerrek SB, 2011-11-11

Source

3 answers

Esto es porque

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

Como usted dijo, el orden total débil (requerido para std::map) está bien, la igualdad (o equivalencia , requisito adicional para cualquier contenedor basado en hash) no está bien para satisfacer los requisitos clave para el]}

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

Viendo que para std::map, la equivalencia es cuando !less(a,b) && !less(b,a), diría que se cumplen todas las restricciones.

5

Author: sehe,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-11-11 16:24:19

NaNs se puede almacenar dentro de un mapa namely es decir, son copia construible y menos que comparable. std::less para dobles no cumple con los requisitos del mapa para un orden estricto débil, por lo que técnicamente tienes un comportamiento indefinido aquí. Sin embargo, el comportamiento se explica fácilmente, incluso si no es requerido por el estándar. Map usa equivalencia en lugar de igualdad para determinar si un elemento es un duplicado. Dos NAN comparan equivalente, pero no igual. Sin embargo, eso se desmorona en algunos casos. Para por ejemplo, si intenta insertar algo que no sea un NaN en ese mapa, se trataría como equivalente al NaN y no obtendría ninguna inserción. Trate de añadir algunos números reales, además de las NaNs y se puede ver el mapa se desglosa también.

El comportamiento hash es esperado pero no definido para una tabla hash también require las tablas hash requieren que su contenido sea copy construcable y equality comparable. Los hashes de múltiples NAN comparan iguales, por lo que todos van a entrar en el mismo bucket, pero una tabla hash usa la comparación de igualdad en lugar de menos que la comparación (igualdad en lugar de equivalencia). Por lo tanto, ninguna de las NAN se compara igual entre sí y obtienes múltiples inserciones para esa clave. Esto se debe a que NaN rompe el requisito de igualdad comparable de la tabla hash namely a saber, el invariante que std::equal_to(x, x) true.

3

Author: Billy ONeal,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-11-11 16:41:15

score 16 · Accepted Answer

Ambos están prohibidos por el estándar.

Para los contenedores asociativos (ordenados), la definición de orden débil estricto (25.4/4) dice:

Si definimos equiv(a, b) como !comp(a, b) && !comp(b, a), entonces el los requisitos son que comp y equiv ambos sean relaciones transitivas ... equiv(a, b) && equiv(b, c) implica equiv(a, c)

Esto falla para a = 0.0, b = NaN, c = 1.0, comp = std::less<double>()

Para los contenedores desordenados, 23.2.5 / 3 dice que el predicado de igualdad Pred " induce una relación de equivalencia sobre valores de tipo Key". Las relaciones de equivalencia son reflexivas, y std::equal_to<double>()(NaN,NaN) es falsa, por lo que equal_to<double>() no es una relación de equivalencia.

Por cierto, teclear contenedores en un doble da un poco de miedo de la misma manera que comparar dobles para la igualdad siempre da un poco de miedo. Nunca sabes lo que vas a conseguir en la parte menos significativa.

Algo que siempre he considerado un poco extraño es que el estándar expresa los requisitos en términos de la clave escriba, no en términos de los valores de clave reales añadidos al contenedor. Creo que podría optar por leer esto como si no garantizara que map<double, int> tiene un comportamiento definido en absoluto si la implementación admite NAN, independientemente de si realmente agrega una NAN a una instancia o no. En la práctica, sin embargo, una implementación de std::map no puede de alguna manera conjurar un NaN de su bolsillo trasero e intentar compararlo, solo compara los valores clave pasados a la instancia. Así que debería estar bien (si ligeramente aterrador) siempre que evite agregar NaNs.

Estaría muy agradecido por los comentarios sobre cómo manejan otros idiomas claves de coma flotante en contenedores asociativos

Algunos experimentos rápidos en Python (donde set y dict son contenedores asociativos desordenados que contienen claves y valores por referencia) sugieren que las NAN son tratadas como objetos que son desiguales en valor incluso si son "el mismo NAN", pero el mismo objeto nan se puede encontrar de nuevo por identidad. Por lo que he visto, los contenedores no parecen ser molestados por contener múltiples nan, o una mezcla de nan y otros valores:

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