CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 3 123 LastLast
Results 1 to 15 of 34
  1. #1
    Join Date
    Feb 2008
    Posts
    22

    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

  2. #2
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,042

    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

  3. #3
    Join Date
    Oct 2002
    Location
    Timisoara, Romania
    Posts
    14,360

    Re: float as a key in std::map

    I never consider that possibility, but doesn't sound like a good idea to me.
    Marius Bancila
    Home Page
    My CodeGuru articles

    I do not offer technical support via PM or e-mail. Please use vbBulletin codes.

  4. #4
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: float as a key in std::map

    Quote Originally Posted by S__B View Post
    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.

  5. #5
    Join Date
    Feb 2008
    Posts
    22

    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

  6. #6
    Join Date
    Feb 2008
    Posts
    22

    Re: float as a key in std::map

    Quote Originally Posted by monarch_dodra View Post
    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;
    	}

  7. #7
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: float as a key in std::map

    Quote Originally Posted by D_Drmmr View Post
    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.

  8. #8
    Join Date
    Feb 2008
    Posts
    22

    Re: float as a key in std::map

    Quote Originally Posted by monarch_dodra View Post
    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

  9. #9
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,042

    Re: float as a key in std::map

    Quote Originally Posted by monarch_dodra View Post
    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 View Post
    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

  10. #10
    Join Date
    Feb 2008
    Posts
    22

    Re: float as a key in std::map

    Quote Originally Posted by D_Drmmr View Post
    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?

  11. #11
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: float as a key in std::map

    Quote Originally Posted by S__B View Post
    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.

  12. #12
    Join Date
    Apr 1999
    Posts
    27,449

    Re: float as a key in std::map

    Quote Originally Posted by S__B View Post
    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.
    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.

  13. #13
    Join Date
    Nov 2003
    Location
    Belgium
    Posts
    8,150

    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.
    Marc Gregoire - NuonSoft (http://www.nuonsoft.com)
    My Blog
    Wallpaper Cycler 3.5.0.97

    Author of Professional C++, 4th Edition by Wiley/Wrox (includes C++17 features)
    ISBN: 978-1-119-42130-6
    [ http://www.facebook.com/professionalcpp ]

  14. #14
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: float as a key in std::map

    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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  15. #15
    Join Date
    Nov 2003
    Location
    Belgium
    Posts
    8,150

    Re: float as a key in std::map

    Quote Originally Posted by laserlight View Post
    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.
    Marc Gregoire - NuonSoft (http://www.nuonsoft.com)
    My Blog
    Wallpaper Cycler 3.5.0.97

    Author of Professional C++, 4th Edition by Wiley/Wrox (includes C++17 features)
    ISBN: 978-1-119-42130-6
    [ http://www.facebook.com/professionalcpp ]

Page 1 of 3 123 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured