Re: using a float as the index in an STL map?
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, int> m;
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=EFve 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: james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34