Operator< and strict weak ordering

Question

Hello!

How to define operator< on n-tuple (for example on 3-tuple) so that it satisfy strict weak ordering concept ? I know that boost library has tuple class with correctly defined operator< but for some reasons I can't use it.

Answer 1

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".

---

[edit] removed wrong code

Answer 2

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.

Answer 3

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.

Answer 4

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;

Answer 5

To Konstantin: Can you publish your tuple implementation? If it is a boost::tuple your problem might result in the fact that your tuple consists of non-comparable types, e.g.

class MyClass { .... };

instances of MyClass can't be less-then-compared if you don't explicitly define the comparison. Putting this type into the tuple will make it uncomparable as well.

To markh44: Until now I don't have enough credits to comment in your post directly.

Just a formal remark: The code taken from standard lib implementation is not standard conform. ISO C++ reserves all names starting with _ followed by capital letter (i.e. _Left or _Right) for the implementation purposes. The same applies to names containing __ (double underscore). Any compiler will compile it, but you might see strange compiler erros resulting from macro replacements, where macro names might be identical with your identifier names.

Regards,

Ovanes

Answer 6

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. If you have two objects of a type that you define.

In terms of C++ this means if you have two objects of a give type 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.

Check the SGI page on the subject:
http://www.sgi.com/tech/stl/StrictWeakOrdering.html