Defining operator< for a struct

I sometimes use small structs as keys in maps, and so I have to define an operator< for them. Usually, this ends up looking something like this:

struct MyStruct
{
    A a;
    B b;
    C c;

    bool operator<(const MyStruct& rhs) const
    {
        if (a < rhs.a)
        {
           return true;
        }
        else if (a == rhs.a)
        {
            if (b < rhs.b)
            {
                return true;
            }
            else if (b == rhs.b)
            {
                return c < rhs.c;
            }
        }

        return false;
    }
};

This seems awfully verbose and error-prone. Is there a better way, or some easy way to automate definition of operator< for a struct or class?

I know some people like to just use something like memcmp(this, &rhs, sizeof(MyStruct)) < 0, but this may not work correctly if there are padding bytes between the members, or if there are char string arrays that may contain garbage after the null terminators.

This is quite an old question and as a consequence all answers here are obsolete. C++11 allows a more elegant and efficient solution:

bool operator <(const MyStruct& x, const MyStruct& y) {
    return std::tie(x.a, x.b, x.c) < std::tie(y.a, y.b, y.c);
}

Why is this better than using boost::make_tuple? Because make_tuple will create copies of all the data members, which can be costly. std::tie, by contrast, will just create a thin wrapper of references (which the compiler will probably optimise away entirely).

In fact, the above code should now be considered the idiomatic solution to implementing a lexicographical compare for structures with several data members.

Others have mentioned boost::tuple, which gives you a lexicographical comparison. If you want to keep it as a structure with named elements, you can create temporary tuples for comparison:

bool operator<(const MyStruct& x, const MyStruct& y)
{
    return boost::make_tuple(x.a,x.b,x.c) < boost::make_tuple(y.a,y.b,y.c);
}

In C++0x, this becomes std::make_tuple().

UPDATE: And now C++11 is here, it becomes std::tie(), to make a tuple of references without copying the objects. See Konrad Rudolph's new answer for details.

I would do this:

#define COMPARE(x) if((x) < (rhs.x)) return true; \
                   if((x) > (rhs.x)) return false;
COMPARE(a)
COMPARE(b)
COMPARE(c)
return false;
#undef COMPARE

In this case you can use boost::tuple<int, int, int> - its operator< works just the way you want.

I think the easiest way is to stick with the < operator for all comparisons and don't use > or ==. Below is the pattern I follow, and you can follow for all your structs

typedef struct X
{
    int a;
    std::string b;
    int c;
    std::string d;

    bool operator <( const X& rhs ) const
    {
        if (a < rhs.a) { return true; }
        else if ( rhs.a < a ) { return false; }

        // if neither of the above were true then 
        // we are consdidered equal using strict weak ordering
        // so we move on to compare the next item in the struct

        if (b < rhs.b) { return true; }
        if ( rhs.b < b ) { return false; }

        if (c < rhs.c) { return true; }
        if ( rhs.c < c ) { return false; }

        if (d < rhs.d) { return true; }
        if ( rhs.d < d ) { return false; }

        // if both are completely equal (based on strict weak ordering)
        // then just return false since equality doesn't yield less than
        return false;
    }
};

The best way I know is to use a boost tuple. It offers among others a builtin comparison and constructors.

#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_comparison.hpp>

typedef boost::tuple<int,int,int> MyStruct;

MyStruct x0(1,2,3), x1(1,2,2);
if( x0 < x1 )
   ...

I also like Mike Seymors suggestion to use temporary tuples through boost's make_tuple

I usually implement lexicographical ordering this way:

bool operator < (const MyObject& obj)
{
	if( first != obj.first ){
		return first < obj.first;
	}
	if( second != obj.second ){
		return second < obj.second;
	}
	if( third != obj.third ){
		return third < obj.third
	}
	...
}

Mind you it needs extra consideration for floating point values (G++ warnings), for those something like this would be better:

bool operator < (const MyObject& obj)
{
	if( first < obj.first ){
		return true;
	}
	if( first > obj.first ){
		return false;
	}
	if( second < obj.second ){
		return true;
	}
	if( second > obj.second ){
		return false;
	}
	...
}

#include <iostream>

#include <boost/fusion/include/adapt_struct.hpp>
#include <boost/fusion/include/less.hpp>

struct MyStruct {
   int a, b, c;
};

BOOST_FUSION_ADAPT_STRUCT( MyStruct,
                           ( int, a )
                           ( int, b )
                           ( int, c )
                          )

bool operator<( const MyStruct &s1, const MyStruct &s2 )
{
   return boost::fusion::less( s1, s2 );
}

int main()
{
   MyStruct s1 = { 0, 4, 8 }, s2 = { 0, 4, 9 };
   std::cout << ( s1 < s2 ? "is less" : "is not less" ) << std::endl;
}

if you can't use boost, you could try something like:

#include <iostream>

using namespace std;

template <typename T>
struct is_gt
{
  is_gt(const T& l, const T&r) : _s(l > r) {}

  template <typename T2>
  inline is_gt<T>& operator()(const T2& l, const T2& r)
  {
    if (!_s)
    {
      _s = l > r;
    }
    return *this;
  }

  inline bool operator!() const { return !_s; }

  bool _s;
};

struct foo
{
  int a;
  int b;
  int c;

  friend bool operator<(const foo& l, const foo& r);
};

bool operator<(const foo& l, const foo& r)
{
  return !is_gt<int>(l.a, r.a)(l.b, r.b)(l.c, r.c);
}

int main(void)
{
  foo s1 = { 1, 4, 8 }, s2 = { 2, 4, 9 };
  cout << "s1 < s2: " << (s1 < s2) << endl;
  return 0;
}

I guess this avoids any macros, and as long as the types in the structure support <, it should work. Of course there is overhead for this approach, constructing is_gt and then superflous branches for each parameter if one of the values is greater...

Edit:

Modified based on comments, this version should now short-circuit as well, now uses two bools to keep state (not sure there's a way to do this with a single bool).

template <typename T>
struct is_lt
{
  is_lt(const T& l, const T&r) : _s(l < r), _e(l == r) {}

  template <typename T2>
  inline bool operator()(const T2& l, const T2& r)
  {
    if (!_s && _e)
    {
      _s = l < r;
      _e = l == r;
    }
    return _s;
  }

  inline operator bool() const { return _s; }

  bool _s;
  bool _e;
};

and

bool operator<(const foo& l, const foo& r)
{
  is_lt<int> test(l.a, r.a);
  return test || test(l.b, r.b) || test(l.c, r.c);
}

just build up a collection of such functors for various comparisons..

I just learned the boost::tuple trick, thanks, @Mike Seymour!

If you can't afford Boost, my favorite idiom is:

bool operator<(const MyStruct& rhs) const
{
    if (a < rhs.a)  return true;
    if (a > rhs.a)  return false;

    if (b < rhs.b)  return true;
    if (b > rhs.b)  return false;

    return (c < rhs.c);
}

which I like because it sets everything in parallel structure that makes errors and omissions easier to spot.

But, of course, you are unit testing this anyway, right?

I wrote a perl script to help me. For example given:

class A
{
int a;
int b;
int c;

It would emit:

bool operator<(const A& left, const A& right)
{
    bool result(false);

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

    return result;
}

Code (it's a bit long):

#!/usr/bin/perl

use strict;

main:

my $line = <>;
chomp $line;
$line =~ s/^ *//;

my ($temp, $line, $temp) = split / /, $line;

print "bool operator<(const $line& left, const $line& right)\n{\n";
print "    bool result(false);\n\n";

my $ifText = "if";

$line = <>;

while($line)
{
    if($line =~ /{/)
    {
        $line = <>;
        next;
    }
    if($line =~ /}/)
    {
        last;
    }

    chomp $line;
    $line =~ s/^ *//;

    my ($type, $name) = split / /, $line;
    $name =~ s/; *$//;

    $line = <>;
    if($line && !($line =~ /}/))
    {
        print "    $ifText(left.$name != right.$name)\n";
        print "    {\n";
        print "        result = left.$name < right.$name;\n";
        print "    }\n";

        $ifText = "else if";
    }
    else
    {
        print "    else\n";
        print "    {\n";
        print "        result = left.$name < right.$name;\n";
        print "    }\n";

        last;
    }
}

print "\n    return result;\n}\n";

bool operator <(const A& l, const A& r)
{

    int[] offsets = { offsetof(A, a), offsetof(A, b), offsetof(A, c) };
    for(int i = 0; i < sizeof(offsets)/sizeof(int); i++)
    {
        int ta = *(int*)(((const char*)&l)+offsets[i]);
        int tb = *(int*)(((const char*)&r)+offsets[i]);

        if (ta < tb)
             return true;
        else if (ta > tb)
             break;

    }
    return false;
}

When you can produce iterators over the elements defining the lexicographic order you can use std::lexicographic_compare, from <algorithm>.

Otherwise I suggest basing comparisons on old three-value compare functions, e.g. as follows:

#include <iostream>

int compared( int a, int b )
{
    return (a < b? -1 : a == b? 0 : +1);
}

struct MyStruct
{
    friend int compared( MyStruct const&, MyStruct const& );
    int a;
    int b;
    int c;

    bool operator<( MyStruct const& rhs ) const
    {
        return (compared( *this, rhs ) < 0);
    }
};

int compared( MyStruct const& lhs, MyStruct const& rhs )
{
    if( int x = compared( lhs.a, rhs.a ) ) { return x; }
    if( int x = compared( lhs.b, rhs.b ) ) { return x; }
    if( int x = compared( lhs.c, rhs.c ) ) { return x; }
    return 0;
}

int main()
{
    MyStruct const  s1 = { 0, 4, 8 };
    MyStruct const  s2 = { 0, 4, 9 };
    std::cout << ( s1 < s2 ? "is less" : "is not less" ) << std::endl;
}

I included the last if and return in the compare function just for generality. I imagine it can help maintenance to very rigidly adhere to a single system. Otherwise you could just do a return compared( lhs.c, rhs.c ) there (and perhaps you prefer that).

Cheers & hth.,

− Alf

If three-way comparisons are more expensive than two-way, and if the more-significant portions of the structures will often be equal, it may be helpful to define field comparison functions with a 'bias' parameter, such that if 'bias' is false, they will return true when a>b, and when bias is true, they will return true if a>=b. Then one can find out if a>b by doing something like:

return compare1(a.f1,b.f1, compare2(a.f2,b.f2, compare3(a.f3,b.f3,false)));

Note that all comparisons will be performed, even if a.f1<>b.f1, but comparisons will be two-way instead of three-way.