What's the simplest way of defining lexicograp

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

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.

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.