Mathematics behind Comparison #5: Ordering Algorithms

01 Oct 2018 by Jonathan

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.

Note: The C++ language rules for <=> have changed since writing this post. See https://jonathanmueller.dev/talk/cppcon2019/ for the current rules. This blog post is outdated.

Implementation Helpers

The standard library has a couple of algorithms and classes that require an ordering, like std::sort() or std::set. But this ordering is implemented by passing it a predicate that defines the operator<, i.e. it returns true if the first argument is considered less than the second one. And the type std::less is the default predicate that just uses the operator<.

We want to implement them using three-way comparisons, i.e. with a predicate that returns one of the _ordering types from C++20 (read the previous part). This makes it somewhat easier to use in the algorithms.

Then our default_ordering is this little class:

struct default_ordering
{
    template <typename T, typename U>
    auto operator()(const T& lhs, const U& rhs) const noexcept
    {
        return std::compare_3way(lhs, rhs);
    }
};

As discussed before, the generic spelling of “three-way comparison” is std::compare_3way, not operator<=>.

I’ve also made two changes compared to std::less: First, the ordering itself is not a template but the member function. This allows comparing two different types with each other. C++14 added std::less<> (where T defaults to void) which looks like that as well.

And second, I’ve made it unconditionally noexcept because comparison shouldn’t throw.

In the standard library we can use std::greater instead of std::less if we want to reverse the ordering. Here a reverse_ordering looks like this:

struct reverse_ordering
{
    template <typename T, typename U>
    auto operator()(const T& lhs, const U& rhs) const noexcept
    {
        auto result = std::compare_3way(lhs, rhs);
        switch (result)
        {
        // swap less and greater
        case std::partial_ordering::less:
            return std::partial_ordering::greater;
        case std::partial_ordering::greater:
            return std::partial_ordering::less;

        // don't change if equivalent or unordered
        default:
            return result;
        }
    }
};

With the new three-way comparisons there are also multiple kinds of orderings. Let’s write some predicates to ensure a certain one when we need it:

template <class Ordering, typename T, typename U>
using ordering_category = std::decay_t<decltype(std::declval<Ordering>()
                                            (std::declval<T>(), std::declval<U>()))>;

template <class OrderingCategory>
struct is_strong_ordering
: std::is_convertible<OrderingCategory, std::strong_ordering>
{};

template <class OrderingCategory>
struct is_weak_ordering
: std::is_convertible<OrderingCategory, std::weak_ordering>
{};

template <class OrderingCategory>
struct is_partial_ordering
: std::is_convertible<OrderingCategory, std::partial_ordering>
{};

We have a little helper that gives us the ordering category returned by an Ordering of T and U and then some traits for the three orderings. Due to the implicit conversions is_partial_ordering is also true if the ordering is a strong ordering, etc.

And I’ve used std::is_convertible for strong orderings even though std::is_same would be sufficient currently. But as people did that with std::random_access_iterator_tag there can’t be a std::contiguous_iterator_tag now because that would only be convertible to it.

So let’s implement some algorithms. You’re going to notice that most algorithms don’t actually need to have the full relationship between two objects, only whether one is less than the other.

But then it surely is more efficient to pass a predicate that only calculates that information?

In the general case, it isn’t (much). On the assembly level, there is one instruction for a three-way comparison of integers that simply does a subtraction, then the sign is the answer. Likewise, std::strcmp() also does a three-way comparison. And LLVM has optimizations that detect three-way comparison where we only care about one result and optimize them accordingly.

When you only want equality, asking for the full relationship is more expensive, however! Because when you just want to have equality of two containers, you can immediately return false when they have different sizes. A three-way comparison has to compare them element by element for the lexicographical ordering.

Finding Maximal and Minimal Elements

Our task is simple: Given some sequence of elements we want to find the element that is the “biggest/smallest one” according to a given ordering relation. But first, let’s define “biggest one” a bit more precisely. For that you have to read part 2 first.

If we have a set of values S and some ordering for that set, we say that an element m ∈ S is a maximal element if it is not less than any other element s ∈ S. So if the ordering is a ≤-ordering, m ≤ s is only true if s ≤ m is true as well, i.e. the elements are equivalent. And for a <-ordering, m < s is not true. Likewise, m' ∈ S is a minimal element if it is not greater than any other element s ∈ S.

Now whenever you encounter a definition that talks about some special elements of a set, there are two questions you need to think about:

Does this element always exist?
Can there be multiple elements with that property?

We can immediately answer question one with a “no”: The set of all numbers is infinite on both ends, so there is no maximal or minimal element. However, those sets don’t matter for programming, as we do not have infinite memory anyway, so all sets are finite.

But are there (non-empty) finite sets without a maximal (minimal) element?

The good answer is: no, there aren’t. Every non-empty finite set has a maximal and minimal element, so our algorithm can always return something.

And the second question can also be answered with “no” pretty much immediately: What if we have a maximal element in there multiple times? Or what if we have an ordering where we don’t have true equality and the maximal element is equivalent to multiple other elements?

So let’s narrow that question: can there be multiple non-equivalent maximal elements? For the purposes of our algorithms equivalent elements are “equal” for all intents and purposes; a weak ordering is as good as a strong ordering.

And you might be tempted to say no to that question: If the maximal element isn’t less than all other elements, no element can be greater! And this is true … for a (strict) total order. A finite set of numbers will always have exactly one maximal element, the highest number.

With a total ordering “not less” means “greater or equivalent”. But when we have a partial ordering “not less” can also mean “incomparable”.

Consider the set of sets {ø, {1}, {2}}, i.e. the empty set, the set containing 1 and the set containing 2. As seen before, the subset relation ⊆ is a partial order. Furthermore, {1} is a maximal element as ø ⊆ {1} and not {2} ⊆ {1}, so {1} is not smaller than another element. But {2} is a maximal element for the same reason! Neither {1} or {2} is smaller than the other as they are incomparable, so both are maximal elements.

So for a finite set we are always going to have at least one maximal/minimal element but in the case of a partial order we might have multiple non-equivalent elements.

If we have only one maximal (minimal) element we give it a special name: m ∈ S is the greatest element if it is greater than or equivalent to all other elements. Then the condition is slightly different: s ≤ m must be true for all s ∈ S. Likewise, the least element is less than or equivalent to all other elements.

Not every set has a greatest element, as we’ve seen, but if we have one, we have only one. And when we have a total ordering, there can only be one maximal element so we will always have one. The greatest element of a totally ordered set is also called the maximum, the least element the minimum.

So we need an algorithm that finds all maximal elements, one that finds the greatest element if there is one, and one that finds the maximum element for a total ordering.

The standard library algorithm std::max_element() actually returns the greatest element of the of the sequence. As the comparison predicate must define a strict weak ordering which is a total ordering, there is always one (or the sequence is empty).

It is called max_ because of “maximum”, not “maximal”. Naming.

So let’s start with it first:

template <typename ForwardIt, class Ordering>
ForwardIt maximum(ForwardIt begin, ForwardIt end, Ordering order)
{
    // we need a total ordering, i.e. at least `std::weak_ordering`
    static_assert(is_weak_ordering<decltype(order(*begin, *begin))>::value);

    if (begin == end)
        return end;
    
    // the first one is the maximum so far
    auto maximum = begin;
    for (cur = std::next(begin); cur != end; ++cur)
    {
        if (order(*maximum, *cur) < 0)
            // found an element that is bigger
            maximum = cur;
    }

    return maximum;
}

template <typename ForwardIt>
ForwardIt maximum(ForwardIt begin, ForwardIt end)
{
    return maximum(begin, end, default_ordering{});
}

This is the standard algorithm, nothing special here. It will return an iterator to the maximum, or end if the sequence is empty. The version without an ordering just passes our default_ordering.

The algorithms for a partial ordering are more interesting as there can be more than one maximal element. So the result is actually a container of iterators:

template <typename ForwardIt, class Ordering>
std::vector<ForwardIt> maximal_elements(ForwardIt begin, ForwardIt end, Ordering order)
{
    std::vector<ForwardIt> result; // the candidates
    for (auto cur = begin; cur != end; ++cur)
    {
        // remove all candidates that are less than the current one 
        auto new_result_end = std::remove_if(result.begin(), result.end(),
                [&](ForwardIt iter) { return ordering(*iter, *cur) < 0; });
        result.erase(new_result_end, result.end()); 

        // insert current one if it is not less for all candidates
        auto is_maximal = std::all_of(result.begin(), result.end(),
                [&](ForwardIt iter) { return ordering(*cur, *iter) != std::partial_ordering::less; });
        if (is_maximal)
            result.push_back(cur);
    } 
    return result;
}

This algorithm is more complicated. We’re now having a container of elements that are maximal so far. The candidates are removed if we found an element that is greater than them, and we’re adding a new element if it is not less than all of them.

Note that “not less” is spelled ordering(*cur, *candidate) != std::partial_ordering::less or !(ordering(*cur, *candidate) < 0) but not ordering(*cur, *candidate) >= 0. The last one is false for std::partial_ordering::unordered even though that’s the case that is perfectly fine!

Further note that this is a quadratic algorithm. But you can’t do better than that: In the extreme case no elements are comparable but to determine that you have to compare every element with every other.

And finally the greatest_element() algorithm is simply:

template <typename ForwardIt, class Ordering>
ForwardIt greatest_element(ForwardIt begin, ForwardIt end, Ordering order)
{
    auto maximals = maximal_elements(begin, end, order);
    if (maximals.size() == 1)
        return maximals.front();
    else
        return end;
}

If we have exactly one maximal element we return that, otherwise we return end.

The minimal version and optimizations (i.e. use maximum() in maximal_elements() if we have a total ordering) are left as an exercise for the reader.

Sorting Elements

Given a sequence of elements and an ordering we might also want to order the elements according to that ordering, sort them. For orderings that are total there is only one way to do that and you’re all familiar with algorithms that do that, so I’m not discussing it further. But for partial orderings it is more interesting as they have elements that are not comparable: There are two ways to order them relative to each other and both are correct!

However, you’ll probably also know an algorithm to sort a sequence with a partial order. We can treat it as a directed graph: The vertices are the elements of our sequence and there is an edge from a to b if a ≤ b. Then we can do a topological sort on the graph. The result is an order of the vertices where a will come before b if they are connected, i.e. if a ≤ b.

Sadly, there’s a catch: a topological sort may not always succeed, it doesn’t handle cycles in the graph.

But consider a potential cycles of vertices a, b and c where a ↦ b, b ↦ c and c ↦ a. It means that a ≤ b and b ≤ c and c ≤ a. So by the transitive property also b ≤ a and c ≤ b, which means that the vertices are equivalent.

And this makes sense: The topological sort can’t order them, because there is no unique way to order them; they’re all equivalent.

I won’t write any code here (because I want to get this blog post out today), but the plan to sort using a partial sort is as follows: Construct a graph, then topological sort them. If there are cycles insert all elements of the cycles directly one after the other.

The complexity of a topological sort is usually linear in both vertices and edges but the construction of the graph is quadratic in the general case. In order to know the elements that are greater than a given element we have to check all of them.

Searching in a Sorted Sequence

Once we have a sorted sequence we can search for a particular element using a binary search. The algorithm compares the middle element with the target element:

If they’re equivalent, we’re done.
If the middle is less, we look in the second half and repeat.
If the middle is greater, we look in the first half and repeat.

This directly means that the algorithm only works on a total ordering: If the middle element is not comparable with the target we don’t know where to look!

And note that we don’t actually need a sorted sequence: It is sufficient that we’ve got all elements less than the target, followed by the target, followed by all elements greater than the target. The actual order of the elements less than or greater doesn’t matter.

A simple implementation of std::lower_bound(), which returns the first iterator not less than the target, can look like this:

template <typename ForwardIt, typename T, typename Ordering>
ForwardIt lower_bound(ForwardIt begin, ForwardIt end, const T& target, Ordering order)
{
    // we need a total ordering
    static_assert(is_weak_ordering<decltype(order(*begin, target))>::value);

    auto length = std::distance(begin, end);
    while (length != 0)
    {
        // get the middle element
        auto half_length = length / 2;
        auto mid         = std::next(begin, half_length);

        if (order(*mid, target) < 0)
        {
            // less than, look at the second half
            begin = std::next(mid);
            length -= half_length + 1;
        }
        else
            // greater, look at the first half
            length = half_length;
    }
    return begin;
}

Here we can use the fact that our default_ordering can take arguments of two different types: We could have a sequence of std::string and look for a const char*. The comparison can be done without creating a temporary std::string object each time.

So let’s finally talk about mixed-type comparison as we’ve only really looked at a comparison for the same type so far. Remember, mathematically an ordering is defined on a set of values and C++ types have a given set of values.

For a mixed-type comparison the two types must have the same set of values or there must be a mapping between the sets. An example of the first category would be std::string and std::string_view — they both represent “strings” so have the same set of values. An example of the second category would be std::chrono::seconds and std::chrono::milliseconds, while they represent different things, you can easily convert between them to create a common set of values. std::string and const char* is more interesting because a const char* could also simply be a pointer to char which then has a different set of values. But because the common meaning is “C string” a comparison has been defined that uses that representation.

Rule: Create a mixed-type comparison if the two types are implicitly convertible to each other but the conversion would be too expensive.

Conversion is a good indicator that your types have the same set of values or compatible ones. And I can simply defer to the guidelines for constructor and cast design. The comparison between std::string and const char* follows that rule.

Rule: Create a mixed-type comparison if the two types are explicitly convertible but would be implicitly convertible if the conversion wasn’t so expensive.

This is the std::string_view to std::string conversion. It is only explicit because it would be too expensive. But comparisons don’t need to convert so they should be convertible.

Ordered Containers

Finally, let’s look at a std::set-like container implemented using three-way comparison. The implementation is straightforward, just change your predicates slightly. But the design is a bit more interesting.

First, I’d argue that we don’t want this:

template <typename T, class Ordering = default_ordering>
class ordered_set;

If the default is default_ordering we can only use types that have implemented the comparison operators without specifying a custom predicate. And I’ve argued before that most types should not have them which would make it annoying.

For example, std::complex cannot provide a default ordering that makes mathematical sense. However, to do a log n lookup with a binary search it just needs some ordering: it doesn’t need to make sense.

So I propose that it should use a new default, key_ordering:

template <class Key>
struct key_ordering
{
    template <class U>
    std::weak_ordering operator()(const Key& key, const U& lookup) noexcept
    {
        return default_ordering{}(key, lookup);
    }
};

This is now a template and it defaults to default_ordering. But a type can specialize it to provide a different ordering, just for the purposes of lookup. std::complex would want to do that, for example.

But std::vector could also specialize that and provide an ordering where the containers are first sorted by length and only then by contents. This is a well-defined ordering but not the one you intuitively expect, so it shouldn’t be the operator< implementation. It is a lot faster if most containers have a different number of elements, so would be preferable to operator< (unless you need the specific order).

I’ve also hard-coded the result to std::weak_ordering: binary search doesn’t work with a partial ordering.

We still keep the template for the second parameter to allow the lookup of std::string with const char*, for example. A customization can restrict the types there. Since C++14 this is also supported by std::set and is called “transparent comparison”. A custom comparator explicitly has to opt-in for that though.

An example of a set using this mechanics is my flat_set from foonathan/array. The ordering interface is slightly different at the moment but I’m going to adapt it.

Conclusion

Writing algorithms using three-way comparison isn’t too different from writing them using the normal comparison predicates. But the additional categories are nice to provide some more generic algorithms or express requirements more naturally.

Switching to three-way comparisons is also an opportunity to introduce a new key_ordering specifically designed for ordered sets and maps. This ordering doesn’t need to make sense, so it can be faster and introduced for types without any ordering.

The only downside of using three-way comparison is the additional cost for algorithms that just want equality. They should still be written based on operator==.

If you’ve liked this series, please let me now. I might write about the mathematics behind other operators as well.

This blog post was written for my old blog design and ported over. If there are any issues, please let me know.