Teclas de punto flotante en std: mapa

Se supone que el siguiente código busca la clave 3.0 en un std::map que existe. Pero debido a la precisión del punto flotante, no se encontrará.

 map mymap; mymap[3.0] = 1.0; double t = 0.0; for(int i = 0; i  0); } 

En el ejemplo anterior, contains siempre será false . Mi solución actual es simplemente multiplicar t por 0.1 en lugar de agregar 0.1, así:

 for(int i = 0; i  0); } 

Ahora la pregunta:

¿Hay alguna manera de introducir un fuzzyCompare en std::map si utilizo llaves double ? La solución común para la comparación de números en coma flotante suele ser algo así como ab < epsilon . Pero no veo una manera directa de hacer esto con std::map . ¿Realmente tengo que encapsular el tipo double en una clase y sobrescribir el operator<(...) para implementar esta funcionalidad?

Podría implementar su propia función de comparación.

 #include  class own_double_less : public std::binary_function { public: own_double_less( double arg_ = 1e-7 ) : epsilon(arg_) {} bool operator()( const double &left, const double &right ) const { // you can choose other way to make decision // (The original version is: return left < right;) return (abs(left - right) > epsilon) && (left < right); } double epsilon; }; // your map: map mymap; 

Actualizado: vea el Ítem ​​40 en STL Efectivo ! Actualizado basado en sugerencias.

Así que hay algunos problemas con el uso de dobles como claves en un std::map .

Primero, NaN , que compara menos que sí mismo, es un problema. Si hay alguna posibilidad de que se inserte NaN , use esto:

 struct safe_double_less { bool operator()(double left, double right) const { bool leftNaN = std::isnan(left); bool rightNaN = std::isnan(right); if (leftNaN != rightNaN) return leftNaN 

pero eso puede ser demasiado paranoico. No, repito, no, incluya un umbral épsilon en su operador de comparación que pase a un std::set o similar: esto violará los requisitos de pedido del contenedor y dará como resultado un comportamiento indefinido e impredecible.

(Puse NaN como mayor que todas las double , incluyendo +inf , en mi orden, sin una buena razón. Menos que todas las double también funcionarían).

Entonces, use el operator< predeterminado operator< , o el anterior safe_double_less , o algo similar.

A continuación, le aconsejo que use std::multimap o std::multiset , ya que debe esperar varios valores para cada búsqueda. También podría hacer que la administración de contenido sea algo cotidiano, en lugar de un caso de esquina, para boost la cobertura de prueba de su código. (Raramente recomendaría estos contenedores). Además, bloquea el operator[] , que no se recomienda utilizar cuando se utilizan teclas de coma flotante.

El punto donde desea usar un épsilon es cuando consulta el contenedor. En lugar de usar la interfaz directa, crea una función auxiliar como esta:

 // works on both `const` and non-`const` associative containers: template auto my_equal_range( Container&& container, double target, double epsilon = 0.00001 ) -> decltype( container.equal_range(target) ) { auto lower = container.lower_bound( target-epsilon ); auto upper = container.upper_bound( target+epsilon ); return std::make_pair(lower, upper); } 

que funciona en std::map y std::set (y multi versiones).

(En una base de código más moderna, esperaría que un objeto de range equal_range mejor para regresar de una función de equal_range . Pero por ahora, lo haré compatible con equal_range ).

Esto encuentra un rango de cosas cuyas claves son "suficientemente cercanas" a la que está solicitando, mientras que el contenedor mantiene sus garantías de pedido internamente y no ejecuta un comportamiento indefinido.

Para probar la existencia de una clave, haz esto:

 template bool key_exists( Container const& container, double target, double epsilon = 0.00001 ) { auto range = my_equal_range(container, target, epsilon); return range.first != range.second; } 

y si desea eliminar / reemplazar entradas, debe considerar la posibilidad de que haya más de una entrada.

La respuesta más corta es "no use valores de coma flotante como claves para std::set y std::map ", ya que es un poco molesto.

Si usa claves de coma flotante para std::set o std::map , casi nunca haga una .find o a [] en ellas, ya que es altamente probable que sea una fuente de errores. Puede usarlo para una colección ordenada automáticamente de cosas, siempre que el orden exacto no importe (es decir, que un 1.0 en particular esté adelante o atrás o exactamente en el mismo lugar que otro 1.0). Incluso entonces, iría con multimap / multiset, ya que confiar en las colisiones o la falta de ellas no es algo en lo que confíe.

El razonamiento sobre el valor exacto de los valores de punto flotante IEEE es difícil, y la fragilidad del código que depende de él es común.

Aquí hay un ejemplo simplificado de cómo usar soft-compare (aka epsilon o casi igual) puede ocasionar problemas.

Deje epsilon = 2 por simplicidad. Pon 1 y 4 en tu map . Ahora podría verse así:

 1 \ 4 

Entonces 1 es la raíz del árbol.

Ahora ponga los números 2 , 3 , 4 en ese orden. Cada uno reemplazará la raíz, porque se compara con ella. Entonces tienes

 4 \ 4 

que ya está roto. (Suponga que no se realiza ningún bash de reequilibrar el árbol.) Podemos continuar con 5 , 6 , 7 :

 7 \ 4 

y esto está incluso más roto, porque ahora si preguntamos si 4 está allí, dirá “no”, y si pedimos un iterador para valores menores que 7 , no incluirá 4 .

Aunque debo decir que he utilizado map basados ​​en este operador de comparación difusa defectuoso en numerosas ocasiones en el pasado, y siempre que abrí un error, nunca fue debido a esto. Esto se debe a que los conjuntos de datos en las áreas de mi aplicación en realidad nunca equivalen a probar el estrés con este problema.

Como dice Naszta , puedes implementar tu propia función de comparación. Lo que omite es la clave para hacerlo funcionar: debe asegurarse de que la función siempre devuelva false para cualquier valor que esté dentro de su tolerancia de equivalencia.

 return (abs(left - right) > epsilon) && (left < right); 

Editar: como se señala en muchos comentarios a esta respuesta y a otras, existe la posibilidad de que esto no salga bien si los valores que alimenta se distribuyen arbitrariamente, ¡porque no se puede garantizar eso !(a y !(b da como resultado !(a . Esto no sería un problema en la pregunta , porque los números en cuestión están agrupados alrededor de 0.1 incrementos; siempre que su épsilon sea lo suficientemente grande como para dar cuenta de todos los posibles errores de redondeo, pero es menor a 0.05, será confiable. Es de vital importancia que las claves del mapa nunca estén más cerca que 2 * epsilon aparte.

Usar dobles como claves no es útil. Tan pronto como realice una aritmética en las teclas, no está seguro de qué valores exactos tienen y, por lo tanto, no puede usarlas para indexar el mapa. El único uso sensato sería que las claves son constantes.