float as a key in std::map

Hi,
It is reasonable to use floating point number as a key in std::map. Would it fail while trying to lookup for a keymap?
Thanks
SB

Depends how you want to use it. In any case, if you are afraid of rouding errors, you could write a comparison predicate that uses a certain precision to compare two floating point numbers. Then you can pass that predicate to the map.

I never consider that possibility, but doesn't sound like a good idea to me.

Quote:

---

Originally Posted by S__B

Hi,
It is reasonable to use floating point number as a key in std::map. Would it fail while trying to lookup for a keymap?
Thanks
SB

---

Depends.

If you use map::operator[] or map::find to find an exact match, you will probably fail miserably.

However, it is completely fine if you want to use it to store a range, and use map::lower_bound/map::upper_bound, it is perfectly fine.

I'm a bit confused with the working of map versus hash_map. For the hash_map the "Equal" is used to find the item, whereas the map seems to take "LessThan" as a template argument. Is that sufficient for finding an item?
Thanks
SB

Quote:

---

Originally Posted by monarch_dodra

Depends.

If you use map::operator[] or map::find to find an exact match, you will probably fail miserably.

However, it is completely fine if you want to use it to store a range, and use map::lower_bound/map::upper_bound, it is perfectly fine.

---

I need to use it for find. In fact, I am debugging someone's code and find this usage, and am a bit skeptical of it. So, I wrote a small test application, which seems to work quite fine. I don't see any issues. But is there anything that I am missing and can be disasterous?

Code:

---

using namespace std;
        map<double,int> m;
        vector<double> v;
        int i;
        for( i = 0; i < 10; i++ ) {
                double d = (double) rand() / RAND_MAX * M_PI;
                d = exp( d );
                v.push_back(d);
                cout << (v[i]-d) << endl;
                m.insert(make_pair(d,i));
        }

        for( i = 0; i < v.size(); i++ ) {
                //cout << m[v[i]] << endl;
                map<double,int>::iterator it = m.find(v[i]);
                cout << (v[i]-it->first) << endl;
        }
        for( map<double,int>::iterator it = m.begin(); it != m.end(); ++it ) {
                //cout << (it->second-it->second) << endl;
        }

---

Quote:

---

Originally Posted by D_Drmmr

Depends how you want to use it. In any case, if you are afraid of rouding errors, you could write a comparison predicate that uses a certain precision to compare two floating point numbers. Then you can pass that predicate to the map.

---

I think you would run into problems with that, as your predicate would not be transitive. For example, according to your predicate, 0.3 is equivalent to 0.4 and 0.4 is equivalent to 0.5, but 0.3 would not be equivalent to 0.5. While I don't think that is too much of a problem with a standard map, it might wreak havoc on a multimap.

I think it would be more advisable to use a map with a classic predicate, and implement a "lax_find" and "lax_insert"method that searches for your keys using lower_bound. At least, you know exactly what you are doing, and not subverting the underlying container.

PS. I could not find the exact requirements on map predicates.

Quote:

---

Originally Posted by monarch_dodra

I think you would run into problems with that, as your predicate would not be transitive. For example, according to your predicate, 0.3 is equivalent to 0.4 and 0.4 is equivalent to 0.5, but 0.3 would not be equivalent to 0.5. While I don't think that is too much of a problem with a standard map, it might wreak havoc on a multimap.

I think it would be more advisable to use a map with a classic predicate, and implement a "lax_find" and "lax_insert"method that searches for your keys using lower_bound. At least, you know exactly what you are doing, and not subverting the underlying container.

PS. I could not find the exact requirements on map predicates.

---

I think I don't quite follow this. First, for std::map, I need to define LessThan() not EqualTo(). Correct? (this behavior is opposite to the hash_map, which I normally use) How this translates to finding the item is beyond me. My understanding is that for each key, an "internal key" is generated, which is then used as the key in the hashtable. For hash_map, one can provide a hashing function, which generates such an "internal key" that is as unique as possible. But even is two numbers turn out to have similar "internal keys" there is a way to resolve the issue. So in the end, is this LessThan required to resolve the ambiguity of similar keys? But how this can avoid floating point errors?

Now here for std::map, suppose I have a key "K" which is a float. I add an item, (K,I) in the map. Why it won't be able to find this item later when I search? Is it possible to have
(K - K) not equal to 0?

Thanks
SB

Quote:

---

Originally Posted by monarch_dodra

I think you would run into problems with that, as your predicate would not be transitive. For example, according to your predicate, 0.3 is equivalent to 0.4 and 0.4 is equivalent to 0.5, but 0.3 would not be equivalent to 0.5. While I don't think that is too much of a problem with a standard map, it might wreak havoc on a multimap.

---

Good point. You'd need to set the epsilon value such that this situation won't occur.
However, I don't think that using the default predicate is possible in general, since IIRC it is not guaranteed that a comparison using floats will yield the same result every time. If the value is moved to a register or memory, it can be truncated/rounded, yielding a different result of a comparison.

Quote:

---

Originally Posted by S__B

I need to use it for find. In fact, I am debugging someone's code and find this usage, and am a bit skeptical of it. So, I wrote a small test application, which seems to work quite fine. I don't see any issues. But is there anything that I am missing and can be disasterous?

---

Note that the problems comparing floating point values hold in general. Your specific compiler may have an option to avoid at least some of these errors. E.g. in VS you have a compiler option that will avoid the problems with floating point values that linger in the processor. This would make it possible to use a std::map<float, int> as long as you don't rely on the result of a computation being equal to the result of a different computation.

What I mean is that this can be guaranteed using this compiler option:

Code:

---

float x = 0.1 + 0.1;
assert(x == 0.1 + 0.1); // works in VS with /fp:precise

---

whereas it cannot be guaranteed in general.
However, this still isn't guaranteed

Code:

---

float x = 0.1 + 0.1;
assert(x == 0.2); // might fail

---

Quote:

---

Originally Posted by D_Drmmr

What I mean is that this can be guaranteed using this compiler option:

Code:

---

float x = 0.1 + 0.1;
assert(x == 0.1 + 0.1); // works in VS with /fp:precise

---

whereas it cannot be guaranteed in general.
However, this still isn't guaranteed

Code:

---

float x = 0.1 + 0.1;
assert(x == 0.2); // might fail

---

---

But if I don't add or subtract anything, it should work? For example,
1. an array initialized with all possible "floating point key values".
2. map initialized with (key,item) where keys are used from the array in (1).
3. use elements of array in (1) to find different keyitems in the map
Please correct me if I'm wrong?

Quote:

---

Originally Posted by S__B

But if I don't add or subtract anything, it should work? For example,
1. an array initialized with all possible "floating point key values".
2. map initialized with (key,item) where keys are used from the array in (1).
3. use elements of array in (1) to find different keyitems in the map
Please correct me if I'm wrong?

---

The bottom line is that floating point arithmetic isn't exact. Worst yet, not only is it not exact, but it goes against common assumptions:

[29.16] Why is floating point so inaccurate? Why doesn't this print 0.43?
[29.17] Why doesn't my floating-point comparison work?
[29.18] Why is cos(x) != cos(y) even though x == y? (Or sine or tangent or log or just about any other floating point computation)

Once you read this, you should understand all the pitfalls with floating point calculations, and why it is so difficult to rely on them.

So to answer your question to the best i can: Maybe it will work, maybe it won't. I'm sorry.

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

*Almost.

Quote:

---

Originally Posted by S__B

I need to use it for find. In fact, I am debugging someone's code and find this usage, and am a bit skeptical of it. So, I wrote a small test application, which seems to work quite fine.

I don't see any issues. But is there anything that I am missing and can be disasterous?

---

How many compilers did you test this on? How many versions of the compiler you're using did you test this on? What compiler options did you test this with? What values did you use?

The bottom line, as monarch_dodra mentioned, is that your program is basically ill-formed in terms of consistency. You are using a double in a "raw" fashion to do lookups into a map. Since the ordering of the map depends on the ordering of the keys, the values of those keys, if they're computed can be different if you changed compilers, versions, CRT, settings, etc. So your program will have different behaviour using the same code and the same input data.

Even if you run this on all the compilers in the shop, you can't guarantee it works 100&#37; of the time consistently, with the reason being using the double as the key in the map.

Quote:

---

Why it won't be able to find this item later when I search? Is it possible to have
(K - K) not equal to 0?

---

This is even a bigger issue than the map.

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.

Floating point math isn't the same as algebra or school-book math. You can never assume that what you do by hand using decimal point values works with exact precision with binary floating point. Even the most simplest things aren't what they seem:

Code:

---

for (double i = 0.0; i <= 1.0; i += 0.001)
{
}

---

How many times is this loop executed? The round-off error by adding 0.001 each time could throw the number of times that loop executes off by 1.

Regards,

Paul McKenzie

The LessThan is only used to *order* the elements in a map because the std::map is an ordered container. It's not used to *find* an element which might cause problems with floating point values.
C++0x includes new containers called *unordered associative* containers and these don't order their elements.

Quote:

---

Originally Posted by Marc G

The LessThan is only used to *order* the elements in a map because the std::map is an ordered container. It's not used to *find* an element which might cause problems with floating point values.

---

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.

Quote:

---

Originally Posted by laserlight

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.

---

My mistake.