c++ - flotante - norma ieee 754 pdf

¿Los flotadores IEEE son tipos de clave válidos para std:: map y std:: set?

Question

Fondo

El requisito de un comparador en el tipo de clave de un contenedor asociativo (por ejemplo, std :: map) es que impone un orden débil estricto en los elementos del tipo de clave.

Para un comparador dado comp(x, y) definimos equiv(x, y) = !comp(x, y) && !comp(y, x) .
Los requisitos para que comp(x, y) sea ​​un orden débil estricto son

1. Irreflexibilidad ( !comp(x, x) Comp ( !comp(x, x) para todo x )
2. Transitividad del orden (si comp(a, b) y comp(b, c) luego comp(a, c) ).
3. Transitividad de equivalencia (si equiv(a, b) y equiv(b, c) luego equiv(a, c) )

std::less<float> (el comparador predeterminado) usa operator< , que no crea un orden débil estricto debido a NaN . Como x < NaN y NaN < x son falsos para todo x , NaN es equivalente a todos los flotantes bajo este comparador, esta condición de ruptura # 3: equiv(1.0, NaN) y equiv(NaN, 2.0) pero no equiv(1.0, 2.0) Para los flotantes IEEE excepto NaN, es un orden débil estricto (donde cada número tiene su propia clase de equivalencia excepto para 0 y -0 ).

La pregunta

¿Esto significa que el estándar C ++ no permite utilizar flotantes IEEE (y dobles largos) como un tipo de clave en un contenedor asociativo debido a la cuestión anterior, incluso si me aseguro de que NaN nunca se inserta en el contenedor ? No estoy muy seguro sobre la redacción de "elementos de Key " en el estándar, si esto significa todos los elementos posibles o solo los elementos que terminan en el contenedor.

Nota: La pregunta no es sobre problemas wrt. truncamiento / redondeo, probablemente publique una pregunta diferente al respecto pronto.

Actualizar:

Suspiro Debería haber planteado la pregunta sin especificar flotación, solo pensé que era un buen ejemplo.

La pregunta realmente es : ¿se permite usar un comparador que solo impone un orden débil estricto sobre los elementos que se colocan en el contenedor, no todas las instancias posibles del tipo de clave? Por favor, no responda simplemente "sí" o "no", me gustaría algunas referencias a las discusiones estándar / previas sobre esta / una respuesta de un miembro del comité o algo así.

Answer 1

Colocar flotantes como claves de un contenedor asociativo a veces es una mala idea ya que la semántica de igualdad es bastante pobre. Pero depende de lo que quieras hacer. Tenga en cuenta que NaN e infinidades generalmente no son un problema. Puede manejarlos con funciones especiales de comparación (generalmente no), y obviamente los requisitos del estándar se refieren a las claves reales que terminarán en el contenedor , que puede ver como un subconjunto del tipo de clave. Una implementación de mapa nunca presentará instancias clave que usted no haya introducido en el mapa.

Una vez utilicé este predicado para un mapa en el que podía rechazar dos valores muy cercanos:

struct FuzzyComparer
{
    template <typename T>
    bool operator()(T x, T y) const
    {
        static const T oneMinusEps = (T)1. - 64 * std::numeric_limits<T>::epsilon();
        return x / y < oneMinusEps;
    }
};

Esto no le proporciona una buena relación de equivalencia. Esto solo es útil cuando desea almacenar valores discretos de coma flotante, y está listo para tolerar algún error de redondeo en el cálculo que arroje la clave que desea recuperar. Para las claves reales que se insertarán , produce una relación de equivalencia.

No podrá encontrar una buena relación de equivalencia en números de coma flotante que sea compatible con las operaciones aritméticas, es decir. con hace suma y multiplicación asociativa.

O bien tiene que descartar la parte de "relación de equivalencia", que no debería ser tan importante en el código del mundo real (dudo que se use la transitividad de la relación eq en una medida que le molestaría en una implementación de mapa típica). ) o descartar la compatibilidad con operaciones aritméticas. Pero, ¿de qué sirve usar valores de punto flotante como claves?

Answer 2

En resumen: esto está bien (en el sentido de que se trata de su pregunta).

Si evita los valores (es decir, NaN ) que no cumplirían los requisitos de pedido, entonces el comportamiento está completamente definido.

Answer 3

Puede poner flotantes y dobles como la clave de un std :: map o std :: set para que se clasifiquen correctamente.

El problema es cuando se trata de la singularidad, ya que es posible que se dupliquen debido a la forma en que se comparan los flotantes y los dobles.

Usar una comparación basada en épsilon (valores cercanos considerados iguales) tampoco está exenta de peligros, ya que podría eliminar los no duplicados genuinos por estar demasiado cerca.

Es posible que la "búsqueda" no encuentre un elemento que esté allí si usa el simple "buscar", por lo que puede usar algún tipo de búsqueda épsilon con upper_bound () en x-delta donde x es lo que realmente está buscando, y permitiendo un valor que es menor que x + delta.

Dado todo eso, claramente no hay problema de usar float o double como clave en std :: multiset o std :: multimap siempre que use upper_bound para buscar en lugar de equal_range.

Con respecto a los NaN, si el conjunto o el mapa no están vacíos, se considerarían "iguales" a cualquier elemento que ya esté allí y, por lo tanto, no se insertarían. Si inserta primero un NaN, todas las inserciones posteriores deberían fallar.

Se considerarían iguales porque x<NaN y NaN<x ambos evalúan falso.

Por supuesto, con la misma lógica si se trata de un mapa y se llama

myMap[ NaN ] = x;

podría modificar justificadamente cualquier elemento.

(Lo mismo si find(NaN) , que podría devolver cualquier iterador).

Por lo tanto, si va a tener NaN en cualquier parte de este cálculo, use un comparador especial como el de Steve Jessop.

Answer 4

Sospecho que las restricciones deberían tomarse como referencias al comportamiento de la relación en los valores que se usan realmente como claves, no necesariamente en todos los valores del tipo. No tiene tiempo en este momento para pasar por el estándar en busca de un lenguaje de "pistola humeante" que se refiera a los elementos reales del contenedor en lugar de a todos los valores del tipo.

Caso similar: ¿qué ocurre si un comparador (para un contenedor de punteros o punteros inteligentes) llama a una función virtual y alguien vincula una clase derivada del tipo que compara, que anula la función virtual de modo que el comparador no sea un estricto débil ¿orden? ¿El programa se vuelve indefinido incluso si nadie alguna vez usa esa clase derivada?

En caso de duda, puede admitir NaN con un comparador que sea un orden débil estricto:

bool operator()(double a, double b) {
    if ((a == a) && (b == b)) {
        return a < b;
    }
    if ((a != a) && (b != b)) return false;
    // We have one NaN and one non-NaN.
    // Let''s say NaN is less than everything
    return (a != a)
}

Las dos últimas líneas "optimizan" para return (b == b); , aunque no estoy seguro de que el comentario se optimice con eso.

Creo que Tomalak me ha convencido de que el lenguaje dice que todo el tipo debe ser ordenado.

Esto tiene poco sentido, ya que un mapa no evoca valores de la nada, solo usa los valores que se le dan (y copias de ellos), pero la pregunta es acerca de las reglas, y las reglas son las que yo sepa. C ++ 0x es lo mismo. Me pregunto si hay un informe de defectos o algún punto para enviar uno.

También es molesto porque en sistemas (muy raros) donde std::less es lento para los punteros, no puede usar < como el comparador en un mapa de punteros, incluso si sabe que los punteros son todos elementos de la misma formación. Vergüenza.

Otra opción es usar la siguiente clase como tipo de clave, de modo que las claves se verifican para NaN solo en la entrada al mapa, no en cada comparación como se indicó anteriormente.

struct SaneDouble {
    double value;
    SaneDouble (double d) : value(d) {
        if (d != d) throw std::logic_error();
    }
    static friend bool operator<(SaneDouble lhs, SaneDouble rhs) {
        return lhs.value < rhs.value;
    }
    // possibly a conversion to double
};

Esto plantea otra pregunta: claramente alguien podría crear un SaneDouble y luego establecer su value en NaN (suponiendo que la implementación les permita obtener uno desde algún lugar sin fallar). Entonces, ¿los "elementos de SaneDouble" están estrictamente ordenados o no? ¿Mi intento poco entusiasta de crear una clase invariante en el constructor hace que mi programa sea indefinido incluso si nadie rompe realmente el invariante, simplemente porque podrían hacerlo y, por lo tanto, los resultados de hacerlo son "elementos de SaneDouble"? ¿Es realmente la intención del estándar que el comportamiento del programa se defina si y solo si el value se marca como private ? ¿El estándar realmente define en algún lugar qué son "los elementos" de un tipo?

Me pregunto si deberíamos interpretar "elementos de clave" para significar que el comparador induce un orden débil estricto sobre algunos elementos de Key. Presumiblemente incluyendo los realmente usados. "Tengo rosquillas" no significa que tengo todas las rosquillas. Sin embargo, es un estiramiento.