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

The thing is that you are fine with just declaring one trivalue compare function if you autogenerate all operators using: http://en.wikipedia.org/wiki/Barton%E2%80%93Nackman_trick

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.

Answer 4

One thing I did once which seemed a useful idiom was to write a compare function which returns a boolean given takes two arguments plus a boolean called "bias". The function returns true if the first argument is greater, or if "bias" is set and the two arguments are equal. Thus, a compare whose result depended upon two sub-comparisons would be:

  if (compare(a.part1,b.part1,compare(a.part2,b.part2,bias)))
    ...

Note that this will do 'extra' comparisons, since part2's will be compared even if the part1 compare would be sufficient to yield an answer, but if avoids redundant tests for equality.

Otherwise, using tri-value logic, one could do something like:

  int result;

  if ((result = compare(a.part1,b.part1)) != 0) return result;
  if ((result = compare(a.part2,b.part2)) != 0) return result;

The latter form avoids unnecessary comparisons, and is easily extensible to any number of fields.

Answer 5

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 6

For the first tri-value compare() function

int compare( const S &l, const S &r ) {
    return r.val - l.val;
}

For the later

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

Answer 7

This is no clearer or shorter than your last example, but it does have the advantage of not requiring anything other than operator< on the members.

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

The last case can always be simplified, unfortunately the prior cases must always be the longer form.

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