double as map key

double as map key

Post by wangb » Thu, 25 Aug 2005 15:00:11


Hi, if I have to use double as the key of a map,what should I do?
 
 
 

double as map key

Post by Ulrich Eck » Thu, 25 Aug 2005 15:41:10


In general, use map<double, some_value>, just as you would with any other
key.

However, I wouldn't recommend that because floating point calculations are
alway slightly unprecise because there is only a limited number to contain
an infinite range. For example 1.2 can't be expressed as a float or double
- depending on the precision, the closest approximation in either a bit
above or below, but never the exact number. This makes comparisons for
equality moot, you always need to look if a number is in a certain range.

Now, in order to give a better advise what to use, we'd first need to know
what problem you're trying to solve.

Uli

 
 
 

double as map key

Post by Jason Winn » Thu, 25 Aug 2005 21:34:25


I am curious too. People have asked that here before but I can't think
of a case where I would ever want to use double for a map? I mean, in
order to use a map that means you have some sort of data that you
identify uniquely by some real number. It's hard for me to think of a
situation where you need to refer to object by ID# 1.495

Keys are usually things that are very concrete and well-defined.

Jason
 
 
 

double as map key

Post by Ulrich Eck » Thu, 25 Aug 2005 22:48:36


I could imagine a case where I'd consider that: storing sample values. In
that case you have a number of records containing related measured values.
You'd then use one value as key and another as value to achieve a cheap way
of sorting your samples for plotting. Also, you could only use operator[]
for inserting, everything else rather only works through iteration. This is
a hack though, if you want sorting do it with a custom comparator. Also,
you'd better take a multimap<> in most cases or multiset<>, the latter to
prevent accidental modification of the contained samples.

Uli
 
 
 

double as map key

Post by Jason Winn » Thu, 25 Aug 2005 23:42:00

Oh, I have used sorted arrays for the same thing, to store points like
that. I suppose a function is technically a mapping. The reason why
I'd use an array instead is to do searching. But you can use
lower_bound for std::map and lower_bound for std::vector just the same,
so I suppose there isn't that big of a difference. Still, if you aren't
doing a lot of inserts, vector is probably better, because typical
implementations of map use trees, right (red-black I believe in at least
one implementation)? So I'd imagine that if you were creating the
dataset once and iterating or searching lots of times after vector would
be more efficient.

But I apologize for getting off-topic. But now I see how you could use
map<double, ?> for some useful purpose. So now we need more information
from the original poster about what he wants to do.

Jason
 
 
 

double as map key

Post by wangb » Fri, 26 Aug 2005 11:03:43

Hi,
Thanks for your help, What i want to do it's just store something in a
map, but somebody told me, when use double, some number we think it's equal
will be not equal for the precision problem.If that's true,it will cause
error.Can I write my our function like
std::greater<double> to tell the map if fabs(key1-key2) < 0.000000001,it
will be equal?

Sorry for my poor english.




"wangbo" < XXXX@XXXXX.COM >
 
 
 

double as map key

Post by wangb » Fri, 26 Aug 2005 11:22:23

Hi,
Thanks for your help, What i want to do it's just store something in a
map, but somebody told me, when use double, some number we think it's equal
will be not equal for the precision problem.If that's true,it will cause
error.Can I write my our function like
std::greater<double> to tell the map if fabs(key1-key2) < 0.000000001,it
will be equal?

Sorry for my poor english.



"Jason Winnebeck" < XXXX@XXXXX.COM > ????



In
values.
way
operator[]
is
to
 
 
 

double as map key

Post by Igor Tande » Fri, 26 Aug 2005 12:08:07


No you can't. Such a relation is not transitive. That is, it is possible
that x === y and y === z but x !== z (where === means "close enough" as
you define above), for example for y == x + eps and z == x + 2 * eps
where eps is slightly smaller than your threshold of 0.000000001. But an
equivalence relation must be transitive for the map to work properly.
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925
 
 
 

double as map key

Post by Ken Alvers » Fri, 26 Aug 2005 22:59:27


Unfortunately, what you describe would not be transitive. Say your tolerance
was 0.1. Then you would have the following:

0.05 = 0.14
0.14 = 0.23

however,

0.05 < 0.23

You would have to use a comparison function that didn't create these
discrepancies...If you really wanted, you could truncate both numbers and
compare the result, however that could still fail as inaccuracies accumulate.
In reality, doubles are not exact, and having a key that is inexact is
probably ill-advised in any case.

Ken
 
 
 

double as map key

Post by P.J. Plaug » Fri, 26 Aug 2005 23:41:38


Right, and remember that what you really need for a map ordering rule
must enforce a strict weak ordering. Basically, this means that
a < b && b < a must never be true. (And that rules out NaNs as keys,
which is a whole 'nother aspect of using doubles as keys.)

P.J. Plauger
Dinkumware, Ltd.
http://www.yqcomputer.com/