float as a key in std::map

[Marc G]

[ merged threads ]

Don't start multiple threads on the same issue.

[S__B]

If you are talking about the "LessThan" comparison with respect to the current standard associative containers, then that is not true: equivalent keys, which is what the find() member function looks for, is defined in terms of the "LessThan" comparison.

QUESTION 1: I think I am missing something here. I am not sure how "map" will use "LessThan" for "find". Can you please explain, or point to a link?

This is why I recommend you try an approach where you can guarantee your searches. For example, a ranged search that can give all the keys between [target-epsilon, target+epsilon]. This way, if your key is almost equal, but not exactly equal, you will still find it. With this approach, at least, you don't have to worry about all that dangerous floating point crap*.

QUESTION 2: How to define a "LessThan" with an epsilon?

What if the second K in that equation is computed, and the hand calculation shows what you should have is K - K, but the computer calcuation shows that the first K is not exactly equal to the second K, maybe off by 0.00000001? Your lookup fails even though algebraically it should have worked.

QUESTION 3: I know the general issues with "floats" but in my case if all keys are stored in a "vector", and then "map" is created from these keys, and finally the "vector" is used to search for items in the "map", why it will fail. The point is that no matter what the compiler or the compiler settings are, once a float e.g. 0.43 is stored in an array (e.g. as 0.430000001), it will remain 0.430000001. So instead of 0.43 as being a key, the key would be "0.430000001". Then the question is why it would be problematic, more problematic using an epsilon tolerance?

[Lindley]

QUESTION 1: I think I am missing something here. I am not sure how "map" will use "LessThan" for "find". Can you please explain, or point to a link?

Two items are considered equal if a == b is true. This is the test used by std::find().

Two items are considered equivalent if !(a < b) && !(b < a). This is the test used by std::map::find().

QUESTION 2: How to define a "LessThan" with an epsilon?

I don't think it's possible, for the above-mentioned reasons.

QUESTION 3: I know the general issues with "floats" but in my case if all keys are stored in a "vector", and then "map" is created from these keys, and finally the "vector" is used to search for items in the "map", why it will fail. The point is that no matter what the compiler or the compiler settings are, once a float e.g. 0.43 is stored in an array (e.g. as 0.430000001), it will remain 0.430000001. So instead of 0.43 as being a key, the key would be "0.430000001". Then the question is why it would be problematic, more problematic using an epsilon tolerance?

In that case it should be fine.....but it creates a "delicate" situation in which a later change by another coder who doesn't understand this subtlety could bring the whole thing crashing down. That's the sort of situation it's better to avoid if you can.

[S__B]

Two items are considered equal if a == b is true. This is the test used by std::find().

Two items are considered equivalent if !(a < b) && !(b < a). This is the test used by std::map::find().



I don't think it's possible, for the above-mentioned reasons.



In that case it should be fine.....but it creates a "delicate" situation in which a later change by another coder who doesn't understand this subtlety could bring the whole thing crashing down. That's the sort of situation it's better to avoid if you can.

Thanks Lindley for the clarification. In this case, I'm "another code" trying to debug some of the inherited code, without crashing it down.
The situation is that the keys instead of floats is the coordinates of a point in 3D, i.e., the following structure:

class CPoint3D
{ 
public: 
float x, y, z; 

public:
static bool operator< (const CPoint3D& a, const CPoint3D& b)
{
    if ( a.x < b.x )
        return true;
    else if ( a.x > b.x )
        return false;
    else if ( a.y < b.y )
        return true;
    else if ( a.y > b.y )
        return false;
    else if ( a.z < b.z )
        return true;
    else if ( a.z > b.z )
        return true;
    else
        return false;
}
};

Given the delicate balance described above, this should work as a "consistent" LessThan function.

[Lindley]

I think one of those return statements might be wrong.

[Paul McKenzie]

if all keys are stored in a "vector", and then "map" is created from these keys

How do you access the keys in the vector? What operations do you do to say "get me my value in the vector" and I will place it in the map"? Do not assume that this is even safe to do with floating point values.

To access the float, possibly a floating point CPU instruction is done which could cause a slight modification of the number, and that thing you never expected to happen just happens. Floating point trouble not only happens during calculation -- passing them by value, assignment, etc. could lead to these issues.

Regards,

Paul McKenzie

[S__B]

I think one of those return statements might be wrong.

Thanks Lindley for pointing out a problem.

How do you access the keys in the vector? What operations do you do to say "get me my value in the vector" and I will place it in the map"? Do not assume that this is even safe to do with floating point values.

To access the float, possibly a floating point CPU instruction is done which could cause a slight modification of the number, and that thing you never expected to happen just happens. Floating point trouble not only happens during calculation -- passing them by value, assignment, etc. could lead to these issues.

Paul, you are suggesting a serious flaw in this implementation. I thought that when a value is fetched into an internal register, it is just mirrored (a binary mirror) so that it won't change. Another question is that would this "problem" be more pronounced if it is compiled for 32-bit machines, but run on 64-bit machine. I am not sure, I know how it will handle the internal registers in such case. Or the behavior will be similar on either machines.
Thanks,
SB

[monarch_dodra]

QUESTION 2: How to define a "LessThan" with an epsilon?

I don't think it's possible, for the above-mentioned reasons.

What I was thinking was something like this:

#include <string>
#include <map>
#include <iostream>

static const double epsilon = 0.05;

std::map<double, std::string>::const_iterator find_approximatly(const std::map<double, std::string>& i_map, double i_key)
{
    std::map<double, std::string>::const_iterator it_low = i_map.lower_bound(i_key-epsilon);

    if(it_low == i_map.end())
        {return i_map.end();}

    const double found_value = it_low->first;
    if (found_value > i_key+epsilon)
        {return i_map.end();}

    return it_low;
}

int main()
{
    std::map<double, std::string> a_map;
    a_map[0.1] = "0.1";
    //a_map[0.1] = "0.1";
    a_map[0.49] = "0.49";

    {
        double first_key = 0.1;
        std::cout << "searching: " << first_key;
        std::map<double, std::string>::const_iterator first_found = find_approximatly(a_map, first_key);
        if (first_found != a_map.end())
            {std::cout << " found at: " << first_found->second << " actual double value: " << first_found->first << std::endl;}
        else
            {std::cout << " not found " << std::endl;}
    }

    {
        double second_key = 0.3;
        std::cout << "searching: " << second_key;
        std::map<double, std::string>::const_iterator second_found = find_approximatly(a_map, second_key);
        if (second_found != a_map.end())
            {std::cout << " found at: " << second_found->second << " actual double value: " << second_found->first << std::endl;}
        else
            {std::cout << " not found " << std::endl;}
    }

    {
        double third_key = 0.5;
        std::cout << "searching: " << third_key;
        std::map<double, std::string>::const_iterator third_found = find_approximatly(a_map, third_key);
        if (third_found != a_map.end())
            {std::cout << " found at: " << third_found->second << " actual double value: " << third_found->first << std::endl;}
        else
            {std::cout << " not found " << std::endl;}
    }
}

output:

searching: 0.1 found at: 0.1 actual double value: 0.1
searching: 0.3 not found
searching: 0.5 found at: 0.49 actual double value: 0.49

[Eri523]

But wouldn't a < with an epsilon tolerance be rather some sort of <=, simply violating the strict weak ordering rule?

Just my $.02...

[monarch_dodra]

But wouldn't a < with an epsilon tolerance be rather some sort of <=, simply violating the strict weak ordering rule?

Just my $.02...

Well, the point would be that the container still uses the strict operator<. However, whenever you as the user are looking for a specific key, you can use approximate_search, to have a broader search. approximate_search still use a strict ordering.

The basic idea is to make a basic wrapper around your container, but you avoid subverting it by giving an odd "less than or just a little more" operator.

[Paul McKenzie]

Paul, you are suggesting a serious flaw in this implementation. I thought that when a value is fetched into an internal register, it is just mirrored (a binary mirror) so that it won't change. Another question is that would this "problem" be more pronounced if it is compiled for 32-bit machines, but run on 64-bit machine. I am not sure, I know how it will handle the internal registers in such case. Or the behavior will be similar on either machines.
Thanks,
SB

My bottom line is that writing such code has inherent faults. If it's not calculation, it will be something else unexpected.

One question -- how are you going to debug such a program if a customer (if you have customers) reports a problem (wrong values being used, for example)? I would take a big gulp and prepare for sleepless nights.

Regards,

Paul McKenzie

[Chris_F]

class CPoint3D
{ 
public: 
float x, y, z; 

public:
static bool operator< (const CPoint3D& a, const CPoint3D& b)
{
    if ( a.x < b.x )
        return true;
    else if ( a.x > b.x )
        return false;
    else if ( a.y < b.y )
        return true;
    else if ( a.y > b.y )
        return false;
    else if ( a.z < b.z )
        return true;
    else if ( a.z > b.z )
        return true;
    else
        return false;
}
};

Usually, when dealing with coordinates like this, you compare the length of the vector.

http://www.math.montana.edu/frankw/c...tude/refer.htm

[S__B]

Usually, when dealing with coordinates like this, you compare the length of the vector.

http://www.math.montana.edu/frankw/c...tude/refer.htm

A problem in that case would be that it won't result in something unique. Please correct me if I'm wrong.

[monarch_dodra]

A problem in that case would be that it won't result in something unique. Please correct me if I'm wrong.

Both have their advantages and disadvantages.

The advantage of using coordinates is that it results in a unique ordering. The disadvantage to it is that the order of your nodes can change drastically if one of them is moved even just a little bit.

The advantage of using vector length is that it uses an actual mathematical/physical value, which is the Euclidean Norm (although almost any 3D norm will do). An advantage to doing this is that for starters, it makes sense by looking at a graph which nodes are order before what other nodes, and the ordering is more robust to tiny changes in point positions.

[itsmeandnobodyelse]

My bottom line is that writing such code has inherent faults. If it's not calculation, it will be something else unexpected.

One question -- how are you going to debug such a program if a customer (if you have customers) reports a problem (wrong values being used, for example)? I would take a big gulp and prepare for sleepless nights.

Regards,

Paul McKenzie

I strongly want support what Paul has said. Floating point numbers are not suitable for being used as keys. The 'same' mathematical value can be represented with different bits and cannot be found anymore in the map, e. g. value 12 can be represented as 12.000000000... or as 11.9999999999... (even in math) depending on statements like x = 12. or x = sqrt(144); .

For the 3D coordinates you probably have equidistant values (if not, how would you ever expect to find a point again?). Then, you easily can substitute the floats by integers by counting the steps, thus avoiding any of the issues discussed here.

For the less function I wouldn't use a length-based approach. If you ever want to iterate thru all points of that mapping you probably would value the fact when the points were neatly ordered by their coordinate values. Moreover, by using the length you could get unique keys for different points what would spoil your map. And a multimap surely make no sense.