lbertacco
asked on
STL hash_set with vector as key
I need to create an hash_set that has a vector<bool> as the key. This should work under MS VC7.1 and possibly also gcc3.2.
The idea is something like:
class ptHash {
public:
size_t operator()(const vector<double> & pt) {
size_t h=0;
for(vector<double>::size_t
h ^= hash(pt[i]);
}
}
};
hash_set<vector<double>, ptHash > history;
but this is ofcourse incomplete.
MSVC7.1 seems to expect a "traits" class rather than a hash function object so it complains about:
...include\xhash(164): error C2039: 'bucket_size' : is not a member of 'ptHash'
...include\xhash(165): error C2039: 'min_buckets' : is not a member of 'ptHash'
...
I didn't test with STLport but that seems to really expect a hash function object. Are the 2 STL implementations incompatible?
If this can help, all the vector<double> that will be inserted in the hash_set will be of the same size.
P.S. BTW where can I find documentation for the STLport hash_set/map/... ? The Stlport documentation seems to describe only how to download/build the library, doesn't talk about the templates/objects it imlements !?! The C++ Standard Library book by Addison Wesley doesn't talk about hash_* since they are not part of the standard.
The idea is something like:
class ptHash {
public:
size_t operator()(const vector<double> & pt) {
size_t h=0;
for(vector<double>::size_t
h ^= hash(pt[i]);
}
}
};
hash_set<vector<double>, ptHash > history;
but this is ofcourse incomplete.
MSVC7.1 seems to expect a "traits" class rather than a hash function object so it complains about:
...include\xhash(164): error C2039: 'bucket_size' : is not a member of 'ptHash'
...include\xhash(165): error C2039: 'min_buckets' : is not a member of 'ptHash'
...
I didn't test with STLport but that seems to really expect a hash function object. Are the 2 STL implementations incompatible?
If this can help, all the vector<double> that will be inserted in the hash_set will be of the same size.
P.S. BTW where can I find documentation for the STLport hash_set/map/... ? The Stlport documentation seems to describe only how to download/build the library, doesn't talk about the templates/objects it imlements !?! The C++ Standard Library book by Addison Wesley doesn't talk about hash_* since they are not part of the standard.
There is very limited use for a bool vector as a hash key. You can easily convert it to an uint32_t for up to 32 elements, or even uint64_t. Or do you expect more than that? Do you want to implement something like a search engine?
In any case, if you need a flexible size hash key, you could still create bit strings out of you bools.
In any case, if you need a flexible size hash key, you could still create bit strings out of you bools.
ASKER
sorry, a typo. The hash_set must be of vector<double> as specified in the "pseudo" code, not vector<bool>.
Size of the vector will be in the order of 100 to 50000 elements.
Size of the vector will be in the order of 100 to 50000 elements.
ASKER
the http://www.cppreference.com doesn't seem to cover the hash_set template to me.
lbertacco,
You're right. It only covers the map and multimap types. hash_set is deprecated. I remember it was quite complicated to use.
You cannot really use doubles as hash keys, as doubles are not exact - if you want to test two of them for equality, you must do something like
bool equal = fabs(double1 - double2) <= epsilon;
This rules out hashing.
However, if you know for sure that your values are within a certain range, you can use fixedpoint arithmetics (like using mantissa only) - and this could be used for hashing.
Stefan
You're right. It only covers the map and multimap types. hash_set is deprecated. I remember it was quite complicated to use.
You cannot really use doubles as hash keys, as doubles are not exact - if you want to test two of them for equality, you must do something like
bool equal = fabs(double1 - double2) <= epsilon;
This rules out hashing.
However, if you know for sure that your values are within a certain range, you can use fixedpoint arithmetics (like using mantissa only) - and this could be used for hashing.
Stefan
lbertacco,
A nice reference for IEEE floating points and how to convert them will be
http://babbage.cs.qc.edu/courses/cs341/IEEE-754.html
Stefan
A nice reference for IEEE floating points and how to convert them will be
http://babbage.cs.qc.edu/courses/cs341/IEEE-754.html
Stefan
ASKER
Stefan73, you are right that in general you shouldn't hash on dobules, but in my case the doubles are already rounded or anyway snapped to certain values. So it's fine for me to compare them exactly.
Also hash_set is not deprecated (where did you find this?), it's just not standardized.
Anyway I've found the solution myself, here it is:
template<class _T>
class hash_compare_for_vectors {
private:
typedef vector<_T> Key;
hash_compare<_T > THC;
public:
static const size_t bucket_size = 4;
static const size_t min_buckets = 8;
size_t operator()(const Key & k) const {
size_t h=0;
for(Key::size_type i=0; i<k.size(); i++) h ^= THC(k[i]);
return h;
};
bool operator( )(const Key & k1, const Key & k2) const {
if(k1.size()!=k2.size()) return true;
for(Key::size_type i=0; i<k1.size(); i++) {
if(THC(k1[i], k2[i])) return true;
}
return false;
};
};
hash_set<vector<double>, hash_compare_for_vectors<d
--------------
Maybe the compare operator can be improved if vectors can be compared directly (?)
Also hash_set is not deprecated (where did you find this?), it's just not standardized.
Anyway I've found the solution myself, here it is:
template<class _T>
class hash_compare_for_vectors {
private:
typedef vector<_T> Key;
hash_compare<_T > THC;
public:
static const size_t bucket_size = 4;
static const size_t min_buckets = 8;
size_t operator()(const Key & k) const {
size_t h=0;
for(Key::size_type i=0; i<k.size(); i++) h ^= THC(k[i]);
return h;
};
bool operator( )(const Key & k1, const Key & k2) const {
if(k1.size()!=k2.size()) return true;
for(Key::size_type i=0; i<k1.size(); i++) {
if(THC(k1[i], k2[i])) return true;
}
return false;
};
};
hash_set<vector<double>, hash_compare_for_vectors<d
--------------
Maybe the compare operator can be improved if vectors can be compared directly (?)
>Also hash_set is not deprecated (where did you find this?), it's just not standardized.
AFAIK it was left out of the standard in favour of map/multimap.
AFAIK it was left out of the standard in favour of map/multimap.
ASKER
It has been left out just because of late submission. It's not that one is better than the other. Simply one uses red-black trees and the other uses hash tables. Both have pros and versus, but in many cases hash tables are more performant than bal-trees.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Have a look at http://www.cppreference.com
Cheers,
Stefan