«

Hi,

It seems that using floats as the first tupelo for an STL map (shown
below) can cause problems but I don't remember what the problems were.
Is it common practice to use a structure like below? I would appreciate
if you can share your experience using such a structure. Thanks.

std::map<float, int> m;

JD

JDT wrote:
> It seems that using floats as the first tupelo for an STL map (shown
> below) can cause problems but I don't remember what the problems were.

The only thing I can think of is that if you expect two different
results of a calculation to lead to the same number (and ultimately
to the same stored in the map value), you may be in for a surprise.
Due to rounding errors in the FPU the mathematically equivalent
calculations can lead to different numbers internally.

Example, given that 'a' is 1.f and 'b' is 2.f, the expressions
(a + 2.f/3) and (b - 1.f/3) _can_ give you different results.

> Is it common practice to use a structure like below? I would
> appreciate if you can share your experience using such a structure.
> Thanks.
> std::map<float, int> m;

I _never_ saw a 'map' where 'float' would be the Key type. I cannot
claim to have seen all code in the world, and even a significant part
of it, so I cannot attest to "commonality" of the practice.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

Victor Bazarov wrote:
> Example, given that 'a' is 1.f and 'b' is 2.f, the expressions
> (a + 2.f/3) and (b - 1.f/3) _can_ give you different results.

Concrete example:

double d1 = 1.0;
double d2 = 0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1;
std::cout << d1 << " " << d2 << " " << (d1 == d2) << std::endl;

That prints (at least in a regular PC):

1 1 0

Printing the doubles with more decimal places would show the
difference. It's very small, but it's there, thus (d1 == d2) is
false.

Victor Bazarov wrote:

> JDT wrote:
>
>>It seems that using floats as the first tupelo for an STL map (shown
>>below) can cause problems but I don't remember what the problems were.
>
>
> The only thing I can think of is that if you expect two different
> results of a calculation to lead to the same number (and ultimately
> to the same stored in the map value), you may be in for a surprise.
> Due to rounding errors in the FPU the mathematically equivalent
> calculations can lead to different numbers internally.
>
> Example, given that 'a' is 1.f and 'b' is 2.f, the expressions
> (a + 2.f/3) and (b - 1.f/3) _can_ give you different results.
>
>
>>Is it common practice to use a structure like below? I would
>>appreciate if you can share your experience using such a structure.
>>Thanks.
>>std::map<float, int> m;
>
>
> I _never_ saw a 'map' where 'float' would be the Key type. I cannot
> claim to have seen all code in the world, and even a significant part
> of it, so I cannot attest to "commonality" of the practice.
>
> V

Hi Victor:

In the following scenario, I think using float as the key to a map makes
sense. For example, the following table needs to be sorted in the
ascending order of the 1st tuple (i.e. Values). So I can simply insert
the pairs into a map and then get a list of sorted pairs automatically.
Do people often have similar needs or are there other better ways to
accomplish this purpose? Any further help is much appreciated.

Values # of items
3.5 5
4.7 9
9.3 7
......

JD

JDT wrote:
> Victor Bazarov wrote:
>
>> JDT wrote:
>>
>>> It seems that using floats as the first tupelo for an STL map (shown
>>> below) can cause problems but I don't remember what the problems
>>> were.
>>
>>
>> The only thing I can think of is that if you expect two different
>> results of a calculation to lead to the same number (and ultimately
>> to the same stored in the map value), you may be in for a surprise.
>> Due to rounding errors in the FPU the mathematically equivalent
>> calculations can lead to different numbers internally.
>>
>> Example, given that 'a' is 1.f and 'b' is 2.f, the expressions
>> (a + 2.f/3) and (b - 1.f/3) _can_ give you different results.
>>
>>
>>> Is it common practice to use a structure like below? I would
>>> appreciate if you can share your experience using such a structure.
>>> Thanks.
>>> std::map<float, int> m;
>>
>>
>> I _never_ saw a 'map' where 'float' would be the Key type. I cannot
>> claim to have seen all code in the world, and even a significant part
>> of it, so I cannot attest to "commonality" of the practice.
>>
>> V
>
> Hi Victor:
>
> In the following scenario, I think using float as the key to a map
> makes sense. For example, the following table needs to be sorted in
> the ascending order of the 1st tuple (i.e. Values). So I can simply
> insert the pairs into a map and then get a list of sorted pairs
> automatically. Do people often have similar needs or are there other
> better ways to accomplish this purpose? Any further help is much
> appreciated.
> Values # of items
> 3.5 5
> 4.7 9
> 9.3 7
> .....

That's fine. Another way is to have a vector<pair<float,int> >, stuff
it with all the pairs you encounter, then sort them based on the pair's
'.first' member. You'd have better space economy that way. Of course,
in that case if you need to extract the correct order at any moment,
you'd have to sort right there (whereas 'std::map' always keeps them
sorted).

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

On 20 Apr, 22:33, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:

> That's fine. Another way is to have a vector<pair<float,int> >, stuff
> it with all the pairs you encounter, then sort them based on the pair's
> '.first' member. You'd have better space economy that way. Of course,
> in that case if you need to extract the correct order at any moment,
> you'd have to sort right there (whereas 'std::map' always keeps them
> sorted).


Uhm, I don't think it would be the best idea, because every time you
have to add a number you have to perform a search that is linear,
while the access to the map is logarithmic.

I think a good alternative would be to manually define the comparison
operator "less" considering that the equality

(a == b)

on a map is given by

!less(a,b) && !less(b,a)

it should be sufficient to write less() as something like


less(a, b){
if (a - b > threshold)
return false;
else
return true;
}

with threshold a proper small number. Sry for the loose syntax

you should then use map<double, unsigned, less>.

Regards,

Zeppe

On Apr 21, 12:36 am, zeppethef...@gmail.com wrote:
> On 20 Apr, 22:33, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:

> > That's fine. Another way is to have a vector<pair<float,int> >, stuff
> > it with all the pairs you encounter, then sort them based on the pair's
> > '.first' member. You'd have better space economy that way. Of course,
> > in that case if you need to extract the correct order at any moment,
> > you'd have to sort right there (whereas 'std::map' always keeps them
> > sorted).

> Uhm, I don't think it would be the best idea, because every time you
> have to add a number you have to perform a search that is linear,
> while the access to the map is logarithmic.

Why would the search have to be linear? I've used lower_bounds
to keep a vector sorted on more than a few occasions.

But the real question concerns the actual use. I got the vague
impression that the ordering was only relevant once the
collection had been constructed. If that's the case, the best
solution is probably to just add the values to a vector, and
sort once at the end, when the vector is full. Otherwise, it
depends.

> I think a good alternative would be to manually define the comparison
> operator "less" considering that the equality

> (a == b)

> on a map is given by

> !less(a,b) && !less(b,a)

> it should be sufficient to write less() as something like

> less(a, b){
> if (a - b > threshold)
> return false;
> else
> return true;
> }

> with threshold a proper small number.

That's a nice way to get undefined behavior. Since such a
function doesn't define an ordering relationship (which must be
transitive), it doesn't meet the requirements for std::map or
std::set.

--
James Kanze (Gabi Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

On Fri, 20 Apr 2007 19:52:01 +0000, JDT wrote:

> Hi,
>
> It seems that using floats as the first tupelo for an STL map (shown
> below) can cause problems but I don't remember what the problems were.
> Is it common practice to use a structure like below? I would appreciate
> if you can share your experience using such a structure. Thanks.
>
> std::map<float, int> m;
>
> JD

I'd be interested in authoritative and intelligent input on this as well.
My understanding is that for a type to be a key for a map, it only need be
(sortable)..iow: it overloads the relational operators so that two values
of the same type can be compared.

As to how you generate your keys...well, that could pose a problem since
ieee floating point numbers are approximations of actual floating point
values.

float n=2.0f

is it stored internally as 2.0 or 1.9999999997?

A way around this would be to (box) the float key into its own class and
make your relational operators be inexact comparitors.

btw: I HAVE actually found uses for maps that have floating point keys. I
use them when doing histograms of numerical data.

On Apr 21, 12:12 am, JDT <jdt_yo...@yahoo.com> wrote:
> In the following scenario, I think using float as the key to a map makes
> sense. For example, the following table needs to be sorted in the
> ascending order of the 1st tuple (i.e. Values). So I can simply insert
> the pairs into a map and then get a list of sorted pairs automatically.
> Do people often have similar needs or are there other better ways to
> accomplish this purpose? Any further help is much appreciated.
>
> Values # of items
> 3.5 5
> 4.7 9
> 9.3 7
> .....

A safer approach that would solve some(but not all) of the problems
already discussed would be to insert a new key only if it's not close
enough to already existing ones, that is to the upper_bound() and its
previous iterator. Of course inserting with different order may result
in different keys(no with the clean numbers of your example). Do the
same when searching.
In other words don't use the convenient brackets [] use upper_bound()
instead.

James Kanze wrote:
> On Apr 21, 12:36 am, zeppethef...@gmail.com wrote:
>
>> I think a good alternative would be to manually define the comparison
>> operator "less" considering that the equality
>
>> (a == b)
>
>> on a map is given by
>
>> !less(a,b) && !less(b,a)
>
>> it should be sufficient to write less() as something like
>
>> less(a, b){
>> if (a - b > threshold)
>> return false;
>> else
>> return true;
>> }
>
>> with threshold a proper small number.
>
> That's a nice way to get undefined behavior. Since such a
> function doesn't define an ordering relationship (which must be
> transitive), it doesn't meet the requirements for std::map or
> std::set.
>

On the other hand, assuming a reasonable threshold (EPSILON), what's
wrong with:

less(float a, float b)
{
if (fabs(a - b) > EPSILON) // difference big enough to be
return a < b; // significant
else
return false; // elements are "equal"
}