using a float as the index in an STL map?

[Alf P. Steinbach]

* Greg Herlihy:

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.

 

[James Kanze]

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.

 

[Colander]

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]

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.