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);
}

Answer 3

One lazy way to do it:

bool operator<( point const &pt ) const
{
    return ::boost::make_tuple(x,y,z) <
           ::boost::make_tuple(pt.x,pt.y,pt.z);
}

Answer 4

The simplest way to write this is like this:

bool operator<(const point& p) const
{
    if(x < p.x)
    {
        return true;
    }
    else if(p.x < x)
    {
        return false;
    }

    if( y < p.y)
    {
        return true;
    }
    else if( p.y < y)
    {
        return false;
    }

    if( z < p.z)
    {
        return true;
    }
    else if(p.z < z)
    {
        return false;
    }

    return false;

}

Answer 5

if they're supposed to be ordered in a certain way, you'll want to specify that exact way (for example by euclidean distance from 0/0/0). If all you want is to distinguish different points, you could do something like

x == x2 ? (y == y2 ?  (z < z2) : y < y2) : x < x2 

Answer 6

Just a guess guys,

bool operator<(const point& other) const
{
  return( memcmp( (void*) this, (void*) &other, sizeof(point)) < 0);
}

Of course, the order is kind of weird since x,y and z are signed values, but this should be suitable to order into a std::map, isn't it ?