c++ - unordered_map - ¿Es NaN un valor clave válido para contenedores asociativos?

unordered_map c++ example

Question

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

¿Es NaN un tipo de clave válido?

Con los contenedores ordenados, debería decir "no", porque no respeta el estricto ordenamiento débil.

Con los contenedores desordenados, no tengo ni 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 se tratan de la misma manera, lo que espero, aunque parece 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 yo esperaría.

¿La norma tiene que decir algo al respecto?

Actualización: gracias a las excelentes respuestas a continuación, tenga en cuenta que std::map se interrumpirá si inserta algo más en él una vez que haya un NaN en él.

(Estaré muy agradecido por los comentarios sobre cómo otros idiomas manejan las claves de punto flotante en contenedores asociativos).

Answer 1

Ambos están prohibidos por la norma.

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 los requisitos son que comp y equiv 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 en los valores de tipo Key ". Las relaciones de equivalencia son reflexivas, y std::equal_to<double>()(NaN,NaN) es falso, por equal_to<double>() tanto equal_to<double>() no es una relación de equivalencia.

Por cierto, incrustar contenedores en una doble da un poco de miedo de la misma manera que comparar dobles para la igualdad es siempre un poco de miedo. Nunca sabes lo que obtendrás en lo más mínimo.

Algo que siempre he considerado un poco extraño es que el estándar expresa los requisitos en términos del tipo de clave, no en términos de los valores clave reales agregados al contenedor. Creo que podría elegir leer esto porque no garantiza que map<double, int> tiene un comportamiento definido si la implementación es compatible con NaN, independientemente de si agrega un NaN a una instancia o no. Sin embargo, en la práctica, una implementación de std::map no puede conjurar un NaN de su bolsillo trasero y tratar de compararlo, solo compara valores clave pasados ​​a la instancia. Por lo tanto, debería estar bien (si es que da un poco de miedo) siempre que evite agregar NaN.

Estaré muy agradecido por los comentarios sobre cómo otros idiomas manejan las claves de punto flotante en contenedores asociativos

Algunos experimentos rápidos en Python (donde set y dict son contenedores asociativos no ordenados que contienen claves y valores por referencia) sugieren que los NaN se tratan como objetos que tienen un valor desigual, incluso si son "el mismo NaN", pero el mismo nan objeto puede ser encontrado de nuevo por identidad. Por lo que he visto, los contenedores no parecen estar perturbados por contener varios nans, o una mezcla de nans 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

Answer 2

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 hash (no ordenado) ) mapa

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

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

Answer 3

NaN se pueden almacenar dentro de un mapa, es decir, son copiables y no comparables. std::less for double no cumple con los requisitos del mapa para un estricto ordenamiento débil, por lo que técnicamente tiene un comportamiento indefinido aquí. Sin embargo, el comportamiento se explica fácilmente, incluso si no es requerido por la norma. El mapa utiliza la equivalencia en lugar de la igualdad para determinar si un elemento es un duplicado. Dos NaN comparan equivalentes, pero no iguales. Sin embargo, eso se desmorona en algunos casos. Por ejemplo, si intentas insertar algo que no sea un NaN en ese mapa, se trataría como equivalente al NaN y no obtendrías ninguna inserción. Intente agregar algunos números reales además de los NaN y también podrá ver el mapa desglosado.

El comportamiento del hash es esperado, pero no está definido para una tabla hash también. Las tablas hash requieren que sus contenidos sean copiables y comparables en igualdad. Los hashes de múltiples NaN se comparan de la misma forma, por lo que todos van a ir al mismo grupo, pero una tabla hash usa la comparación de igualdad en lugar de la comparación (igualdad en lugar de equivalencia). Por lo tanto, ninguno de los NaN se compara entre sí y se obtienen varias inserciones para esa clave. Esto se debe a que NaN rompe el requisito de igualdad de la tabla hash, es decir, el invariante que std :: equal_to (x, x) es verdadero.