Re: VC9: STL: hash_set/map : hash_compare without operator < ???
- From: Ulrich Eckhardt <eckhardt@xxxxxxxxxxxxxx>
- Date: Tue, 19 May 2009 12:37:00 +0200
mario semo wrote:
I try to implement a hash_set (hash_map - both) for a class which has no
ordering relation (operator < etc), but just has an operator== and !=.
in earlier STL versions the hash_set/map template has arguments for a
hash class and for an equal_to class.
FYI: You mean the C++ standard library, not the STL.
STL in VC9 does not have these arguments, but just has an hash_compare
which expects an instance of class less<Type>.
I do not expect an hash collection to sort the elements, it should just
store the elements based on an hash value and allow fast access.
If two values have the same hash, the container must still be able to tell
them apart. The hash containers primarily work with a hash to speed up
things but at the second level use normal comparisons to provide guarantees
that are not given by hashes.
i read the documentation and the docu says:
================================
In general, the elements need be merely less than comparable to establish
this order: so that, given any two elements, it may be determined either
that they are equivalent (in the sense that neither is less than the
other) or that one is less than the other. This results in an ordering
between the non-equivalent elements. On a more technical note, the
comparison function is a binary predicate that induces a strict weak
ordering in the standard mathematical sense. A binary predicate f(x,y) is
a function object that has two argument objects x and y and a return value
of true or false. An ordering imposed on a hash_set is a strict weak
ordering if the binary predicate is irreflexive, antisymmetric, and
transitive and if equivalence is transitive, where two objects x and y are
defined to be equivalent when both f(x,y) and f(y,x) are false. If the
stronger condition of equality between keys replaces that of equivalence,
then the ordering becomes total (in the sense that all the elements are
ordered with respect to each other) and the keys matched will be
indiscernible from each other. =================================
Do i understand the documentation correctly in the sense, that it is ok to
implement template less<T> simple by returning a!=b ?
No. You can not derive an ordering from the existing comparison operators.
You could do the reverse though, because '!(a<b) and !(b<a)'
implies 'a==b'.
class my_hash_compare
: public hash_compare<A,less<A>>
{
......
bool operator()(const A& _Keyval1, const A& _Keyval2) const
{
// ?????????
return _Keyval1 != _Keyval2;
}
Is this correct?
No, see above. In addition you are not allowed to use names like _Keyval,
those are reserved.
what happens with this less<A> which i pass as argument? i do not have an
operator < for objects of type A so how is this less<A> be instantiated?
std::less<T> per default uses operator<. You can therefore simply provide
operator< to make std::less work as is. Alternatively, if T is not a type
where a less-than comparison makes sense, you can provide a functor like
std::less, though the hash_compare interface requires some additional
things, if I understand correctly.
Suggestion: as a first step, use std::set or std::map instead of hash_set or
hash_map. If you manage to provide a suitable comparator to those (and it
is easier to locate good examples on the web), adapting them to the hash
containers will be a breeze.
class my_hash_compare
: public hash_compare<A,less<A>>
{
public:
size_t operator()(const A & _Keyval) const
{
int v = _Keyval.val;
return hash_value(v);
}
bool operator()(const A& _Keyval1, const A& _Keyval2) const
{
// ?????????
return _Keyval1 != _Keyval2;
return _Keyval1.val < _Keyval2.val;
}
};
Uli
--
C++ FAQ: http://parashift.com/c++-faq-lite
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932
.
- Follow-Ups:
- Re: VC9: STL: hash_set/map : hash_compare without operator < ???
- From: mario semo
- Re: VC9: STL: hash_set/map : hash_compare without operator < ???
- References:
- VC9: STL: hash_set/map : hash_compare without operator < ???
- From: mario semo
- VC9: STL: hash_set/map : hash_compare without operator < ???
- Prev by Date: VC9: STL: hash_set/map : hash_compare without operator < ???
- Next by Date: Re: VC9: STL: hash_set/map : hash_compare without operator < ???
- Previous by thread: VC9: STL: hash_set/map : hash_compare without operator < ???
- Next by thread: Re: VC9: STL: hash_set/map : hash_compare without operator < ???
- Index(es):
Relevant Pages
|
