Search code examples
c++comparison-operatorslexicographic

operator< comparing multiple fields

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

Solution

  • 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 (and later)

    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.field2);
}

    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.