   hash of 3D vectors
  Well, i'm trying to implement such a hash (STL)of my own 3D vector structures:template <class T> struct vector3{   T x, y, z;   operator =(...){/*implementation goes here*/}   operator <(...){/*implementation goes here*/}}something like that... then I need a hash of 3D vectors such ashash<vector3<int>, vector3<int>> the_hash; vector3<int> a,b,c;a.x = a.y = a.z = 1;b.x = b.y = b.z = 0;c.x = 1;c.y = 2;c.z = 3;the_hash[a] = b; //[0,0,0] => [1,1,1]the_hash = c; //[1,1,1] => [1,2,3]Print(the_hash[a]); //prints [1,2,3]!Print(the_hash); //prints [1,2,3]!Print(the_hash[c]); //this hash is not defined and prints [1,2,3]!and , of course it does not work...I wonder if this is possible... maybe my operator= and operator< are the "key"?or how to overcome this problem?any hints?thanks[Edited by - VerMan on September 3, 2007 3:48:40 AM]
  It's very likely that your overloaded operators are the problem here. I don't know how your hash class compares keys (there is no std::hash class that I know of, so I'm assuming you made it), but I think it is imposing unseen constraints on your comparing operators.Can you show us your implementation of the less than operator?A trivial example, imagine your less-than operator simply compares the magnitudes. You can then have 2 vectors which are actually different but your comparison function marks them as the same.Furthermore, these containers are built for comparing "nice" keys (I don't know about this particular one, but it probably is). They will assume that (for example) if a < b and b < c, then a < c. You need to make a vector comparison operator that satisfies this constraint and others.I can't really test this, but you might have more luck comparing in this manner:template<class T>bool vector<T>::operator<(vector<T> const& other) {  if(x < other.x) return true;  if(x > other.x) return false;  if(y < other.y) return true;  if(y > other.y) return false;  if(z < other.z) return true;  if(z > other.z) return false;  return false;}and then defining other comparison operators in terms of < so that you don't duplicate too much code. Note that this won't necessarily perform well. It's best to try to find a container designed for this task.   ;  Thanks Mr Evil, I was using some hash STL of the extended STL libraries but now I'm using the Map class and it looks like this:template <class T> struct Vector3 {   T x;   T y;   T z;   bool operator<(const Vector3<T>& right) const   { return ( (this->x <= right.x) && (this->y <= right.y) && (this->z <= right.z) );   }}And it works the same, it does not work.Oh, maybe it's because I haven't implemented the [] operator so when I try to access one of the maps: the_map[v] the behavior is undefined.... ?   ;Quote:Original post by VerManAnd it works the same, it does not work.operator < is expected to be a total order on the equivalence classes created by operator == (which is thus assumed to be an equivalence relationship). Which yours isn't (you can't compare [1,0,0] and [0,0,1] as neither is greater than the other yet they are not equal). Check out lexicographical order, which is a typical total order on vectors. MrEvil has posted a correct implementation of that order.   ;  Thank you Victor, actually I want to test for inequality i don't care if one vector is less than the other, but if one vector is different than the other so I can have a different map but the STL map requires this operator<. I mean, even using Mr Evil implementations which according to the links you pointed out is how it should be implemented... uhmm I always have a [0,0,0] as a result. Maybe I should pack those values somehow and use a standard Map<int> instead of Map<Vector3<int>>  =(   ;  Also remember that you'll need some sort of epsilon values for your vectors, since floats have precision errors.   ;Quote:Original post by VerManactually I want to test for inequality i don't care if one vector is less than the other, but if one vector is different than the other so I can have a different map but the STL map requires this operator<.Yes, it does, in order to accelerate finding elements. With only equality and inequality, finding an element requires you to traverse the entire set of elements, which is slow if you have a lot. The alternative is hashing, which is a constant-time operation if the hashtable size is chosen appropriately. However, hashing is not yet supported widely (it's in TR1), though you can already use boost::hash if you wish.Quote:I mean, even using Mr Evil implementations which according to the links you pointed out is how it should be implemented... uhmm I always have a [0,0,0] as a result. Which code?   ;Quote:Which code?This one:template <class T> struct Vector3 {   T x;   T y;   T z;   bool operator<(const Vector3<T>& right) const   { if(this->x < right.x) return true; if(this->x > right.x) return false; if(this->y < right.y) return true; if(this->y > right.y) return false; if(this->z < right.z) return true; if(this->z > right.z) return false; return false;   }}And later using:std::map<Vector3<int>, Vector3<int>> the_map;Vector3<int> v1;Vector3<int> v2;v1.x=0; v1.y=0; v1.z=0;v2.x=1; v2.y=1; v2.z=1;the_map[v1] = v2;...printme(the_map[v1]); //expected result [1,1,1]//actual: [0,0,0];  oh my i'm such a moron... the problem was the printme function, I don't know why but thanks to Evil Steve that pointed out float numbers (i'm not using float... but wait my print function uses %f instead of %d!) so that's why I was getting always zeroes. So, for instance:std::cout << "[%d,%d,%d]", the_map[v1].x, the_map[v1].y, the_map[v1].z;prints [1,1,1]  but:std::cout << "[%f,%f,%f]", the_map[v1].x, the_map[v1].y, the_map[v1].z;was printing [0.00000, 0.00000, 0.00000]!   