🔒 Locked

std::map with my own less function

Started by floriang Oct 26, 2005 at 12:50 AM 3 replies 900+ views

Original Post

Oct 26, 2005 at 12:50 AM

I'm having a bit of trouble here: I'd like to create a hashtable (std::map), mapping a bunch of points (meaning a structure tPoint3Df with 3 coordinates, x, y and z) to some arbitrary object pointer, in my case a vector object. I've worked a lot with maps before, taking object pointers, ints, float, etc. for my map keys, but never a structure of my own. My typedef looks as follows: typedef map pointVectorMap; here's the question: how must my point3DfLess function be implemented? I currently have an implementation, working on the length of the point (absolute value of square root of square coordinates), which I assume incorrect because the find() function does not work properly. In my case, it seems like the vector I get returned is independent of the key-point's z value. I assume that is because the length is not enough of a property to say one point is "less" than another, makes sense. I just can't figure out another solution at the moment. my less function is currently implemented as follows struct point3DfLess { // functor for operator bool operator()(const tPoint3Df& leftPoint, const tPoint3Df& rightPoint) const { // apply operator to operands double leftLength = sqrt(leftPoint.x * leftPoint.x + leftPoint.y * leftPoint.y + leftPoint.z * leftPoint.z); double rightLength = sqrt(rightPoint.x * rightPoint.x + rightPoint.y * rightPoint.y + rightPoint.z * rightPoint.z); return ( (leftLength < rightLength) || (leftLength == rightLength && leftPoint.x < rightPoint.x) || (leftLength == rightLength && leftPoint.y < rightPoint.y && leftPoint.z < rightPoint.z)); } }; Any help would be appreciated, thanks in advance

Trap

Oct 26, 2005 at 1:05 AM

The less-predicate has to behave like < does.

Especially:
1) a a2) !(a a==b
3) a !(b
I guess your predicate doesn't obey 1) or 3).

Nitage

Oct 26, 2005 at 2:23 AM

if(right.a!=left.a){    return right.a < left.a;}else if(right.b != left.b){    return right.b < left.b;}else{    return right.c < left.c;}

Also, std::map isn't a hashtable.

floriang

Oct 26, 2005 at 1:51 PM

thanks for the input guys, I still can't get it to run properly though :(

Trap, thanks for the theoretics, I was tired yesterday before posting the question, I could have checked the MSDN before asking, so sorry for not making myself a little smarter in advance. So now I double checked the MSDN, predicate must be irreflexive, antisymmetric and transitive (equivalence must be transitive too).

Nitage, your predicate seems to comply with the given conditions, after having read Trap's reply I came up with the same solution before having read yours (except that in your reply, left and right are swapped I suppose).

Now that I have implemented the function accordingly,

if (leftPoint.x != rightPoint.x)
{
return leftPoint.x < rightPoint.x;
}
else if (leftPoint.y != rightPoint.y)
{
return leftPoint.y < rightPoint.y;
}
else
{
return leftPoint.z < rightPoint.z;
}

I still get solutions that are not dependent of the z coordinate. The find() doesn't work as it should. Is there anything else I have to consider when implementing a compare function as above? Must I implement anything else?

To be a little more precise on my problem: It's for visualizing a random earthquake. I have a given heightmap, and for each texel I create a point, a tPoint3Df, y coordinate being 0.0f. For each point then, I create random deformation vectors, mapping the tPoint3Dfs to to the deformation. This is done in some deformation manager of mine. I then register a bunch of vertices in my manager, whe goes through the whole map, trying to find a tPoint3Df with the vertices' coordinates (projected into x-z again), using the find().

When setting up the tPoint3Df to Deformation map, the map's size afterwards is somewhat at 262thousand entries, 512x512 texels, so the setting up works correctly. And apperently, the find() on the vertices always delivers an entry, but it doesn't seem to be a unique or correct mapping, because as said, the deformation then extracted is always the same for all points with the same z-coordinate.

Any ideas? I'm still on it.

Extrarius

Oct 26, 2005 at 2:14 PM

Your problem may be that the coordinates don't end up exactly the same due to floating point errors/inaccuracies. Unfortunately, fixing such a problem can be exceedingly difficult and will often be platform dependant or have undesirable side effects.

One possible solution is to use something like:

const float FLOAT_TOLERANCE = 0.0001f; //0.01% error allowed//Equality test. Use instead of ==bool FloatEqual(float a, float b){   if(b != 0.0f)   {      return fabsf(a/b) < FLOAT_TOLERANCE;   }   else if(a != 0)   {      return fabsf(b/a) < FLOAT_TOLERANCE;   }   else   {      return true; //Both 0   }}//Relative comparison, use instead of <bool FloatLess(float a, float b){   if(FloatEqual(a, b))   {      return false;   }   return (a < b);}

Make sure that wherever you use FloatEqual for equality testing, you also use FloatLess for greater-than and less-than comparisons. If you combine FloatEqual with the standard comparison operators, you'll get invalid results.
You can define the other comparisons from the above two if you're not comfortable just using those.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.