Operator≪ and Strict Weak Ordering

Operator and strict weak ordering

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;

...

Does greater operator satisfy strict weak ordering?

Does greater operator “>” satisfy strict weak ordering?

The mathematical strict greater than relation is a strict weak ordering.

As for the operator in C++ langauge: For all integers types: Yes. In general: No, but in most cases yes. Same applies to strict less than operator.

As for the confusing quote, "is less than" in that context intends to convey that means that the the end result of the sort operation is a non-decreasing sequence i.e. objects are "less" or equal to objects after them. If std::greater is used as comparison object, then greater values are "lesser" in order.

This may be confusing, but is not intended to exclude strict greater than operator.

what is the case where > doesn't satisfy strict weak ordering?

Some examples:

Overloaded operators that don't satisfy the properties.
> operator on pointers that do not point to the same array has unspecified result.
> does not satisfy irreflexivity requirement for floating point types in IEEE-754 representation unless NaNs are excluded from the domain.

Does satisfies strict weak ordering means that there's no need for == definition?

First thing's first. Defining operator < doesn't mean you get a definition of operator == for free from the compiler. It still needs to be defined explicitly.

The table above assumes something that is true for many types and ordering relations, but not for all. It assumes that equivalence between two elements implies equality. That need not hold.

We can certainly use < to check for equivalence between two elements. They are equivalent according to the strict week ordering (that's what !(a < b) && !(b < a) means). It doesn't necessarily mean those elements are equal.

A good example would be case insensitive comparison between strings of characters. In that case we will certainly have !("ab" < "AB") && !("AB" < "ab"), and the two string are equivalent, but they aren't equal in value.

Having said all that. If the order relation you defined implies all the other ones for your type, there are tricks to generate all the other operations from it. Just as the table demonstrates.

strict weak ordering confusion

If it "doesn't make sense" for one Airport to come before another Airport then the use of std::set<Airport> doesn't make sense, either. This container leverages the order amount elements to locate objects in O(log(n)) operations (where n is the size of the container). If you can identify object by identity only, the best complexity you can achieve is O(n). You can use a combination of std::find() or std::find_if() and one of the sequence containers, e.g., std::vector<Airport> or std::deque<Airport>.

Since you don't need to define an order in terms of operator<(), it may be reasonable to just bring the Airports into some order for the purpose of locating them in a std::set<Airport> which is done by using a different comparison function object than std::less<Airport>. The attribute you currently have in your Airport object don't really look like suitable keys, though. In fact, they all look as if they would be mutable, i.e., you probably wouldn't want a std::set<Airport> anyway because you can't modify the elements in an std::set<T> (well, at least, you shouldn't; yes, I realize that you can play tricks with mutable but this is bound to break the order of the elements).

Based on this, I'd recommend to use a std::map<std:string, Airport>: the std::string is used to identify the airport, e.g., using the airport codes like "JFK" for the John F. Kennedy Airport in New York or "LHR" for London Heathrow. Conveniently, there is already a strict weak order defined on strings.

That said, to define a strict weak order on a set of objects O, you need to a binary relation r(x, y) such that the following conditions hold for elements x, y, and z from O:

irreflexive: r(x, x) == false
asymmetric: r(x, y) == true implies r(y, x) == false
transitive: r(x, y) == true and r(y, z) == true implies r(x, z) == true
incomparability: r(x, y) == false and r(y, x) == false and r(y, z) == false and r(z, y) == false implies r(x, z) == false and r(z, x) == false

The first three should be simple enough. The last one is a bit odd at first but actually not that hard either: The basic idea is that the relation doesn't entirely order element but groups them into equivalent classes. If you think of the relation r to be "smaller than" it just says that if neither x is smaller than y nor y is smaller than x, then x and y are equivalent. The incomparable elements are just equivalent.

The standard containers work with a strict weak order but, e.g., std::set<T> and std::map<K, V> keep just one version of equivalent keys. It is nice that this is sufficient but it is often simpler to just use a total order which is a strict weak order where for each pair of element x and y either r(x, y) == true or r(y, x) == true (but, due to the asymmetry not both).

stl ordering - strict weak ordering

A partial order would not be sufficient to implement some algorithms, such as a sorting algorithm. Since a partially ordered set does not necessarily define a relationship between all elements of the set, how would you sort a list of two items that do not have an order relationship within the partial order?

Strict weak ordering operator in C++

You're missing the other side of the fitness check:

bool Chromosome::operator<(const Chromosome & rhs) const
{
    const Chromosome& lhs = *this;
    if (lhs.fitness < rhs.fitness)
        return true;
    else if (rhs.fitness < lhs.fitness)
        return false; // <== this!

Otherwise, if lhs.fitness > rhs.fitness, you're checking the vectors, when you shouldn't.

How do i sort mathematical vectors by strict weak ordering for a map?

It is mathematically impossible to use a tolerance with relational operators and yield a strict weak ordering. Any kind of convergence criterion will fail to satisfy ordering algorithms and data structures requirements. The reason is very simple: the incompatibility of two values, using a tolerance, doesn't yield an equivalence relation since it is not transitive. You may have almostEqual(a, b) and almostEqual(b, c) and yet ~almostEqual(a, c). Try this using a=1.0; b=2.0; c=3.0; tolerance=1.5;. You may look at this answer: Is floating-point == ever OK?.

You may still define an equivalence relation on floats using truncation, floor, roof, or round kind of functions. Let's define for example less3(a, b) if and only if floor(a * 8) < floor(b * 8) assuming a and b are binary floats and are not NAN and multiplications doesn't yield both the same signed infinite; this compares a and b using 3 bits of precision (0.125 in decimal). Now define equiv3(a, b) if and only if !less3(a, b) && ~less3(b, a). It can be shown that eqiv3(a, b) yields an appropriate equivalence relation. Since less3 is an order relation and equiv3 is an equivalence relation, then less3 is a strict weak order on floats (excluding NANs). Furthermore, in the case a * 8 == +INF && b * 8 == +INF || a * 8 == -INF && b * 8 == -INF you may fallback with ordinary < operator on floats.

Strict weak ordering on pointer values

Using std::less<Bar*> is sufficient (but using operator< is not). The pointer specializations of std::less (as the accepted answer to "Using std::less with nullptr" points out) guarantee a total ordering. Comparison with nullptr is unspecified, meaning the standard does not impose a particular ordering, but std::less must still produce a total ordering (and for a given pointer p, p < nullptr necessarily produces the same value every time).

Since a total ordering is stronger than a weak ordering, using std::less is sufficient in your case.

EDIT: If not what is the proper way (e.g. how to combine std::less with std::tie)?

There is no neat way, unfortunately. Since std::tie returns an std::tuple, and comparison on tuples is defined in terms of operator< on their values (rather than std::less), you can't really use std::tie here. To use std::less, you'd have to do it manually:

bool operator<(const Foo& rhs) const {
  if (std::less<>{}(x, rhs.x))
    return true;
  if (std::less<>{}(rhs.x, x))
    return false;
  return std::less<>{}(y, rhs.y);
}

As an aside, your current implementation (reinterpreting the pointers as integers) also produces a total ordering (obviously, since you're comparing integers) but instead of unspecified behavior you'll have implementation-defined behavior (from the reinterpret_cast).

How to force std::weak_ordering

... but how to force the compiler to do so?

When you use auto as the return type of defaulted operator<=>, the compiler will pick the common comparison category of all the members. So if you have something like:

// any type that is weakly ordered
struct Weak {
    bool operator==(Weak const&) const;
    std::weak_ordering operator<=>(Weak const&) const;
};

struct Foo {
    Weak w;
    int i;
    auto operator<=>(Foo const&) const = default;
};

Then using <=> on two instances of type Foo will give you a weak_ordering, since that's the common comparison category of Weak and int.

In the same way that given:

struct Bar {
    float f;
    auto operator<=>(Bar const&) const = default;
};

Bar::operator<=> gives you a std::partial_ordering.

There are no core language types that give you a std::weak_ordering, but there are some library types that might:

// some typical C++17 comparable type
struct Widget {
    bool operator==(Widget const&) const;
    bool operator<(Widget const&) const;
};

struct LotsOfWidgets {
    std::vector<Widget> widgets;
    auto operator<=>(LotsOfWidgets const&) const = default;
};

The <=> here returns std::weak_ordering (to avoid having to assume what it is you meant by < and ==).

Or you could simply provide that yourself. You don't have to use auto:

struct WeakInt {
    int i;
    friend std::weak_ordering operator<=>(WeakInt, WeakInt) = default;
};

Operator≪ and Strict Weak Ordering