Provide strict ordering during comparison with multiple fields

Question

How do you provide strict ordering between objects with a lot of comparable fields?

Assume you have two objects x and y that you have to compare, each with 3 fields (a, b,c)

bool less(x, y)
  return x.a < y.a || x.b < y.b || x.c < y.c

Good, but this provide weak ordering. If x.a < y.a and y.b < x.b, less(x,y) is true, less(y, x) is also true.

I am used to writing

bool less(x, y)
  return x.a < y.a || (x.a == y.a && x.b < y.b)

but it start being very ugly once the number of fields involved grows.

bool less(x, y)
  return x.a < y.a || 
        (x.a == y.a && x.b < y.b) ||
        (x.a == y.a && x.b == y.b && x.c < y.c) ||
        (x.a == y.a && x.b == y.b && x.c == y.c && x.d < y.d);

Does someone has a better looking algorithm?

Answer 1

If you are on C++11 or higher, there is a nice trick to get SWO without having to write it out by hand. You can use std::tuple, to pack your members and the fact that std::tuple implements operator< as a lexicographical ordering.

So you can write this

struct foo {
    int x, y, z;

    bool operator<(const foo& rhs) const {
        return std::tie(x, y, z) < std::tie(rhs.x, rhs.y, rhs.y);
    }
};

and struct foo will be compared lexicographically by x, y, z. This is still a lot to write, so you can improve it a bit

struct foo {
    int x, y, z;

    auto tied() const {
        return std::tie(x, y, z);
    }

    bool operator<(const foo& rhs) const {
        return tied() < rhs.tied();
    }
};

this can save a lot of typing if you have a lot of members, but it assumes C++14 (for C++11, you have to write out the return type of tied by hand).