Archived

This topic is now archived and is closed to further replies.

gimp

[STL] map.find doesn't work with my class?

Recommended Posts

I''ve just been stumpted by a weird(to me) problem where I think stl isn''t doing what I think it should. Basically I have a user defined class as the key in a map. When I do a find it seems to find things that arn''t in the map?
  
std::map<CVector3, unsigned short>::const_iterator itr = a_VertexDirectory.find(a_Triangle.Points[i]);
  
The idea here is that the map should tell me if that vertex is already in use and what index I should use to access it. On the first insertion:
  
a_VertexDirectory.insert(std::pair<CVector3, unsigned short>(a_Triangle.Points[i], CurrentIndex));
  
...alls well. The I process the next pass with the next(different) Vertex. This time the find doesn''t return a_VertexDirectory.end(), it returns an iterator to the previously added(and different) vertex. I''ve also toyed with the comparison function it uses. I''ve tried it as a member function and as a normal function. No difference.
  
inline bool operator < (const CVector3& a_First, const CVector3& a_Second)
{
    return (a_First.x < a_Second.x && a_First.y < a_Second.y && a_First.z < a_Second.z);
}
  
...which looks ok compared to other classes which appear to work fine. Any idea''s? Chris Brodie http:\\fourth.flipcode.com

Share this post


Link to post
Share on other sites
I think the problem is your operator<. For the STL containers (map, set) to work properly, it needs to be defined such that if (a < b) is true, then (b < a) cannot. This part is OK. However, it also assumes (I think) that if (a < b) is false, and so is (b < a), then the two are equal.

In this case, given example values of (1, 2, 3) and (3, 2, 1) for two vectors, both comparisons will return false, and so the map will assume that they are equal.

So, rewrite your operator< function. I suggest:


  
bool operator<(const CVector3& lhs, const CVector3& rhs)
{
return (lhs.x < rhs.x ||
(lhs.x==rhs.x && lhs.y<rhs.y ) ||
(lhs.x==rhs.x && lhs.y==rhs.y && lhs.z<rhs.z )
);
}

Share this post


Link to post
Share on other sites
I have no idea if it is the problem or not, but it seems strange that !(V1 < V2) && !(V2 < V1) can be true without them being equal (if V1 has 1 coordinate greater than V2''s the first < test will fail, and if V2 has 1 coordinate greater than V1''s, the second one will). You might need to define an operator == as well so the map knows when it found the right one.

Share this post


Link to post
Share on other sites
I know you weren''t asking but part of the problem for me is difficulty in reading the code. I''d simplify it so that there is less to look at


  
//I''d use a few typedefs:

typedef std::map<CVector3, unsigned short> VertexDirectory;
typedef VertexDirectory::iterator VertexDirectoryIter;
// I''d also change the name to ''a_directory'' as you know from

// its type that it is a directory of vertices.

// Then you can have the following

VertexDirectoryIter itr = a_directory.find(a_Triangle.Points[i]);

// also use make_pair which works out the correct kind of

// pair to make from the types that you pass it

a_directory.insert(make_pair(a_Triangle.Points[i], CurrentIndex));

Share this post


Link to post
Share on other sites
Thanks All!

It''s 2am here in Sydney and I can still get help. Thanks tr0n and guys for the information. The problems is now solved with your help.

The problem was indeed the < operator. I had been reading my STL book and the aweful msdn doco to solve the problem but non of what I read mentioned how the comparison operator was actually used.

Tr0n you''ll be happy to know that your sample worked as a drop in replacement for my code.

Chris Brodie
http:\\fourth.flipcode.com

Share this post


Link to post
Share on other sites