How to define operator< on an n-tuple that satisfies a strict weak ordering [duplicate]

Question

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.

Maxillary

See this answer in the c++faq. – Consignor

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

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;

...

Hardigg

This assumes the question is about ordering within the tuple, rather than what I'd assume, ordering between tuples. – Tropho

OK, edited code compares and orders between tuples, rather than within. I presume! – Tropho

Yeah, added a comment to the effect, but it didn't get though. The original code was really d'oh. I could claim that it showed the principle without actually doing anything useful, but.... – Hardigg

Though if you have iterators as in your vector example, just use std::lexographical_compare. – Forejudge

This is implementation of Lexicographical ordering - the one of many possible strict weak orderings on n-tuple. – Cherise

Comparison is NOT expensive. Branch missprediction is. – Talton

@Dan: that's true on average, but depends a lot on the data types. – Hardigg

Answer 2

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.

Simoniac

The best explanation of Strict Weak Ordering I have read. I love that you made it very clear by exhaustively explaining all cases – Gev

Specifically what helped me understand how to establish a strict weak ordering is how equivalence is determined by a and b never being less than the other. This is precisely where the bug existed in my comparator predicate. – Niemi

Answer 3

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

Nyctophobia

I have more details on how to use a member tie() function to support concise and consistent versions of multiple operators in this answer - but to summarise auto My_Struct::tie() const { return std::tie(a_, b_, c_); } then e.g. bool operator<(const My_Struct& lhs, const My_Struct& rhs) { return lhs.tie() < rhs.tie(); } (repeat for <=, == etc.). Of course C++ adds 3-way comparison, which is an even better alternative. – Nyctophobia

Answer 4

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.

Olives

Answer 5

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;

Musetta

Answer 6

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.

Plane

Of course you shouldn't actually use that code (at least without first renaming the variables). Leading underscores are bad outside the standard library. – Carbrey

Fair comment, I just pasted it without thinking. A good argument against cutting and pasting code! – Plane

+1. This has the benefit of requiring only LessThanComparable behavior rather than additionally requiring the EqualityComparable concept implicit under many other answers. – Hydroponics

Not all things with underscores on the front are always reserved. _Leadingcapitals always are, as in this case. So are any identifiers containing double__underscores anywhere. However, _leadinglowercase is only reserved in the global scope (I would argue it's not worth using elsewhere either, though). – Venose

Answer 7

Note that interestingly, an operator < that always returns false meets the requirements of strict weak ordering.

Esquimau