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 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
impliesr(y, x) == false
- transitive:
r(x, y) == true
andr(y, z) == true
impliesr(x, z) == true
- incomparability:
r(x, y) == false
andr(y, x) == false
andr(y, z) == false
andr(z, y) == false
impliesr(x, z) == false
andr(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;
};
Related Topics
Most Efficient Way to Compare a Variable to Multiple Values
How to Fully Disable Resizing a Window Including the Resize Icon When the Mouse Hovers the Border
Why Use Apparently Meaningless Do-While and If-Else Statements in Macros
Is There a Difference Between Copy Initialization and Direct Initialization
Forcing the Qt Gui to Update Before Entering a Separate Function
What Is an Undefined Reference/Unresolved External Symbol Error and How to Fix It
Why Is Iostream::Eof Inside a Loop Condition (I.E. 'While (!Stream.Eof())') Considered Wrong
Can a Local Variable'S Memory Be Accessed Outside Its Scope
Undefined, Unspecified and Implementation-Defined Behavior
Why Aren't Variable-Length Arrays Part of the C++ Standard
What Should Main() Return in C and C++
What Are Forward Declarations in C++
Why Do I Have to Access Template Base Class Members Through the This Pointer
How to Print Function Pointers With Cout