How do you structure your comparison functions?

Question

I frequently encounter situations, especially with sorting in C++, where I am comparing a series of fields in order to compare a larger structure. A simplified example:

struct Car{
    Manufacturer make;
    ModelName model;
    Year year;
};

bool carLessThanComparator( const Car & car1, const Car & car2 ){
    if( car1.make < car2.make ){
        return true;
    }else if( car1.make == car2.make ){
        if( car1.model < car2.model ){
            return true;
        }else if( car1.model == car2.model ){
            if( car1.year < car2.year ){
                return true;
            }
        }
    }

    return false;
}

My instinctive approach seems cumbersome, especially for more than 3 fields. How would you structure this series of comparisons in C++? Do other languages provide a more succinct or elegant syntax?

Marrowfat

Personal style - I'd implement a strcmp() like function (or method) that returns 0 if a equals b, 1 if a is greater than b, and -1 if a is less than b, and then define the comparison operators (if you like) and/or methods in terms of the comparison function. Then we'd just have bool carLessThanComparator( const Car & car1, const Car & car2 ) { return cmp(car1, car2) == -1; } – Interlope

Answer 1

Well, if your function hits a return in the if clause, there's no need for an explicit else, since it would have already bailed out. That can save on the "indent valley":

bool carLessThanComparator( const Car & car1, const Car & car2 ) {
    if( car1.make < car2.make )
        return true;

    if ( car1.make != car2.make )
        return false;

    if( car1.model < car2.model )
        return true;

    if( car1.model != car2.model )
        return false;

    if( car1.year < car2.year )
        return true;

    return false;
}

I like MarkusQ's LISPish short-circuiting approach as well.

Refrigeration

Why not just "return car1.year < car2.year" as the last statement? – Illstarred

Just for symmetry -- I wanted the code sample to be as clear as I could make it. In practice I'd do what you said, or really I'd code it like Markus did. – Refrigeration

Answer 2

If this happens a lot you could put a template like this into a common header:

template<typename T, typename A1, typename A2, typename A3>
bool
do_less_than(
        const typename T& t1,
        const typename T& t2,
        const typename A1 typename T::* a1,
        const typename A2 typename T::* a2,
        const typename A3 typename T::* a3)
{
    if ((t1.*a1) < (t2.*a1)) return true;
    if ((t1.*a1) != (t2.*a1)) return false;
    if ((t1.*a2) < (t2.*a2)) return true;
    if ((t1.*a2) != (t2.*a2)) return false;
    return (t1.*a3) < (t2.*a3);
}

Add other templates for different numbers of arguments as required. For each less than function, you can then do something like this:

bool carLessThanComparator(const Car& car1, const Car& car2)
{
    return do_less_than(car1, car2, &Car::make, &Car::model, &Car::year);
}

Illstarred

I rarely see the pointer-to-member syntax in C++. Very interesting. – Marrowfat

And this is an example of why – Inelegancy

The main point is that the complexity is in a library and is created once, while the common code becomes more simple. The order of comparison in the actual comparison function is obvious and there are no inverted comparison bugs. – Illstarred

Answer 3

Personally I'd suggest NOT using the != or == operators like we seem to recommend here - this requires the arguments/members to have both less then and equal operators just to do a less then check on a class containing them - using just the less then operator is enought and will save you redundancy and potential defects in the future.

I suggest you write:

bool operator<(const Car &car1, const Car &car2) 
{
    if(car1.make < car2.make)
        return true;
    if(car2.make < car1.make)
        return false;

    if(car1.model < car2.model)
        return true;
    if(car2.model < car1.model)
        return false;

    return car1.year < car2.year;
}

Anatomical

Good point. This does allow you to implement the less-than comparison on the larger structure with only the requirement that less-than comparison is available for each member. – Marrowfat

Answer 4

I know it's an old question, but for future visitors: the modern C++11 solution is to use std::tie

struct Car{
    Manufacturer make;
    ModelName model;
    Year year;
};

bool operator<(Car const& lhs, Car const& rhs)
{
    return std::tie(lhs.make, lhs.model, lhs.year) < std::tie(rhs.make, rhs.model, rhs.year);
}

std::tie converts the struct into a std::tuple so that the above comparison operator delegates to std::tuple::operator<. This in turn does a lexicographical compare with respect to the order in which the members are marshalled into std::tie.

The lexicographic comparison is short-circuited in the same way as in the other solutions to this question. But it is even succinct enough to define on the fly inside a C++ lambda expression. For classes with private data members, it's best defined inside the class as friend function.

Tetrastich

Answer 5

bool carLessThanComparator( const Car & car1, const Car & car2 ){
    return (
      ( car1.make  < car2.make  ) or (( car1.make  == car2.make  ) and
      ( car1.model < car2.model ) or (( car1.model == car2.model ) and
      ( car1.year  < car2.year  ) 
      )));

-- MarkusQ

Alcantara

Answer 6

Personally, I'd override the ==, <, >, and any other operators needed. That would clean up the code, not in the comparison, but when you need to make the comparison. For the actual comparison itself, I would write it similarly to what Crashworks said.

bool operator<(const Car &car1, const Car &car2) {
    if(car1.make < car2.make)
        return true;
    if(car1.make != car2.make)
        return false;
    if(car1.model < car2.model)
        return true;
    if(car1.model != car2.model)
        return false;
    return car1.year < car2.year;
}

Bookstall

Why not just "return car1.year < car2.year" as the last statement? I agree with the operators thing, except I'd only do operator< and operator==, and then use something like boost::totally_ordered – Illstarred

I've never really looked at boost too much, but just looking up boost::totally_ordered, it would be useful. As for the last statement... I actually just copied Crashwork's code when I saw it was the same style I'd use. Using return like you said would be better. – Bookstall

Answer 7

I was wondering the same thing as the OP and stumbled upon this question. After reading the answers I have been inspired by janm and RnR to write a lexicographicalMemberCompare template function that only uses only operator< on the compared members. It also uses boost::tuple so that you can specify as many members as you want. Here it is:

#include <iostream>
#include <string>
#include <boost/tuple/tuple.hpp>

template <class T, class Cons>
struct LessThan
{
    static bool compare(const T& lhs, const T& rhs, const Cons& cons)
    {
        typedef LessThan<T, typename Cons::tail_type> NextLessThan;
        typename Cons::head_type memberPtr = cons.get_head();
        return lhs.*memberPtr < rhs.*memberPtr ?
            true :
            (rhs.*memberPtr < lhs.*memberPtr  ?
                false :
                NextLessThan::compare(lhs, rhs, cons.get_tail()));
    }
};

template <class T>
struct LessThan<T, class boost::tuples::null_type>
{
    static bool compare(const T& lhs, const T& rhs,
                        const boost::tuples::null_type& cons)
    {
        return false;
    }
};

template <class T, class Tuple>
bool lexicographicalMemberCompare(const T& lhs, const T& rhs,
                                  const Tuple& tuple)
{
    return LessThan<T, typename Tuple::inherited>::compare(lhs, rhs, tuple);
}

struct Car
{
    std::string make;
    std::string model;
    int year;
};

bool carLessThanCompare(const Car& lhs, const Car& rhs)
{
    return lexicographicalMemberCompare(lhs, rhs,
        boost::tuples::make_tuple(&Car::make, &Car::model, &Car::year));
}

int main()
{
    Car car1 = {"Ford", "F150", 2009};
    Car car2 = {"Ford", "Escort", 2009};
    std::cout << carLessThanCompare(car1, car2) << std::endl;
    std::cout << carLessThanCompare(car2, car1) << std::endl;
    return 0;
}

Hope this is useful to someone.

Autogiro

You have an operator>. Also, comparison functions tend to be written outside the class. Otherwise pretty nifty. – Pigweed

Oops. Fixed operator> and put operator< outside class. I didn't receive the memo about why putting comparison operators inside classes is bad (when the lhs is already the class itself). – Autogiro

Even if it's just operator< or something, it's still generally better to keep it outside the class, for consistency. – Pigweed

Oof, what was I smoking? This can be done in a single line now in C++11 with std::tie. See TemplateRex's answer: https://mcmap.net/q/1862431/-how-do-you-structure-your-comparison-functions – Autogiro