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

Mathematics behind Comparison #1: Equality and Equivalence Relations

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 equality and equivalence relations. What does it mean for two objects to be equal? What are the mathematical properties and C++ semantics it needs to fulfill? How do I implement proper equality comparison in C++?

In the following parts we’ll look at ordering relations, the new three way comparison and algorithms like sorting and searching on various orderings.

» read more »
Author's profile picture Jonathan

A (Better) Taxonomy of Pointers

At C++Now 2018 I gave a talk about rethinking pointers: foonathan.net/cppnow2018.html.

I highly recommend you check it out, even if you watched the similar talk I gave at ACCU, as that version is a lot better. It rediscovers and discusses the common guidelines about when to use references over pointers, when smart pointers, etc.

If you’re an expert, you might get a deeper meaning from the structured analysis. And if you’re a beginner, you get the condensed guidelines.

However, I think the most valuable thing is the taxonomy of pointer types. It gives new vocabulary when talking about T* vs std::optional<T&> which gives the whole discussion an obvious answer.

And here is also the big problem: Naming is hard.

In particular, my naming of the taxonomy in the talk is bad, so let’s introduce new names.

» read more »
Author's profile picture Jonathan