mario semo

2009-05-19 09:59:15 UTC

Permalink

Raw Message

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.

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.

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 ?

i have some problems in the understanding on "antisymetric" :

"Antisymetric of a relation R on a set S, having the property that for any

two distinct elements of S, at least one is not related to the other via R."

(Wiki)

What does this mean in respect to my implementation of template less ?

below i give a small sample. is this correct?

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?

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?

Here is the complete sample:

#include <stdio.h>

#include <hash_set>

#include <hash_map>

using namespace stdext;

using namespace std;

class A

{

public:

A(int p=0) : val(p){}

virtual ~A() {};

bool operator==(A const &x) const {return val==x.val;}

bool operator!=(A const &x) const {return val!=x.val;}

void dump()

{

printf("...%p...%d...\n",this,val);

}

// assume not available!

#if 0

friend bool operator < ( const A &string1,const A &string2 )

{

return string1.val < string2.val;

}

#endif

int val;

};

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;

}

};

int main(int argc,char *argv[])

{

A aA(123);

A aB(456);

A aC(99);

typedef hash_set<A,my_hash_compare > HashSet2;

HashSet2 inthashset2;

inthashset2.insert(aC);

inthashset2.insert(aB);

inthashset2.insert(aA);

HashSet2::iterator lCursor2;

HashSet2::iterator lEnd2 = inthashset2.end();

for (lCursor2 = inthashset2.begin();lCursor2!=lEnd2;lCursor2++)

{

(*lCursor2).dump();

}

return 0;

}

cl -W4 -nologo -D__WINDOWS__ -DIC_WIN -D_USE_32BIT_TIME_T /J /EHa

hash_coll1.cpp user32.lib

--

mit freundlichen Grüßen

mario semo

mit freundlichen Grüßen

mario semo