std::map unique std::less<> function for a 2D point as key

Question

Well, after four hours of debugging, confused as I could be, I found out the cause of the problem...

I am making some program that saves some point in a std::map and render those in my window. But weirdly, some points failed to make it into the map.

std::map<Point2, Prop*> m_Props_m;

void AddProp(std::pair<Point2, Prop*> p)
{
    m_Props_m.insert(p);
}

struct Point2
{
unsigned int Point2::x;
unsigned int Point2::y;
//--------
Point2::Point2()
    :x(0)
    ,y(0)
{}

bool Point2::operator< (const Point2& b) const
{
    return ( x+y < b.x+b.y );
}

bool Point2::operator> (const Point2& b) const
{
    return ( x+y > b.x+b.y );
}
};

Thank god I have some experience with binary trees so I could find out the cause of my problem.

Imagine we have 2 Point2's.

Point2 a(0,1);
Point2 b(1,0);

As you can see, with the operator< method I have written it would return false, and the operator> would also return false. Thus if a is already in the map, and b gets inserted, the insertion fails.

Now, this is all good and well, but how can I fix this? Is there any way I could have a less than operator for a 2D point that would allow me to store every unique point in the map?

Answer 1

std::map doesn't use operator> at all, so you don't have to worry about that.

To sort on multiple fields (in this case, two), use a so-called "lexicographical ordering", meaning that the first field is most important, and the second breaks ties:

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