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

Answer 3

No. You need to also catch (a.field1 > b.field1).

This is not a strict weak ordering, because it would give (1,2) < (2,1), but also (2,1) < (1,2).

Answer 4

Here's a version that relies on the logical short-circuit rule to avoid explicit branching

template<typename T>
bool operator< (T const& a, T const& b)
{
        return (
                 ( a.field1 < b.field1 ) || (( a.field1 == b.field1 ) &&
                 ( a.field2 < b.field2 ))
        );
}

This assumes that your primitive type of field1 has an operator==. It becomes tedious to type this for more than 2 fields, but you could use std::lexicographical_compare if your class obj stores the fields inside an std::array<T, N> for some type T and size N

template<typename T, int N>
struct obj
{
    std::array<T, N> field;
};

bool operator< (obj const& a, T const& b)
{
        return std::lexicographical_compare(
            a.field.begin(), a.field.end(), 
            b.field.begin(), b.field.end()
        );
}

Note that there is a draft paper N3326 that discusses adding operators == and < automatically for class types.

Answer 5

My method described below involves some macros, but still useful in many cases. Maybe something like this can be also done with inline functions.

#define CMP_LT2(a, b) ((a) < (b) ? (a) : (b))
#define CMP_GT2(a, b) ((a) > (b) ? (a) : (b))
#define CMP_LTE2(a, b) ((a) <= (b) ? (a) : (b))
#define CMP_GTE2(a, b) ((a) >= (b) ? (a) : (b))
#define CMP_EQ2(a, b) ((a) == (b))
#define CMP_NEQ2(a, b) ((a) != (b))
#define CMP_LT3(a, b, c) (CMP_EQ2(a, b) ? (c) : CMP_LT2(a, b))
#define CMP_GT3(a, b, c) (CMP_EQ2(a, b) ? (c) : CMP_GT2(a, b))
#define CMP_LTE3(a, b, c) (CMP_EQ2(a, b) ? (c) : CMP_LT2(a, b))
#define CMP_GTE3(a, b, c) (CMP_EQ2(a, b) ? (c) : CMP_GT2(a, b))
#define CMP_EQ3(a, b, c) ((a) == (b) ? (c) : false)
#define CMP_NEQ3(a, b, c) ((a) != (b) ? true : (c))

Then assume you have:

struct Point3D {
    double x;
    double y;
    double z;
};

And then you write:

struct Point3D {
    double x;
    double y;
    double z;

    bool operator<(const Point3D& other) const noexcept
    {
        return CMP_LT3(z, other.z,
               CMP_LT3(y, other.y,
               CMP_LT2(x, other.x)));
    }
};

Answer 6

You can use variadic templates in c++11 or later

template<typename T>
bool less_than( const T& a, const T& b )
{
    return a < b;
}

template<typename T, typename... Args>
bool less_than( const T& a, const T& b, Args... args )
(
    if ( a < b )
          return true;
    else if ( b < a )
          return false;
    else
          return less_than(  args...  );
)

Then you would call as

return less_than(a.x,b.x,
                 a.y,b.y,
                 a.z,b.z);

It supports any number of fields or types as long as type has < operator. You can mix types.