﻿ Operator≪ and Strict Weak Ordering - ITCodar

# 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 2if (a2 < b2)  return true;if (b2 < a2)  return false;// a2 == b2: continue with element 3if (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.

 removed wrong code

 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 `Airport`s 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 orderedstruct 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 typestruct 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;};``