Operator< and strict weak ordering

...a new answer to a very old question, but the existing answer miss the easy solution from C++11...

C++11 solution

C++11 onwards provides std::tuple<T...>, which you can use to store your data. tuples have a matching operator< that initially compares the left-most element, then works along the tuple until the outcome's clear. That's suitable for providing the strict weak ordering expected by e.g. std::set and std::map.

If you have data in some other variables (e.g. fields in a struct), you can even use std::tie() to creates a tuple of references, which can then be compared to another such tuple. That makes it easy to write operator< for specific member-data fields in a user-defined class/struct type:

struct My_Struct
{
    int a_;
    double b_;
    std::string c_;
};

bool operator<(const My_Struct& lhs, const My_Struct& rhs)
{
    return std::tie(lhs.a_, lhs.b_, lhs.c_) < std::tie(rhs.a_, rhs.b_, rhs.c_);
}

if (a1 < b1)
  return true;
if (b1 < a1)
  return false;

// a1==b1: continue with element 2
if (a2 < b2)
  return true;
if (b2 < a2)
  return false;

// a2 == b2: continue with element 3
if (a3 < b3)
  return true;
return false; // early out

This orders the elements by a1 being most siginificant and a3 least significant.

This can be continued ad infinitum, you could also e.g. apply it to a vector of T, iterating over comparisons of a[i] < a[i+1] / a[i+1] < a[i]. An alternate expression of the algorithm would be "skip while equal, then compare":

while (i<count-1 && !(a[i] < a[i+1]) && !(a[i+1] < a[i])
  ++i;
return i < count-1 && a[i] < a[i+1];

Of course, if the comparison is expensive, you might want to cache the comparison result.

---

[edit] removed wrong code

---

[edit] if more than just operator< is available, I tend to use the pattern

if (a1 != b1)
  return a1 < b1;

if (a2 != b2)
  return a2 < b2;

...

strict weak ordering

This is a mathematical term to define a relationship between two objects.
Its definition is:

Two objects x and y are equivalent if both f(x, y) and f(y, x) are false. Note that an object is always (by the irreflexivity invariant) equivalent to itself.

In terms of C++ this means if you have two objects of a given type, you should return the following values when compared with the operator <.

X    a;
X    b;

Condition:                  Test:     Result
a is equivalent to b:       a < b     false
a is equivalent to b        b < a     false

a is less than b            a < b     true
a is less than b            b < a     false

b is less than a            a < b     false
b is less than a            b < a     true

How you define equivalent/less is totally dependent on the type of your object.

Formal Definition:
Strict Weak ordering

Computer Science:
Strict Weak Ordering

How it relates to operators:
Comparator

---

As a side note we can implement strict weak ordering manually. But we can do it simply using the std::tuple which has implemented it for you. You simply need to create a tuple without copying the objects.

struct S
{
     ThingA   a;
     ThingB   b;
};
bool operator<(S const& lhs, S const& rhs)
{
    return std::tie(lhs.a, lhs.b) < std::tie(rhs.a, rhs.b);
}

Note: This assumes that thingA and thingB already implement strict weak ordering themselves.

We can also implement equality the same way:

bool operator==(S const& lhs, S const& rhs)
{
    return std::tie(lhs.a, lhs.b) == std::tie(rhs.a, rhs.b);
}

Note again: This assumes that thingA and thingB already implement equality.