VC STL - double as map key

Author

double as map key

wangbo

2005-08-24, 3:58 am

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

Ulrich Eckhardt

2005-08-24, 3:58 am

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

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

Jason Winnebeck

2005-08-24, 7:58 am

Ulrich Eckhardt wrote:
> In general, use map<double, some_value>, just as you would with any other
> key.
>
> ...
>
> Now, in order to give a better advise what to use, we'd first need to know
> what problem you're trying to solve.

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

Ulrich Eckhardt

2005-08-24, 7:02 pm

Jason Winnebeck wrote:
> ... 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

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

Jason Winnebeck

2005-08-24, 7:02 pm

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

Ulrich Eckhardt wrote:
> Jason Winnebeck wrote:
>
>
>
> 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
>

wangbo

2005-08-24, 9:57 pm

wangbo

2005-08-24, 9:57 pm

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" <gillius-ng@NOSPAM.gillius.org> ????
news:uG1h9nLqFHA.3544@TK2MSFTNGP15.phx.gbl...[color=darkred]
> 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
>
> Ulrich Eckhardt wrote:
In[color=darkred]
values.[color=darkred]
way[color=darkred]
operator[][color=darkred]
is[color=darkred]
to[color=darkred]

Igor Tandetnik

2005-08-25, 3:58 am

"wangbo" <wangbo_coldwind@hotmail.com> wrote in message
news:eej6tpRqFHA.1336@TK2MSFTNGP11.phx.gbl
> 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?

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

Ken Alverson

2005-08-25, 7:03 pm

"wangbo" <wangbo_coldwind@hotmail.com> wrote in message
news:et$0upRqFHA.1336@TK2MSFTNGP11.phx.gbl...
> 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?

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

P.J. Plauger

2005-08-25, 7:03 pm

"Igor Tandetnik" <itandetnik@mvps.org> wrote in message
news:eyY54ISqFHA.3724@TK2MSFTNGP12.phx.gbl...

> "wangbo" <wangbo_coldwind@hotmail.com> wrote in message
> news:eej6tpRqFHA.1336@TK2MSFTNGP11.phx.gbl
>
> 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.

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.dinkumware.com

Sponsored Links