What's the simplest way of defining lexicographic comparison for elements of a class?

Question

If I have a class that I want to be able to sort (ie support a less-than concept), and it has several data items such that I need to do lexicographic ordering then I need something like this:

struct MyData {
  string surname;
  string forename;

  bool operator<(const MyData& other) const {
    return surname < other.surname || (surname==other.surname && forename < other.forename); }
};

This becomes pretty unmanageable for anything with more than 2 data members. Are there any simpler ways of achieving it? The data members may be any Comparable class.

Destruct

Answer 1

With the advent of C++11 there's a new and concise way to achieve this using std::tie:

bool operator<(const MyData& other) const {
  return std::tie(surname, forename) < std::tie(other.surname, other.forename);
}

Destruct

Answer 2

tuple is a good idea, but if you want to keep having names for your member variables, it might be good enough to restructure your comparison function like this:

struct MyData {
    string surname;
    string forename;
    string var;
    // ...

    bool operator<(const MyData& other) const {
        if (surname != other.surname) return surname < other.surname;
        if (forename != other.forename) return forename < other.forename;
        if (var != other.var) return var < other.var;

        // ...

        return false; //< They are equal
    }
};

Depending on your taste, you might even want a macro like #define COMPARE(field) if (field != other.field) return field < other.field; to reduce duplication. Then the function would just become a list of COMPARE-invocations.

Rusty

Maybe #define LEX_LT(mem) if(mem != other.mem) return mem < other.mem and then chain them as LEX_LT(surname); LEX_LT(forename); LEX_LT(var); ...; return false; – Dube

I like the layout of that, it's much more manageable and less error-prone than the nested-if. I'm not averse to occasional macro use, and that could be handy for larger structures, but I think the basic form is clear enough. – Destruct

Answer 3

You could store the data in a boost::tuple, which provides lexicographic comparison, and provide named accessor functions, along the lines of:

#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_comparison.hpp>

struct Data {
    string &surname()  {return stuff.get<0>();}
    string &forename() {return stuff.get<1>();}

    // it would be polite to add const overloads too.

    bool operator<(const Data &other) const {return stuff < other.stuff;}

private:
    boost::tuple<string, string> stuff;
};

I believe this is also available as std::tr1::tuple, and will be std::tuple in the forthcoming standard.

Maintaining the list of accessors is probably more manageable than maintaining the comparison code.

Spiritual

Interesting solution. It seems a shame to lose the named fields though as seeing the class's contents in the debugger becomes more difficult. – Destruct

You can keep the named fields and use the tuple only for comparison purposes, e.g return boost::tie(surname, forename) < boost::tie(other.surname, other.forename); – Rome

Even better, wrap tie in a member function. Then you only have to maintain a single list of the lexicographical order. – Spiritual

Neat - I hadn't come across boost::tie() before – Destruct

Answer 4

If all members have the same type you could put them in std::vector. By default std::lexicographical_compare will be used to compare vectors.

Hobnob

Answer 5

You can use a boost::tuple or std::pair which has built-in lexigraphical comparison. Of course the disadvantage is you can't associate a method to the tuples.

Dube