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

# 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?

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

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

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