map<float, T>::find

[Rares Vernica]

Hello,

How does find works for a map where the key is float?

I know you cannot just simply compare floats for equality, you need to
use fabs and some epsilon. I know map does not use equality, but uses
"less". Still two floats (float a,b might show as a > b when in fact
they are equal.

I am a bit confused.

Thanks,
Ray

 

[Kai-Uwe Bux]

Hello,

How does find works for a map where the key is float?

I know you cannot just simply compare floats for equality,

Well, you can. It just so happens that it is _often_ not what you want to
do.

you need to use fabs and some epsilon.

Sometimes, that is what you want to do.

I know map does not use equality, but uses "less". Still two floats
(float a,b might show as a > b when in fact they are equal.

Well, there are cases where one can get that impression. The standard allows
floating point numbers to have excess precision during computations.
However, operator< has a perfectly well-defined and natural meaning for
float objects (i.e., the corresponding regions in memory). If you make sure
that the floats that you compute are written to memory, they will compare
equal if and only if they are equal and operator< will do what you expect.
The trick part is making sure that the objects are written to memory.

Now, with regard to find(), one may hope that the keys are already written
to memory (if not, declaring the map object volatile or declaring the map
as map< volatile float, ...> might do the trick). Still, we have to worry
about the parameter. I have recently learned on this list that it is enough
that the parameter is passed by value. The compiler is then required to
initialize the corresponding local object accordingly (though, I also
learned that many compilers get this wrong). Unfortunately, map::find()
takes the parameter as a const reference. What you could do is something
like this:

float rid_excess_precision ( float x ) {
return ( x );
}

and then call

my_map.find( rid_excess_precision( float x ) )



An orthogonal issue (and probably a more serious one) is how you obtain the
keys for which you want to search in the first place. Even if you get
around all the problems above, you will only find the entry in the map if
they match the stored values _exactly_ (and that is what a map is supposed
to do). With floats, it can be very tricky to compute the same value twice.
If you can guarantee precision of your computations only up to a certain
epsilon, then you might be better off using map< long, ... > where you use

floor( x / epsilon )

as the key. (You could also come up with different schemes that do a more
logarithmic mapping if you need a better resolution near 0).


Best

Kai-Uwe Bux

 

[James Kanze]

How does find works for a map where the key is float?

Generally, not too well. Unless you know what you're doing,
of course. You have to know what a float really is (and it's
not a real number).

I know you cannot just simply compare floats for equality, you
need to use fabs and some epsilon.

You know wrong. It's frequent to compare floats for equality.
Not as frequent as it is for ints, nor as frequent as it would
be if we had real real numbers, but again: if you know what
you're doing, and use it correctly, it works. And if you don't
then just arbitrarily using fabs and some epsilon won't work
either.

I know map does not use equality, but uses "less". Still two
floats (float a,b might show as a > b when in fact they are
equal.

If the two floats are different, then they aren't equal.
Theoretically, you do have to pay a lot of attention to the
precision; in C++, the compiler is allowed to maintain
intermediate values in extended precision, so something like
0.2+0.2 may not be equal to 0.4. But in this case, the library
has done what is formally required for you: the values in the
map are all in memory, so have the correct precision, and the
value you are comparing is passed by a const reference, which
means a temporary in memory as well. The only problems
(according to the standard) are in cases where expressions are
involved; since std::map can't do arithmetic on the key
type---there's no guarantee that any of the arithmetic operators
are supported---you should be OK. On the other hand, some
compilers aren't too rigorous about applying the rules in the
standard, the fact that std::map is in fact a template, and all
of the code is "visible" in the translation unit, might lead to
some over-optimistic optimizations. (Some compilers---g++, for
example---document this, and offer an option to force the
compiler to adher strictly to the standard.)

 

[Juha Nieminen]

I know you cannot just simply compare floats for equality

Says who?

If I insert an element with the key 1.0f in the map and then I try to
find the element with the key 1.0f, it will find it. Why wouldn't it?

1.0f is completely equal to 1.0f. Why couldn't you compare them for
equality?

Of course a completely different issue is if you want to find a key
inside a certain range (eg. any key between 1.0-1e-7 and 1.0+1e-7).

, you need to

use fabs and some epsilon. I know map does not use equality, but uses
"less". Still two floats (float a,b might show as a > b when in fact
they are equal.

Comparing two floats with a > b will not give true if they are indeed
equal. If a > b returns true, then the floats are different.

(A different story is that two different functions which should
mathematically speaking return the same value might return different
values eg. because of cumulative rounding errors in the different
calculations.)

 

[Ron Natalie]

Hello,

How does find works for a map where the key is float?

I know you cannot just simply compare floats for equality, you need to
use fabs and some epsilon. I know map does not use equality, but uses
"less". Still two floats (float a,b might show as a > b when in fact
they are equal.

Nonsense. You're confused over the way floating point works. The
floating point relational operators for < and = are consistent. What
you may be thinking is not all numbers are exactly specifiable in the
limited precision of a machine floating point number and hence two
numbers that are close enough to be considered for some purposes as
the same are in fact slightly different.

If you have an algorithm that needs to consider this, you are free
to offer your own comparison function rather than std::less. However
BE ABSOLUTELY certain that it is consistent in the comparison,
especially transitivity.