Sobes.tech
Middle

É uma boa ideia usar o tipo float como chave para um contêiner?

sobes.tech IA

Resposta da IA

Utilizar float como chave para contêineres associativos (por exemplo, std::map, std::unordered_map) ou para ordenação direta não é recomendado pelos seguintes motivos:

  • Problemas de comparação: A igualdade de dois números do tipo float (ou double) raramente é atingida devido a erros na representação de ponto flutuante. Comparar a == b pode resultar em falso, mesmo que matematicamente os números sejam iguais. Isso viola os invariantes dos contêineres que requerem uma ordem fraca estrita (std::map e std::set) ou uma função hash e comparação de igualdade corretas (std::unordered_map e std::unordered_set).

  • Ordenação incorreta: Os operadores de comparação padrão para float nem sempre garantem uma ordem fraca estrita para todos os valores possíveis (por exemplo, NaN).

  • Hash instável: A implementação de funções hash para float pode ser instável devido aos mesmos problemas de representação, levando a comportamentos imprevisíveis ou baixo desempenho em tabelas hash.

Abordagens recomendadas:

  1. Usar representação inteira: Se a precisão não for importante ou os números tiverem um intervalo e resolução limitados, pode-se escalar e converter float para um inteiro (por exemplo, int ou long long) e usá-lo como chave.

    float f = 1.23f;
    int key = static_cast<int>(f * 100); // Exemplo de escalonamento
    std::map<int, Value> my_map;
    my_map[key] = some_value;
    
  2. Usar ponto fixo: Para casos em que é necessária uma representação exata de números fracionários, pode-se usar uma biblioteca para trabalhar com números de ponto fixo.

  3. Comparar com tolerância (epsilon): Embora isso não permita usar float como chave diretamente, na busca pode-se comparar valores usando uma pequena tolerância (epsilon).

    bool are_equal(float a, float b, float epsilon = 1e-6) {
        return std::abs(a - b) < epsilon;
    }
    // Não adequado para uso direto como comparador de chaves em map
    
  4. Usar um comparador personalizado (para std::map/std::set): Pode-se definir um comparador personalizado que leva em conta a tolerância, mas isso ainda pode violar o invariantes do ordenamento fraco estrito.

    struct FloatComparer {
        bool operator()(float a, float b) const {
            // Exemplo simples, que pode violar o ordenamento fraco estrito
            return a < b - 1e-6;
        }
    };
    // Não recomendado usar diretamente em aplicações reais
    // std::map<float, Value, FloatComparer> my_map;
    
  5. Usar representação binária em inteiro (para std::unordered_map/std::unordered_set): Para tabelas hash, pode-se converter a representação binária de float em um inteiro e usá-lo como chave. Isso garante a unicidade da chave para cada representação binária de float, mas não resolve o problema de comparação de números em ponto flutuante que são matematicamente iguais, mas têm representações diferentes (por exemplo, 0.0 e -0.0).

    union FloatIntConverter {
        float f;
        int i;
    };
    
    struct FloatHash {
        size_t operator()(float f) const {
            FloatIntConverter converter;
            converter.f = f;
            return std::hash<int>()(converter.i);
        }
    };
    
    struct FloatEqual {
        bool operator()(float a, float b) const {
            // Comparação das representações binárias
            FloatIntConverter converter_a, converter_b;
            converter_a.f = a;
            converter_b.f = b;
            return converter_a.i == converter_b.i;
        }
    };
    // std::unordered_map<float, Value, FloatHash, FloatEqual> my_map;
    // Nota: isso compara as representações binárias, não a igualdade matemática
    

Na maioria dos casos, se as chaves forem números de ponto flutuante, deve-se reconsiderar a estrutura de dados ou usar uma das abordagens com representação inteira ou números de ponto fixo.