operator< comparing multiple fields

Question

I have the following operator< that is supposed to sort first by a value, then by another value:

    inline bool operator < (const obj& a, const obj& b)      {         if(a.field1< b.field1)             return true;         else             return a.field2 < b.field2;     } 

I have the feeling this is incorrect and that you can't do that without another third comparaison test on the members variables, but I can't find any example where this doesn't work. So whould this really sort as expected? thanks

edit : I would have coded it as :

    inline bool operator < (const obj& a, const obj& b)      {         if(a.field1< b.field1)             return true;                     else if(a.field1> b.field1)             return false;         else             return a.field2 < b.field2;     } 

are there any differences? I'm asking because I know mine is correct from experience but also longer than the first one

Answer 1

I'd like to do it all by myself..

You should only compare the values of Obj::field2 if the values of Obj::field1 are equal.

The easy-to-understand way:

/* This will meet the requirements of Strict-Weak-Ordering */  if (a.field1 != b.field1) return a.field1 < b.field1; else                      return a.field2 < b.field2; 

The correct (recommended) way:

The "correct" way of implementing it uses only operator< to compare the fields, the below looks more complicated than it really is.

It will however yield the same result as the easy-to-understand example previously written.

return a.field1 < b.field1 || (   !(b.field1 < a.field1) && a.field2 < b.field2 ); 

---

There must be a way of implementing operator< without causing a lot of headache?

C++11

You can use std::tuple from the STL which already have operator< for multiple fields defined, such as in the below example.

#include <utility>  ...  inline bool operator< (Obj const& lhs, Obj const& rhs) {   return std::tie (lhs.field1, lhs.field2) < std::tie (rhs.field1, rhs.field); } 

C++03

If your compiler doesn't have support for C++11 yet and you only need to compare two fields from each object you could use std::pair instead.

The reason for std::make_pair is the same as in the previous example using std::tie.

#include <utility>  ...  inline bool operator< (Obj const& lhs, Obj const& rhs) {   return std::make_pair (lhs.field1, lhs.field2)        < std::make_pair (rhs.field1, rhs.field2); } 

^{using std::pair will require copies of the members to be created, which in some circumstances is undesirable.}

Is this really recommended practise?

See the below question/answers for more information, but to sum it up; the c++11 approach doesn't cause that much overhead and it's very simple to implement.

• Implementing comparision operators via 'tuple' and 'tie', a good idea?

Answer 2

Think of what happens if a.field1 is greater than b.field1 but a.field2 is less than b.field2. In that circumstance, you compare based solely on field2 which is not what you want.

You only want to bring field2 into play where the field1 fields are equal, so what you're looking for is something like (pseudo-code):

if a.field1 < b.field1: return true if a.field1 > b.field1: return false # field1s is equal here. return a.field2 < b.field2