Re: VC9: STL: hash_set/map : hash_compare without operator < ???
mario semo wrote:
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.
mh. STL=Standard Template Library, isnt it?
It is.
i used Dinkumware's STL in the last 10 years, so i thought these are
equal.
No, you used Dinkumware's implementation of the C++ standard library. The
STL is really only the collection of containers, iterators and algorithms,
most of which have been incorporated into the C++ standard. It doesn't
include IOStreams but a rope class for large texts, for example. Also, the
two are only 99% compatible, there are small differences even in things
that exist in both.
Note: hash_map and hash_set are not in std:: anymore, but now are in
stdext:: namespace.
Right, since they are not yet part of the C++ standard, they shouldn't be
in 'std' (yet, that is...).
If two values have the same hash, the container must still be able to
tell them apart.
definitly, but therefore not an ordering relation is required. just an
equivalence relation would be necessary.
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'.
yes and no
first : i am not interested in a strong ordered set of elements. i am just
interested in a hash based mapping of elements.
I'm afraid hash_map won't let you do that. It makes some assumption (as per
documentation) about the means it is given for comparison and hashing. The
fact that you don't need the ordering is irrelevant, I'm afraid.
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
which of the relation rules are not fullfilled with my implementation?
irreflexive : yes, it is. (foreach(x): f(x,x)=false) is true.
antisymetric : yes. (forany (x,y with x!=y) f(x,y) or f(y,x) is false. )
is true
Stop, I think you're missing one thing here:
forany (x,y with x!=y) f(x,y) or f(y,x) is false.
forany (x,y with x!=y) f(x,y) or f(y,x) is true.
The point is that either x<y or y<x, i.e. one comparison must yield true
while the other must yield false, provided that the elements are not equal.
i still need an instantiation of less<> my type but my objects are not
compareable.
I'm afraid that this won't be easy then. There is one thing you could try
though, but I'm not really sure if it will work: just implement operator<
to always return false. This requires that the container can store multiple
elements that compare equal (effectively it makes all elements equal to the
container, so only hashing will be used). This presents the problem that
searching for an element will yield any element, because they all look
equal to the container, even if operator== says something different.
Good luck!
Uli
--
C++ FAQ: http://parashift.com/c++-faq-lite
Sator Laser GmbH
Gesch?ftsf?hrer: Thorsten F?cking, Amtsgericht Hamburg HR B62 932