How do you write a operator() or less-than-functor neater than a trivalue-compare-function

Question

Writing an operator< () for a struct appears to be clearer than writing the classical trivalue compare.

for example, to sort the following

struct S {
    int val;
};

you can write an operator< ()

bool operator< ( const S &l, const S &r ) {
     return l.val < r.val;
}

or, a trivalue function (usually in the following fashion )

int compare( const S &l, const S &r ) {
    if( r.val > l.val ) return 1;
    if( r.val < l.val ) return -1;
    return 0;
}

The former is clearer, therefore you can say there's better code quality. The latter forces you to think of 3 cases, which complicates code.

But this thought is a bit deceiving in more complex structures:

struct S {
    int x;
    int y;
};

the following is clear, and begginners tend to write it like so

bool operator< ( const S &l, const S &r ) {
     if( l.x < r.x ) return true;
     if( l.y < r.y ) return true;
     return false;
}

but it's wrong ! You can't sort correctly with this !

And it takes some time to think that you actually have to write it like so

bool operator< ( const S &l, const S &r ) {
     if( l.x < r.x ) return true;
     if( l.x > r.x ) return false;
     if( l.y < r.y ) return true;
     if( l.y > r.y ) return false;
     return false;
}

for it to work correctly.

Can you, and do you write this sort of compare function in a nicer/clearer manner ? The old trivalue compare function at least 'forced' you into thinking about >, <, and == cases.

Answer 1

If I don't care about performance or compiler spew, I tend to use this:

return make_tuple(l.x, l.y, ...) < make_tuple(r.x, r.y, ...);

And for a slightly less expensive in terms of copies version:

return tie(cref(l.x), cref(l.y), ...) < tie(cref(r.x), cref(r.y), ...);

Incidentally, the second version also works with lvalues.

Answer 2

I like to do it like this:

bool operator< ( const S &l, const S &r )
{
    if( l.x != r.x ) return l.x < r.x;
    else return l.y < r.y;
}

EDIT: note that this is also one useful feature of std::pair too - it defines this already so you can't make the mistake.

Answer 3

In the int case you can simply write:

return l.x < r.x || (l.x == r.x && l.y < r.y);

Only of you are talking about a type that doesn't have == with the correct behaviour do you need to use something more complex, even then it's not too bad.

return l.x < r.x || (!(r.x < l.x) && l.y < r.y);

Extending to more members:

return l.x < r.x ||
      !(r.x < l.x) && (l.y < r.y ||
      !(r.y < l.y) && (l.z < r.z ||
      /* ... */
      ) /* lisp-like sequence of ) */ );

If you can arrange your members to be in an array or other container you can use std::lexicographical_compare.