Re: VC9: STL: hash_set/map : hash_compare without operator < ???

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

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
.

Relevant Pages

  • Re: OO Style with Ada Containers
    ... Can you convince me that Ada.Containers is closer to STL than to Java ... But the burden of proof is on you, to prove that the container library ... A generic algorithm in Ada would look something like: ... procedure Generic_Algorithm (C: Cursor); ...
    (comp.lang.ada)
  • Re: Ada Popularity: Comparison of Ada/Charles with C++ STL (and Perl)
    ... I fully agree that we need a container library inside ... Just like the STL did. ... > I think the STL killed off all the other container libraries because ... string::string (int value) ...
    (comp.lang.ada)
  • Re: Is there something basic that I have missed on the upgrade to VS2005?
    ... > I have quite a bit of legacy code that initialises stl containers ... > called I get a debug assertion in the stl code "ITERATOR LIST ... been invalidated (e.g. by modifying the underlying container). ...
    (microsoft.public.vc.stl)
  • Re: Iterators redux
    ... > I am referring to the sort of STL syntax quoted by Harris: ... Inheriting from STL container classes is generally frowned upon as ... In order to make the above loop work with your own container class, ... Depending on the kind of iterator, you may also want to provide ...
    (comp.object)
  • Re: Centering text vertically in label
    ... Perhaps you havel changed the Scalemode property of the container. ... Changing to Inch would yield such values.... ...
    (microsoft.public.vb.general.discussion)