Sign in to follow this  
griffin2000

STL question - Adding a tolerance to a map comparison opertor

Recommended Posts

I have a set of verts like this...
vector<MyVertex>  mVerts;
map<MyVertex,int> mVertexMap;
I can add to my array like this (as MyVertex has < operator defined):
	MyVertex newVert=...;
	map<MyVertex, int>::iterator mapIter=mVertexMap.find(newVert);
	if(mapIter==mVertexMap.end())
	{
		agtUInt32 ind=mVerts.size();
		mVerts.push_back(newVert);
		mVertexMap[newVert]=ind;
		return ind;
	}

	return mapIter->second;
And it works but now I want introduce a tolerance value so if two verts are similar but different they will get combined. How would I do this in STL ? I can add a comparison functor like this:
map<MyVertex,int, MyVertexComp> mVertexMap;
But how do pass in the tolerance ? My first thought was to make it a template parameter to the MyVertexComp class but this doesn't compile (and even if it did, forcing it to be a compile-time value would be nasty). I could make it a static variable in MyVertexComp but this also seems nasty. Is there a neater way ?

Share this post


Link to post
Share on other sites
Whatever you do, don't use a "fuzzy" comparison operator. The std::map requires a comparison operator with certain guarantees, among them that comp(a,b)==true implies comp(b,a)==false. Adding a tolerance value breaks that requirement, and can do all manner of inappropriate things to your map.

Generally, for this sort of thing you'll want a spatial data structure such as a kD-tree, not a std::map.

Share this post


Link to post
Share on other sites
A fuzzy comparison will 'work', yes, but it will mean the map stays in an unpredictable order. And, multiple keys could end up refering to the same element. Imagine you use integers, with a 'tolerance' of 5. Once you add the element '5' into the map, everytime you ask for an element between 0 and 10, you will get that 5. You can't even add anything else in that range, because insert will just replace the one it thinks the new value is equal to - the 5.

However, multimap/multiset could handle it, but the container probably wouldn't be sorted properly, and that could cause all sorts of trouble.

You might consider writing your own custom fuzy search function. I can think of a fairly niave, but functional solution, assuming it's a map of integers.


std::map<int,int> the_map;
//assume the_map has stuff in it...
typedef std::map<int,int>::iterator iterator;

iterator fuzzy_find(int what, int tolerance)
{
iterator I = the_map.find(what);
if (I != the_map.end()) return I; //Exact match!

the_map[what] = 0; //creates 'what' in map
I = the_map.find(what); //we just added it - this can't return end().

//Note that I am ignoring the case where I == begin() or ++I == end().
// Don't forget to account for those special cases!
iterator lower = I; --lower; //closest element smaller than what
iterator higher = I; ++higher; //closest element higher than what

int dif_lower = abs(I->first - lower->first); //difference between what and lower
int dif_higher = abd(I->first - higher->first); //difference between what and higher

the_map.erase(I); //removes 'what' from map

//favors lower when dif_lower == dif_higher,
if (dif_lower <= dif_higher && dif_lower <= tolerance) return lower;
if (dif_lower > dif_higher && dif_higher <= tolerance) return higher;

return the_map.end(); //no value within tolerance
}






Share this post


Link to post
Share on other sites
Quote:
Original post by griffin2000
But how do pass in the tolerance ? My first thought was to make it a template parameter to the MyVertexComp class but this doesn't compile (and even if it did, forcing it to be a compile-time value would be nasty). I could make it a static variable in MyVertexComp but this also seems nasty. Is there a neater way ?


Now that you have been told it is a bad idea, here's the answer to your technical question: you can pass a comparator object to std::map's constructor.

Share this post


Link to post
Share on other sites
I had a similar problem last week with this. I was prting VC6 code to VC8 (at last!) and some old code was using operator <= to put things in a set, which VC8 was moaning about (with good reason) while I was trying to debug some other crash problem in debug mode.

Basically, you can put "fuzzy" values in a map/set, but you can't rely on finding the right element, but it did work iterating through the elements. Needless to say, I had to implement operator< for the set properly in the end and curse the original coder (who has long since gone).

Share this post


Link to post
Share on other sites
Quote:
Original post by Deyja
A fuzzy comparison will 'work', yes, but it will mean the map stays in an unpredictable order. And, multiple keys could end up refering to the same element. Imagine you use integers, with a 'tolerance' of 5. Once you add the element '5' into the map, everytime you ask for an element between 0 and 10, you will get that 5. You can't even add anything else in that range, because insert will just replace the one it thinks the new value is equal to - the 5.


Ahhh but it will still be safe in this case... As the before I add to the map I check to see if there is another node in there. So if '5' is in there then '6' will not get added...

However it looks like .net 2005 will explitally assert if the comparison operator does not meet that criteria. Which is irritating, we have a C void* based red-black tree in our API, I guess I'll use that.



Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this