How to map a bool to a 3d point struct with std::map?

Question

How do I use the following struct:

struct point 
{
    int x;
    int y;
    int z;
};

as a key for std::map<point, bool>? How should I define operator< for two points?

Answer 1

Standard library containers like std::map require that your ordering is a "Strict Weak Ordering", so you have to be very careful when designing one.

The typical approach for a 3-ary tuple looks like this:

bool operator<(const point& other) const
{
   if (x != other.x)
       return (x < other.x);

   if (y != other.y)
       return (y < other.y);

   return (z < other.z);
}

It's like a comparator for just x, but with the difference that if the two xs are the same, you fall through to compare ys. If they are the same, then similarly you fall through to the z comparison.

Answer 2

Of course, boost::tuple<int,int,int> would make this utterly unnecessary.

Update Adding the all-inclusive have-your-cake-and-eat-it-too no-drawback solution here. IMHO it rocks!

#include <boost/tuple/tuple_comparison.hpp>

struct point 
{
    int x, y, z;
    point(int x, int y, int z) : x(x), y(y), z(z) {}
    bool operator<(const point& rhs) const 
    {
        return boost::tie(x, y, z) < boost::tie(rhs.x, rhs.y, rhs.z);
    }
};

Here is the kicker: it all optimizes away. Compile:

int main()
{
    point a(1,2,3), b(3,2,1);
    bool lt = a<b;
    return lt?0:255;
}

With g++ -O2 yields the following in assembly.

main:
.LFB1132:
        pushl   %ebp
        xorl    %eax, %eax
        movl    %esp, %ebp
        popl    %ebp
        ret
.LFE1132:

The compiler was able to optimize the whole of this program to ... return 0 effectively. That is pretty neat.

---

Here goes the simple answer:

struct point 
{
    point(int x, int y, int z) 
        : x(x), y(y), z(z) {}
    int x;
    int y;
    int z;
    bool operator<(const point& rhs) const 
    {
        if (x<rhs.x) return true;
        if (x==rhs.x) 
        { 
            if (y<rhs.y) return true;
            if (y==rhs.y) return z<rhs.z;
        }
        return false;
    }
};

Also, I would consider looking for a redefinition of my struct that will allow using std::lexicographical_compare

#include <algorithm>

// ...
bool operator<(const point& rhs) const 
{
    return std::lexicographical_compare(&xyz, &xyz+3, &rhs.xyz, &rhs.xyz+3);
}