-
December 17th, 2010, 11:46 AM
#1
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
-
December 17th, 2010, 11:58 AM
#2
Re: float as a key in std::map
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.
Cheers, D Drmmr
Please put [code][/code] tags around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky
-
December 17th, 2010, 12:00 PM
#3
Re: float as a key in std::map
I never consider that possibility, but doesn't sound like a good idea to me.
-
December 17th, 2010, 12:07 PM
#4
Re: float as a key in std::map
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.
Is your question related to IO?
Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.
-
December 17th, 2010, 12:12 PM
#5
Re: float as a key in std::map
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
-
December 17th, 2010, 12:18 PM
#6
Re: float as a key in std::map
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;
}
-
December 17th, 2010, 12:25 PM
#7
Re: float as a key in std::map
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.
Is your question related to IO?
Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.
-
December 17th, 2010, 12:44 PM
#8
Re: float as a key in std::map
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
-
December 17th, 2010, 12:54 PM
#9
Re: float as a key in std::map
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.
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
Cheers, D Drmmr
Please put [code][/code] tags around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky
-
December 17th, 2010, 01:17 PM
#10
Re: float as a key in std::map
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?
-
December 17th, 2010, 01:56 PM
#11
Re: float as a key in std::map
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.
Is your question related to IO?
Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.
-
December 17th, 2010, 05:07 PM
#12
Re: float as a key in std::map
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% of the time consistently, with the reason being using the double as the key 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?
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
Last edited by Paul McKenzie; December 18th, 2010 at 04:31 PM.
-
December 18th, 2010, 03:50 AM
#13
Re: float as a key in std::map
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.
-
December 18th, 2010, 05:04 AM
#14
Re: float as a key in std::map
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.
-
December 18th, 2010, 10:49 AM
#15
Re: float as a key in std::map
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.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|