By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,205 Members | 1,075 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,205 IT Pros & Developers. It's quick & easy.

using a float as the index in an STL map?

P: n/a
JDT
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, intm;

JD
Apr 20 '07 #1
Share this Question
Share on Google+
23 Replies


P: n/a
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, intm;
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
Apr 20 '07 #2

P: n/a
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.
Apr 20 '07 #3

P: n/a
JDT
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, intm;


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


Apr 20 '07 #4

P: n/a
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, intm;


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
Apr 20 '07 #5

P: n/a
On 20 Apr, 22:33, "Victor Bazarov" <v.Abaza...@comAcast.netwrote:
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
Apr 20 '07 #6

P: n/a
On Apr 21, 12:36 am, zeppethef...@gmail.com wrote:
On 20 Apr, 22:33, "Victor Bazarov" <v.Abaza...@comAcast.netwrote:
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: ja*********@gmail.com
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

Apr 20 '07 #7

P: n/a
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, intm;

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.
Apr 20 '07 #8

P: n/a
On Apr 21, 12:12 am, JDT <jdt_yo...@yahoo.comwrote:
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.
Apr 20 '07 #9

P: n/a
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"
}
Apr 21 '07 #10

P: n/a
On Apr 21, 4:07 am, red floyd <no.s...@here.dudewrote:
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"

}
Say you have already the keys 1.,2. and EPSILON =1.
Which key is this solution guaranteed to return when searching whith
1.1?

Apr 21 '07 #11

P: n/a
On Apr 21, 3:07 am, red floyd <no.s...@here.dudewrote:
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"
}
What have you changed? You still haven't defined a strict
ordering relationship, so you have undefined behavior.

--
James Kanze (Gabi Software) email: ja*********@gmail.com
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

Apr 21 '07 #12

P: n/a
On Apr 21, 1:43 am, kostas <skola...@gmail.comwrote:
On Apr 21, 12:12 am, JDT <jdt_yo...@yahoo.comwrote:
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
Excuse me, but without knowing the source of his values, how can
you say that it is 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.
I can't think off hand of a case where that would be
appropriate, but there probably exists one. A more likely
solution would be to round the keys before insertion. In a lot
of cases (most, I suspect, if one knows what one is doing),
there isn't a problem.

--
James Kanze (Gabi Software) email: ja*********@gmail.com
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

Apr 21 '07 #13

P: n/a
On Apr 21, 1:31 am, Rae Westwood <boomchuggapow...@badjazzmusic.com>
wrote:
On Fri, 20 Apr 2007 19:52:01 +0000, 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.
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, intm;
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.
The term used by the standard is that there must be a comparison
function which "induces a strict weak ordering on the values".
The standard then specifies what it means by a strict weak
ordering:

The term strict refers to the requirement of an irreflexive
relation (!comp (x, x) for all x), and the term weak to
requirements that are not as strong as those for a total
ordering, but stronger than those for a partial ordering. If
we define equiv(a, b) as !comp (a, b) && !comp (b, a), then
the requirements are that comp and equiv both be transitive
relations:

-- comp (a, b) && comp (b, c) implies comp (a, c)

-- equiv(a, b) && equiv(b, c) implies equiv(a, c)
[Note: Under these conditions, it can be shown that

. equiv is an equivalence relation

. comp induces a well-defined relation on the
equivalence classes determined by equiv

. The induced relation is a strict total ordering.
-- end note ]
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.
Not really. Floating point numbers are exact
representations of floating point numbers. In many
applications, floating point numbers are used to model real
numbers; the approximation there is not very exact (and many
of the rules of real arithmetic do not hold).
float n=2.0f
is it stored internally as 2.0 or 1.9999999997?
Neither. It's stored internally as 0x40000000. Required by
the IEEE standard. As it happens, this value represents the
real number 2.0 exactly---you picked a very bad example:-).

The problem is, of course, that floating point can only
represent a very small subset of the real numbers, and a
non-contiguous subset at that. (int can only represent a
very small subset of the integers, but it is a contiguous
subset.) And that while precisely defined by IEEE, floating
point arithmetic doesn't follow some of the expected
rules---addition is not associative, for example---and
often doesn't give the same results as the same operation
in real arithmetic. And of course, the fact that we enter
floating point constants in the form of decimal numbers, and
that the values we "see" often aren't present in the set of
values representable in floating point.
A way around this would be to (box) the float key into its own class and
make your relational operators be inexact comparitors.
See above. I suspect that most naïve inexact comparitors
would fail to define a strick weak ordering.
btw: I HAVE actually found uses for maps that have floating point keys. I
use them when doing histograms of numerical data.
Just guessing, but in such cases, you would define
equivalences classes over ranges of floating point values,
no? Something along the lines of:

struct FPCmp
{
bool operator()( double a, double b ) const
{
return floor( 100.0 * a ) < floor( 100.0 * b ) ;
}
} ;

(In such cases, I'd probably use a canonic representation of
each equivalence class as the key, i.e. floor(100.0 *
value), in the above example.)

--
James Kanze (Gabi Software) email: ja*********@gmail.com
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

Apr 21 '07 #14

P: n/a
On Apr 21, 1:02 pm, James Kanze <james.ka...@gmail.comwrote:
I can't think off hand of a case where that would be
appropriate, but there probably exists one. A more likely
solution would be to round the keys before insertion. In a lot
of cases (most, I suspect, if one knows what one is doing),
there isn't a problem.
Round to what you forgot to say. I think that whatever rounding scheme
you choose, there is the possibility that slight different values will
round to different keys. Say you have chosen to round to units and
your input is 1.4 and 1.6(not to say 1.499... , 1.50...1). I suspect
that the first will round to 1. and the second to 2. You can say that
my proposal was a round to already existing values.

I had also taken my precautions.
Apr 21 '07 #15

P: n/a
James Kanze wrote:
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.
oh gosh, my bad! :)

Regards,

Zeppe
Apr 21 '07 #16

P: n/a
On Apr 21, 2:56 pm, kostas <skola...@gmail.comwrote:
On Apr 21, 1:02 pm, James Kanze <james.ka...@gmail.comwrote:
I can't think off hand of a case where that would be
appropriate, but there probably exists one. A more likely
solution would be to round the keys before insertion. In a lot
of cases (most, I suspect, if one knows what one is doing),
there isn't a problem.
Round to what you forgot to say. I think that whatever rounding scheme
you choose, there is the possibility that slight different values will
round to different keys.
Certainly. That's why you have rules for rounding.
Say you have chosen to round to units and
your input is 1.4 and 1.6(not to say 1.499... , 1.50...1). I suspect
that the first will round to 1. and the second to 2. You can say that
my proposal was a round to already existing values.
It's not rounding in the classical sense, although as you say,
in some ways, it works like it. The reason I say that I can't
think of a case off hand for it is precisely that the choice of
the central value is more or less random. I'm also not too sure
if it will work; there's certainly no way to write a Compare
operator which reflects it.

--
James Kanze (Gabi Software) email: ja*********@gmail.com
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

Apr 22 '07 #17

P: n/a
Maybe just use a class which represents fractions and use that instead
of floats

Apr 22 '07 #18

P: n/a
On Apr 22, 12:02 pm, James Kanze <james.ka...@gmail.comwrote:
It's not rounding in the classical sense, although as you say,
in some ways, it works like it. The reason I say that I can't
think of a case off hand for it is precisely that the choice of
the central value is more or less random.
Probably there are cases that it's not so important that the map will
end up having the same keys regardless of the insertion order (which
is the main advantage of an arbitrary rounding method as far as i can
see) but that these keys will be closer to the given ones(actually
will be some of them). To continue my simple example either 1.49... or
1.50...1 may be better that 1. or 2. Then, you would probably think ,
it may next come 1.1 which i would be forced to round to some of the
above values while rounding to unit is better. It may come, it may
not. If you already know, use your rounding scheme. Furthermore there
are some interesting cases that this will not happen. Consider for
example an algorithm that produces some values quite far apart one
from the other(in theory) but with some fluctuations due to numerical
calculations(in practice) that you would like to filter out. Why you
should introduce in this case some extra arbitrary rounding
error(rounding guess, if you prefer) ?
Apr 22 '07 #19

P: n/a
On Apr 21, 2:51 am, James Kanze <james.ka...@gmail.comwrote:
On Apr 21, 3:07 am, red floyd <no.s...@here.dudewrote:
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"
}

What have you changed? You still haven't defined a strict
ordering relationship, so you have undefined behavior.
There is no undefined behavior. The less() function does produce a
total ordering:

For any a, b, and c such that less(a, b) returns true and less(b, c)
returns true, then it is the case that less( a, c) also returns true.

Greg
Apr 23 '07 #20

P: n/a
* Greg Herlihy:
On Apr 21, 2:51 am, James Kanze <james.ka...@gmail.comwrote:
>On Apr 21, 3:07 am, red floyd <no.s...@here.dudewrote:
>>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"
}
What have you changed? You still haven't defined a strict
ordering relationship, so you have undefined behavior.

There is no undefined behavior. The less() function does produce a
total ordering:

For any a, b, and c such that less(a, b) returns true and less(b, c)
returns true, then it is the case that less( a, c) also returns true.
For a std::map the 'less' operation must define a strict weak ordering.

"Strict" means that !(a op a) holds for all a. This is true of the
'less' above.

Exactly what "weak" means I'm not sure, but the standard's requirement
(in §25.3/4) is that 'less' should define an equivalence relation, via

bool eq(a,b) { return !less(a,b) && !less(b,a); }

which must be transitive,

eq(a,b) && eq(b,c) implies eq(a,c)

This requirement is not met for the 'less' above.

You can have (a,b) such that their difference is less than EPSILON, and
(b,c) such that their difference is less than EPSILON, but such that the
difference for (a,c) is greater than EPSILON.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Apr 23 '07 #21

P: n/a
On Apr 23, 4:37 am, Greg Herlihy <gre...@pacbell.netwrote:
On Apr 21, 2:51 am, James Kanze <james.ka...@gmail.comwrote:
On Apr 21, 3:07 am, red floyd <no.s...@here.dudewrote:
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"
}
What have you changed? You still haven't defined a strict
ordering relationship, so you have undefined behavior.
There is no undefined behavior. The less() function does produce a
total ordering:
For any a, b, and c such that less(a, b) returns true and less(b, c)
returns true, then it is the case that less( a, c) also returns true.
So? The standard requires a "strict weak ordering". I'm not
too sure what that means mathematically, but the standard
explicitly defines what it means. In particular, it defines
"equiv(a, b)" as "!comp(a, b) && !comp(b, a)", and requires that
equiv define an equivalence relationship. That doesn't hold
for the above function, so the constraints are not met for the
relationship, and undefined behavior results.

Note that it's very easy to end up with undefined behavior
because of this where floating point is involved. But then,
it's very easy to end up with wrong results in general where
floating point is involved. Writing correct floating point code
requires knowing what you are doing, not just stabbing in the
dark and playing around with espilons or avoiding == or
whatever.

--
James Kanze (GABI Software) email:ja*********@gmail.com
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

Apr 23 '07 #22

P: n/a
On Apr 21, 3:07 am, red floyd <no.s...@here.dudewrote:
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"

}
What's wrong is that EPSILON is relative to a and b.

Floats are very hard if not impossible to deal with in an exact
manner. Once I wrote a class with a fixed number of post . digits, I'm
not happy with that either, <1>1.0 + <2>0.04 + <2>0.04, can be both
<1>1.0 and <1>1.1 depending on the binding order of the + operator
losing it's associativity :-(.

Has anyone come up with a all situations solution for float like
numbers? I find myself writing custom code very often in that
corner....

Bas

Apr 23 '07 #23

P: n/a
On Apr 23, 9:00 pm, Colander <colan...@gmail.comwrote:
On Apr 21, 3:07 am, red floyd <no.s...@here.dudewrote:
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"
}
What's wrong is that EPSILON is relative to a and b.
What's wrong is that it doesn't define a "strict weak ordering",
as defined in and required by the standard. Using a relative
epsilon won't change that.

--
James Kanze (GABI Software) email:ja*********@gmail.com
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

Apr 24 '07 #24

This discussion thread is closed

Replies have been disabled for this discussion.