Re: hash_map
On Jun 14, 5:27 am, "BobR" <removeBadB...@worldnet.att.net> wrote:
aaragon <alejandro.ara...@gmail.com> wrote in message ...
[...]
struct eqstr
{
bool operator()(const double& o, const double& p) const
{
return (o == p);
Comparing doubles for equality is most often bad [1].
Not really. Comparing doubles when you don't know what you're
doing is usually bad.
Compare to a range.
Rarely solves anything.
if( ( o + 0.0001 > p ) && ( o - 0.0001 < p ) ){ return true;}
return false;
Which isn't a legal comparison function for anything, since it
isn't transitive. To use double as a key in a hash table, you
need an equivalence relationship and a hash function which is
compatible with that equivalence relationship: a == b implies
hash(a) == hash(b).
Output the numbers using a stream with 'fixed' and a big
'precision', and see if they are (really/almost) equal (in the
limited output (rounding errors in stream output)).
And check how the hash function works. I've yet to find a good
portable way to hash doubles. (Non portably, you could probably
extract the exponent, sign and the mantissa as integer values,
and hash them as integer values. With special handling for 0,
so that +0.0 and -0.0 hash to the same value. And special
handling for infinities and NaN's---in some applications,
assertion failure would be an acceptable special handling in
such cases.)
Not sure this is your problem, but, it (==) should be fixed.
}
};
namespace __gnu_cxx{
Are you a GNU systems/compiler developer?
GNU currently provides a hash table similar to the one that will
be in the next version of the standard, and similar to the one
provided by most other compiler vendors. Since it isn't
standard (yet), they place it in a special namespace, to
indicate that it is a compiler specific extension. Obviously,
the name of this namespace must be in the implementation's
namespace. Thus the __.
The rules for using this namespace are exactly the same as for
using std. GNU authorizes users to explicitly specialize
templates which it contains on user defined types.
template<> struct hash<double> {
size_t operator()(double __x) const {
boost::hash<double> double_hash;
return double_hash(__x);
}
};
}
The question here is what double_hash does. (I'm not sure, but
Boost seems to adopt a strategy roughly like what I described
before, using frexp and ldexp to get at the integral values, and
ignoring the sign (to avoid problems due to +/- 0.0). So it
should be correct, except maybe for infinity and NaNs, but it
probably also is slow enough that an std::map would be faster.)
void lookup(const hash_map<double, pair<double,double> , hash<double>,
eqstr>& Map, const double number){
hash_map<double, pair<double,double> , hash<double>,
eqstr>::const_iterator it = Map.find(number);
cout << number << ": "
<< (it != Map.end() ? "present" : "not present")
<< endl;
}
int main(){
hash_map<double, pair<double,double> , hash<double>, eqstr> HashMap;
HashMap.insert(make_pair(0.1,make_pair(0.,0.5)));
lookup(HashMap,0.1);
lookup(HashMap,0.05);
}
aaragon@aaragon-laptop:~/Desktop$ ./a.out
0.1: present
0.05: not present
Now, the thing is that I can't map the value of 0.05 to the
same pair because my hashing function doesn't to this. Any
ideas???
I'm not sure what you're trying to do, but maybe rounding or
whatever should be done on the values before comparing or
calling the boost hash function. Or just comparing, using
std::map. Basically, etablish a canonical representation for
each equivalence category, and use it.
--
James Kanze (GABI Software, from CAI) 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