Operator< and strict weak ordering

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.

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;

...

You could simply use three-element vectors, which will already have operator<() suitably defined. This has the advantage that it extends to N-elements without you having to do anything.

The basic flow should be along the lines of: if the Kth elements are different, return which is smaller else go to next element. The code following assumes you don't have a boost tuple otherwise you would use get<N>(tuple) and not have the problem to begin with.

if (lhs.first != rhs.first)
    return lhs.first < rhs.first;                
if (lhs.second != rhs.second)
    return lhs.second< rhs.second;
return lhs.third < rhs.third;

Even if you can't use the boost version, you should be able to nick the code. I nicked this from std::pair - a 3 tuple will be similar I guess.

return (_Left.first < _Right.first ||
        !(_Right.first < _Left.first) && _Left.second < _Right.second);

Edit: As a couple of people have pointed out, if you steal code from the standard library to use in your code, you should rename things that have underscores on the front as these names are reserved.