Mathematics behind Comparison #5: Ordering Algorithms

In order to sort a collection of elements you need to provide a sorting predicate that determines when one element is less than the other. This predicate must “induce a strict total ordering on the equivalence classes” according to cppreference. Wait, what?

The upcoming C++ spaceship operator implements a three-way comparison, i.e. it is a single function that can return the results of <, == and > combined. But related to it are terms like “strong equality” and “weak ordering” which are somewhat confusing if you don’t have the mathematical background.

So let’s untangle it: This series will explain both the mathematics behind equality and ordering, as well as give concrete guidelines for implementing the comparison operators and the spaceship operator.

To finish this series let’s talk about algorithms that require an ordering and how they can be implemented using three-way comparison.

» read more »
Author's profile picture Jonathan

Mathematics behind Comparison #4: Three-Way Comparison

In order to sort a collection of elements you need to provide a sorting predicate that determines when one element is less than the other. This predicate must “induce a strict total ordering on the equivalence classes” according to cppreference. Wait, what?

The upcoming C++ spaceship operator implements a three-way comparison, i.e. it is a single function that can return the results of <, == and > combined. But related to it are terms like “strong equality” and “weak ordering” which are somewhat confusing if you don’t have the mathematical background.

So let’s untangle it: This series will explain both the mathematics behind equality and ordering, as well as give concrete guidelines for implementing the comparison operators and the spaceship operator.

Now that we’ve covered both equivalence and ordering relations we can finally talk about the spaceship operator and three-way comparisons.

» read more »
Author's profile picture Jonathan

Mathematics behind Comparison #3: Ordering Relations in C++

In order to sort a collection of elements you need to provide a sorting predicate that determines when one element is less than the other. This predicate must “induce a strict total ordering on the equivalence classes” according to cppreference. Wait, what?

The upcoming C++ spaceship operator implements a three way comparison, i.e. it is a single function that can return the results of <, == and > combined. But related to it are terms like “strong equality” and “weak ordering” which are somewhat confusing if you don’t have the mathematical background.

So let’s untangle it: This series will explain both the mathematics behind equality and ordering, as well as give concrete guidelines for implementing the comparison operators and the spaceship operator.

The previous part was very math heavy but necessary: It introduced the mathematical terminology for ordering relations. With that done we can finally talk about how it applies to C++.

» read more »
Author's profile picture Jonathan

Mathematics behind Comparison #2: Ordering Relations in Math

In order to sort a collection of elements you need to provide a sorting predicate that determines when one element is less than the other. This predicate must “induce a strict total ordering on the equivalence classes” according to cppreference. Wait, what?

The upcoming C++ spaceship operator implements a three way comparison, i.e. it is a single function that can return the results of <, == and > combined. But related to it are terms like “strong equality” and “weak ordering” which are somewhat confusing if you don’t have the mathematical background.

So let’s untangle it: This series will explain both the mathematics behind equality and ordering, as well as give concrete guidelines for implementing the comparison operators and the spaceship operator.

This part covers the mathematics behind ordering relations. They are a lot more complicated than equivalence relations we’ve looked at before. As my blog posts are usually long anyway, I’ve decided to split it into two. So this part is only about the mathematics while the next part—already published—is about how they should be implemented in C++.

» read more »
Author's profile picture Jonathan

Let's Talk about std::optional and optional references

This should have been part 2 of my comparison series, and I have almost finished it, but due to university stuff I just haven’t found the time to polish it.

But the optional discussion started again, so I just wanted to really quickly share my raw thoughts on the topic. In case you are lucky and don’t know what I mean: std::optional<T&> doesn’t compile right now, because the behavior of assignment wasn’t clear (even though it actually is). There are basically four questions in the discussion I want to answer:

  1. Is std::optional<T&> the same as a pointer?
  2. Do we need std::optional<T&>?
  3. Should the assignment operator rebind or assign through?
  4. Should it even have an assignment operator?

tl;dr: no, I don’t, rebind, no.

» read more »
Author's profile picture Jonathan