Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > using a float as the index in an STL map?

Reply
Thread Tools

using a float as the index in an STL map?

 
 
Alf P. Steinbach
Guest
Posts: n/a
 
      04-23-2007
* Greg Herlihy:
> On Apr 21, 2:51 am, James Kanze <(E-Mail Removed)> wrote:
>> On Apr 21, 3:07 am, red floyd <(E-Mail Removed)> wrote:
>>> James Kanze wrote:
>>>> On Apr 21, 12:36 am, (E-Mail Removed) 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?
 
Reply With Quote
 
 
 
 
James Kanze
Guest
Posts: n/a
 
      04-23-2007
On Apr 23, 4:37 am, Greg Herlihy <(E-Mail Removed)> wrote:
> On Apr 21, 2:51 am, James Kanze <(E-Mail Removed)> wrote:


> > On Apr 21, 3:07 am, red floyd <(E-Mail Removed)> wrote:


> > > James Kanze wrote:
> > > > On Apr 21, 12:36 am, (E-Mail Removed) 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:(E-Mail Removed)
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

 
Reply With Quote
 
 
 
 
Colander
Guest
Posts: n/a
 
      04-23-2007
On Apr 21, 3:07 am, red floyd <(E-Mail Removed)> wrote:
> James Kanze wrote:
> > On Apr 21, 12:36 am, (E-Mail Removed) 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

 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      04-24-2007
On Apr 23, 9:00 pm, Colander <(E-Mail Removed)> wrote:
> On Apr 21, 3:07 am, red floyd <(E-Mail Removed)> wrote:
> > James Kanze wrote:
> > > On Apr 21, 12:36 am, (E-Mail Removed) 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:(E-Mail Removed)
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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
float to string to float, with first float == second float Carsten Fuchs C++ 45 10-08-2009 09:47 AM
sorting index-15, index-9, index-110 "the human way"? Tomasz Chmielewski Perl Misc 4 03-04-2008 05:01 PM
Float to int conversion by using two int variables for representation of the float variable k3n3dy C++ 15 04-20-2006 06:53 PM
need code to convert float format to internal java float format which is kept in 4 bytes integer Andy Java 7 05-10-2004 09:26 PM
Re: float->byte->float is same with original float image. why float->ubyte->float is different??? bd C Programming 0 07-07-2003 12:09 AM



Advertisments