Algorithm Design with Concepts, Ranges, and Projections

C++ algorithms concepts projections ranges

Introduction

In this post, we will use the well-known insertion sort algorithm as a case study in the design of generic algorithms. We will explore how concepts, ranges, and projections, introduced in C++20 and further developed in subsequent standards¹^,²^,³^,⁴, can be used to develop a flexible generic implementation of the algorithm, capable of operating on a variety of sequence containers such as std::vector and std::list. For readers unfamiliar with these features, we begin with brief working definitions, which will become clearer as we use them throughout the article:

A concept is a named compile-time predicate that defines a set of constraints on template arguments and can be used to restrict the interfaces of class and function templates, as well as to select the most appropriate function overloads and template specializations. These constraints are checked at compile time and generally provide clearer and more informative diagnostic messages when they are not satisfied. Beyond expressing syntactic requirements, concepts are intended to model meaningful semantic categories and properties that can be reused across generic code. Although concepts can express both syntactic and semantic requirements, compilers generally check only the former. Semantic requirements must generally be ensured by the programmer.

A range designates a sequence of elements, potentially unbounded, over which a computation is to be performed through iteration. It is specified by an iterator and a sentinel denoting the beginning and end of the computation, respectively. The sentinel need not have the same type as the iterator.

A projection is a transformation applied by an algorithm to an element before its value is inspected.

Insertion sort

Let R be a range to be sorted according to a given binary predicate comp, which must induce a strict weak ordering on the values being compared. That is, we assume that comp satisfies the following properties:

Irreflexivity: comp(a,a) is false for every a.
Transitivity: comp(a,b) and comp(b,c) imply comp(a,c).
If we define equiv(a,b) as !comp(a,b) and !comp(b,a), then equiv must also be transitive: equiv(a,b) and equiv(b,c) imply equiv(a,c).

Consequently, equiv partitions the elements into equivalence classes, on which comp induces a strict total ordering.

Let us assume that the range R contains at least two elements, denoted in order of occurrence by r₀, r₁, .... This notation does not imply random access. During its first iteration, insertion sort must order the first two elements of R, that is, if comp(r₁, r₀) evaluates to true, the two elements must be swapped; otherwise, they remain in their original positions. Next, we insert the third element, r₂ (if it exists), into the correct position within the already sorted subrange {r₀, r₁}. At this point, the first three elements of R are correctly ordered. We then insert the fourth element, r₃ (if it exists), into its proper position with respect to the already sorted subrange {r₀, r₁, r₂}, and so on until the entire range R has been sorted.⁵

The following figure shows, from left to right and from top to bottom, the successive iterations involved in sorting the sequence R = {5, 3, 1, 2} in ascending order:

Insertion sort remains useful for small sequences and performs particularly well on nearly sorted data. Its relative ease of implementation also makes it a convenient case study for generic algorithm design. For general-purpose sorting, however, a standard library algorithm such as std::ranges::sort will usually be a more appropriate choice. Interestingly, implementations of standard sorting algorithms commonly use insertion sort internally to handle small subranges.

Let us consider a half-open range R = [first, last) to be sorted using insertion sort, where first is an iterator of type I and last is a sentinel of type S (which need not be the same type as I, as we shall see in a later example). Let proj denote a projection to be applied to the elements of the range. It may, for example, be a function object or a pointer to a data member. As we have already mentioned, a projection allows the algorithm to apply transformations to range elements before comparing their values. This makes it possible, for instance, to sort objects according to the ordering of one of their data members. Let comp denote the binary predicate evaluated on the projected values of the range elements. The range R is said to be ordered with respect to comp and proj if, for every iterator i referring to one of its elements, std::invoke(comp, std::invoke(proj, *std::ranges::next(i, n)), std::invoke(proj, *i)) evaluates to false for every positive integer offset n such that std::ranges::next(i, n) still denotes a valid element of the range.

The use of the standard function template std::invoke is justified in this generic programming context by the variety of callable entities that may be used to represent comp and proj, including function objects, function pointers, and pointers to members.

We shall introduce the following interface for the insertion_sort algorithm, making the constraints imposed on its argument types explicit. In what follows, we will use the using namespace std; directive throughout the code to improve readability:

As we can see, we have specified a number of constraints both within the template parameter list (enclosed in angle brackets) and through the requires clause. In order of appearance:

The iterator type I must model at least the std::forward_iterator concept. In particular, it must be copyable and incrementable (++), dereferenceable when it denotes an element, and support multiple independent passes over the same range. Note that std::forward_iterator does not require the iterator to support modification of the elements it refers to; that requirement is imposed separately by std::permutable (see below).
The type S must model std::sentinel_for<S, I>, allowing a value of type S to denote the end of a range whose iterator type is I. In particular, S must be semiregular, and objects of types I and S must be weakly equality-comparable. One of its semantic requirements is that, whenever bool(first != last) evaluates to true, first must be dereferenceable, and incrementing it must leave [first, last) as a valid range. As noted before, S need not be the same type as I.
The types I, Comp, and Proj must jointly model the std::sortable concept⁶, which is defined as the conjunction of the concepts std::permutable and std::indirect_strict_weak_order (see the listing below). Among other requirements, std::permutable ensures that the iterator type supports the indirect movement, storage, and swapping of elements needed to rearrange them. Meanwhile, std::indirect_strict_weak_order requires the comparison predicate to induce a strict weak ordering on the projected elements.

The compiler can check that Comp can be used as a predicate and that the required expressions are well-formed, but it cannot verify the semantic requirements of a strict weak ordering (including irreflexivity, transitivity, and transitivity of the induced equivalence relation), which must therefore be ensured by the programmer.

Omitting namespace qualification for clarity, std::sortable is defined essentially as follows:

template<typename I, typename Comp, typename Proj> concept sortable = permutable<I> and indirect_strict_weak_order<Comp, projected<I, Proj>>;

Note that we do not require objects of type std::iter_value_t<I> to be copyable. Copyability would be a stronger requirement than necessary and would prevent the algorithm from supporting move-only types. We may wish, for example, to sort exclusive-ownership smart pointers such as std::unique_ptr according to the values of the objects they own, a case that we will examine later.

The default sorting policy adopted by the insertion_sort algorithm is provided by std::ranges::less, while the default projection is the function object type std::identity, whose operator() returns its argument unchanged.

When generating a specific instance of the function template, the compiler will verify that the supplied template arguments satisfy the stated constraints, issuing a meaningful diagnostic message otherwise. Our version of the algorithm can operate on a wide variety of iterators, including the forward iterators of std::forward_list, the bidirectional iterators of std::list, and the contiguous iterators of containers such as std::array and std::vector:

static_assert(forward_iterator<vector<int>::iterator> and forward_iterator<list<int>::iterator> and forward_iterator<forward_list<int>::iterator>);

Next, we shall implement the body of insertion_sort as a composition of well-known standard algorithms.⁷^,⁸^,⁹^,¹⁰ This provides a direct and concise formulation that supports forward ranges:

template< forward_iterator I, sentinel_for<I> S, typename Comp = ranges::less, typename Proj = identity > requires sortable<I, Comp, Proj> // ----------------------------- constexpr void insertion_sort(I first, S last, Comp comp = Comp{}, Proj proj = Proj{}) { // return immediately if the range length is <= 1: if constexpr (sized_sentinel_for<S, I>) { if (last - first <= 1) return; // (A) } else { if (first == last or ranges::next(first) == last) return; // (B) } for (I const i : views::iota(ranges::next(first), last)) { I const j = [&]{ if constexpr (bidirectional_iterator<I>) { auto rev = ranges::subrange{first, i} | views::reverse; return ranges::find_if_not( // (C) rev, [&](auto const& elem) { return invoke(comp, invoke(proj, *i), invoke(proj, elem)); } ).base(); } else { return ranges::upper_bound(first, i, invoke(proj, *i), comp, proj); // (D) } }(); ranges::rotate(j, i, ranges::next(i)); // (E) } }

First, we take into account that if the range to be sorted, [first, last) , is empty or contains only a single element, the algorithm can terminate immediately. The compiler selects the first branch (A) when S and I model std::sized_sentinel_for (as is the case, for example, for a pair of random-access iterators), in which case their distance can be obtained in constant time. Otherwise, the second branch (B) is used. This is typically the case, for example, with iterator pairs from std::list or std::forward_list.

At the beginning of each for loop iteration, the subrange [first, i) is sorted. The current element, denoted by i, is then inserted into its proper position, after which [first, std::ranges::next(i)) is sorted. To locate the insertion position j, we distinguish two strategies according to the capabilities of the iterator type:

I models std::bidirectional_iterator: the sorted subrange [first, i) is traversed in reverse order, starting from the element immediately preceding i. The std::ranges::find_if_not algorithm (C) stops as soon as it finds an element that the current element does not precede according to comp and proj. The base() member of the resulting reverse iterator then yields the position immediately after that element.
I is only a forward iterator: the std::ranges::upper_bound algorithm (D) performs a binary search on the sorted subrange [first, i) to locate the insertion position.

In either case, the resulting iterator j denotes a position after any previously processed elements equivalent to the current one according to comp and proj. More precisely, !bool(std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, *k))) evaluates to true for every iterator k in the subrange [first, j).

The std::ranges::rotate algorithm (E) then moves the element denoted by i to position j by means of a cyclic permutation of [j, std::ranges::next(i)).

It is worth noting, in particular, how every operation performed within the function body conforms exactly to the constraints imposed on its arguments. Also note that the comparator and projection objects are passed by value, consistently with the interfaces of the standard Ranges algorithms.

We shall also provide an overload of the algorithm that operates directly on a range, rather than on the iterator-sentinel pair used by the first version:

template< ranges::forward_range R, typename Comp = ranges::less, typename Proj = identity > requires sortable<ranges::iterator_t<R>, Comp, Proj> // ------------------------------------------------- constexpr void insertion_sort(R&& r, Comp comp = Comp{}, Proj proj = Proj{}) { insertion_sort(ranges::begin(r), ranges::end(r), move(comp), move(proj)); }

In this version, we require the type R to satisfy the std::ranges::forward_range concept and subsequently require the range iterator type std::ranges::iterator_t<R>, the comparator type Comp, and the projection type Proj to satisfy the std::sortable concept.

Example 1: Movable but non-copyable elements

The following code shows how the previous algorithm can be used to sort an array of movable but non-copyable elements, in this case std::unique_ptr<int> smart pointers. The comparator, defined as a lambda expression, takes two such pointers and dereferences them to establish the natural ordering of the integers they point to:

auto ptrs = array{ make_unique<int>(5), make_unique<int>(1), make_unique<int>(7), make_unique<int>(-2) }; insertion_sort(ptrs, [](auto const& p1, auto const& p2){ return *p1 < *p2; }); for (auto const& p : ptrs) { print("{} ", *p); } // output: -2 1 5 7

The memory layout of the array in the example would follow a scheme like the one below, before and after sorting, with ownership of the managed integers being transferred as the smart pointers are moved:

Alternatively, the array could be sorted using a projection that dereferences the pointers:

insertion_sort(ptrs, ranges::less{}, &unique_ptr<int>::operator*);

Example 2: Projections

As we have seen, projections allow the sorting algorithm to specify which value derived from each range element is to be used for comparison. As a further example, the following simple code sorts a vector of Book objects according to one of their public data members, price, using the std::ranges::greater function object to sort the books in descending order:

struct Book { string title; double price; }; auto books = vector<Book>{ {.title = "Romeo and Juliet", .price = 8.95}, { "The Count of Monte Cristo", 12.89}, { "War and Peace", 7.59}, { "Chronicle of a Death Foretold", 10.59}, { "A Study in Scarlet", 9.89} }; insertion_sort(books, ranges::greater{}, &Book::price); for (Book const& b : books) { println("title: {:<30} | price: {} €", b.title, b.price); } /* output: title: The Count of Monte Cristo | price: 12.89 € title: Chronicle of a Death Foretold | price: 10.59 € title: A Study in Scarlet | price: 9.89 € title: Romeo and Juliet | price: 8.95 € title: War and Peace | price: 7.59 € */

Example 3: Sentinels

The following example sorts a C-style null-terminated string and illustrates a situation in which the iterator type I (a char*) and the sentinel type S (named Zstr_sentinel) are different:

struct Zstr_sentinel{ }; constexpr auto operator==(char const* p, Zstr_sentinel /* unnamed */) noexcept -> bool { return *p == '\0'; }

char spell[] = "expelliarmus!"; auto rng = ranges::subrange{spell, Zstr_sentinel{}}; insertion_sort(rng); for (char const c : rng) { print("{}", c); } // output: !aeeillmprsux

Here, the null character belongs to the underlying array but acts as the end marker, and is therefore not part of the range being sorted. A more detailed explanation of the Zstr_sentinel type is available in the literature.¹¹

Example 4: Compile-time sorting

We will conclude this article by putting C++’s compile-time computation capabilities to the test once again. The reader will no doubt have noticed that the insertion_sort overloads have been declared constexpr. This allows them to be evaluated at compile time when invoked in a context that requires a constant expression.¹²

As an example, let us define the following Sorted_array<T, N, Comp, Proj> class template, which publicly inherits from std::array<T, N>. Given an array rvalue, a comparator, and a projection, the class constructor will store and sort the data by calling insertion_sort:

template<movable T, size_t N, typename Comp = ranges::less, typename Proj = identity> struct Sorted_array : array<T, N> { using Data = array<T, N>; constexpr explicit Sorted_array(Data&& entries, Comp comp = Comp{}, Proj proj = Proj{}) : Data{move(entries)} { insertion_sort(*this, move(comp), move(proj)); } };

Let us consider the following simple program:

constexpr auto entries = Sorted_array{array{5, 12, 7, -3, 1}, ranges::greater{}}; auto main() -> int { for (int const i : entries) { printf("%d\n", i); } }

The generated x86-64 assembly (compiled with GCC 16.2 using -O3 and -DNDEBUG) shows that the sorting of entries has been completed at compile time; its elements already appear in descending order, and no run-time sorting code is generated:¹³

.LC0: .string "%d\n" "main": push rbx xor ebx, ebx .L2: mov esi, DWORD PTR "entries"[rbx] mov edi, OFFSET FLAT:.LC0 xor eax, eax add rbx, 4 call "printf" cmp rbx, 20 jne .L2 xor eax, eax pop rbx ret "entries": .long 12 .long 7 .long 5 .long 1 .long -3

Remarkably, none of the machinery used to sort the array appears in the generated run-time code: the executable contains only the already sorted data and the instructions required to print it.

Interestingly, the Clang 23.1.0 compiler is able to unroll the for loop used for printing and produce a sequence of calls to printf.¹⁴ Such a transformation may improve execution speed in some circumstances, at the cost of increasing the size of the generated code:

main: push rbx lea rbx, [rip + .L.str] mov rdi, rbx mov esi, 12 xor eax, eax call printf@PLT mov rdi, rbx mov esi, 7 xor eax, eax call printf@PLT mov rdi, rbx mov esi, 5 xor eax, eax call printf@PLT mov rdi, rbx mov esi, 1 xor eax, eax call printf@PLT mov rdi, rbx mov esi, -3 xor eax, eax call printf@PLT xor eax, eax pop rbx ret .L.str: .asciz "%d\n"

Note: This post is a translated and expanded version of an earlier article that I originally published in Spanish on Blogger: Programando con C++20 (Parte I): Concepts.

Bibliography

cppreference.com - Constraints and concepts ↩
cppreference.com - Concepts library ↩
cppreference.com - Iterator library ↩
cppreference.com - Rages library ↩
Cormen T. H., et al., Introduction to Algorithms. 3rd Edition, MIT Press (2009). ↩
cppreference.com - std::sortable ↩
cppreference.com - std::ranges::find_if_not ↩
cppreference.com - std::ranges::upper_bound ↩
cppreference.com - std::ranges::rotate ↩
Stack Overflow - How to implement classic sorting algorithms in modern C++? ↩
foonathan::blog() - C++20’s Iterator Sentinels ↩
cppreference.com - Constant expression ↩
Compiler Explorer - Article’s code (compiled with GCC) ↩
Eric Niebler - Quicksort of an array of ints at compile-time using C++17 constexpr ↩