C++ Concepts: More than Syntactic Requirements

Published February 26, 2021

After years and years of expectation, concepts have finally made it in C++20.

Concepts are descriptions in code of a set of expressions that must be valid with a given type. Those are syntactic requirements. But there is more to concepts than that: concepts also have semantic requirements.

Before getting into that, here is a recap of what concepts are. If you’re already familiar with concepts you can skip to the section on semantic requirements.

A summary of concepts

To understand what concepts are, we need to take a step back and talk about polymorphism.

C++ offers various ways to achieve polymorphism, that is to describe an interface and then implement this interface with various implementations.

Runtime polymorphism: virtual methods

The first thing that usually comes to mind when thinking about polymorphism is inheritance and virtual methods. In this case, a base class describes the interface, and derived class implement the virtual methods of that base class in order to provide an implementation:

class Interface
{
public:
    virtual void feature1(int input) = 0;
    virtual int feature2() const = 0;
    
    virtual ~Interface() = default;
};

class Implementation1 : public Interface
{
    void feature1(int input) override;
    int feature2() const override;
};

class Implementation2 : public Interface
{
    void feature1(int input) override;
    int feature2() const override;
};

A function can then use any implementation of the interface by working with a pointer or reference of the interface:

void f(Interface const& interface)
{
    // ...

This is called runtime polymorphism because the actual implementation behind a given reference of the interface is discovered when the program is running, typically by using virtual tables.

But there are also other types of polymorphism in C++. One of them is compile-time polymorphism, and it can be implemented with templates.

Compile-time polymorphism with templates

Consider any algorithm of the STL. Let’s take for example std::sort, that has a very simple prototype:

template<typename RandomIterator>
void sort(RandomIterator first, RandomIterator last);

The design of the STL makes it so that we can use std::sort with various types of containers, as long as they provide random-access iterators. Typically std::vector, and less commonly std::deque:

auto myVector = std::vector<int>{3, 1, 4, 2, 5, 2};
std::sort(begin(myVector), end(myVector));

auto myDeque = std::deque<int>{3, 1, 4, 2, 5, 2};
std::sort(begin(myDeque), end(myDeque));

On the other hand, std::sort doesn’t work on iterators that are not random-access:

auto myList = std::list<int>{3, 1, 4, 2, 5, 2};
std::sort(begin(myList), end(myList)); // doesn't compile

This means that std::sort accepts various types, as long as they comply by certain rules, in the case being a random-access iterator.

We can draw a parallel with the runtime polymorphism implemented with inheritance: std::sort also implements polymorphism, because it only works with types that have a certain set of capabilities.

This is a different kind of polymorphism. It is called compile-time polymorphism, because the type implementing the “interface” of a random-access iterator is discovered at compile-time.

An implicit interface

Here are the most notable differences between compile-time and runtime polymorphism:

	Compile-time polymorphism	Runtime polymorphism
Time of resolution	Compilation	Execution
Polymorphic entity	Type	Object
Interface expressed by	typename (implicit)	Base class (explicit)

As the last line of this table notes, runtime polymorphism allows to describe an interface in the base class, whereas compile-time polymorphism does not allow to describe an interface in code.

Indeed, the code just says typename, which means that a type is expected. But it doesn’t tell what this type should be able to do. It is only when compiling the code of the template that the compiler will stop if the type doesn’t provide the needed interface. Put another way, the interface of compile-time polymorphism is implicit.

C++ concepts change that: they allow to describe in code what a type should be able to do in order to be accepted as a template parameter of a certain function.

For instance, C++20 provides a std::random_access_iterator concept that describes what is expected of a random access iterator:

template<class I>
concept random_access_iterator =
bidirectional_iterator<I> &&
derived_from<ITER_CONCEPT(I), random_access_iterator_tag> && totally_ordered<I> &&
sized_sentinel_for<I, I> &&
requires(I i, const I j, const iter_difference_t<I> n) {
    { i += n } -> same_as<I&>;
    { j + n } -> same_as<I>;
    { n + j } -> same_as<I>;
    { i -= n } -> same_as<I&>;
    { j - n } -> same_as<I>;
    { j[n] } -> same_as<iter_reference_t<I>>;
};

Let’s focus on the requires clause of the above definition: it describes with precision what the type is expected to be able to do in order to be considered a random-access iterator. The requires clause describes syntactic requirements for a type.

We could then rewrite the prototype of std::sort this way:

template<std::random_access_iterator RandomIterator>
void sort(RandomIterator first, RandomIterator last);

As it happens, the STL in C++20 does not use std::random_access_iterator in the interface of std::sort, nor any iterator concept in any prototype of any STL algorithm.

Instead, C++20 provides the Ranges library, that provides the range version of STL algorithms which are superior to the old version of STL algorithms (for various reasons outside of our purpose here). And range algorithms use range concepts, that are based on iterator concepts such as std::random_access_iterator.

Semantic requirements

I had long believed that concepts would be just that. But there is another part of concepts and that remains implicit: semantic requirements.

Semantic requirements are what we expect from a type, but that we cannot express with an expression in a requires clause.

For example, random access iterators have a semantic requirement: their operations must be in constant time. Consider std::vector‘s iterators for example: you can indeed increment them of any number of positions in constant time.

This requirement is vital for std::sort. Indeed, std::sort guarantees the complexity of O(N·log(N)) comparisons, where N is the size of the collection to be sorted. This complexity can only be achieved by moving around the collection in constant time.

This kind of constraint cannot be expressed in C++ code. Therefore it cannot be part of the requires clause. But it is still part of the concept. Indeed, here is what the standard says (emphasis mine): “The random_access_iterator concept adds support for constant-time advancement with +=, +, -=, and -, as well as the computation of distance in constant time with -. [iterator.concept.random.access]”

Concepts allow to express your intentions

Concepts allow to write more expressive code, by explicitly stating the intentions of a prototype regarding a type that it uses.

They allow to express those intentions both to the compiler, that would politely reject the code that doesn’t satisfy the concept’s syntactic requirements, and also to other human developers reading the code.

An interesting aspect of concepts is then that they arguably convey more to humans than to compilers, since compilers can’t pick up the semantic requirements, whereas by writing the name of the concept in a prototype, you express to other humans what exactly you expect from a type, including its semantic requirements.