Chapter 4.6. T.10: Specify concepts for all template arguments
How did we get here?
Concepts are one of the big-ticket items of C++20. They have taken a long, long time to make their way into the standard. The first attempt at standardizing them started after C++98 and a version of concepts nearly made it into C++11, or C++0x as it was being called at the time. However, concepts were withdrawn from the working draft at the eleventh hour and put into a Technical Specification (TS). Technical Specifications are used to gather implementation experience. The Concepts TS was published at the end of 2015 allowing compiler implementers to kick the tires and check the roadworthiness of the feature.
C++17 hit feature freeze during 2016, at which point concepts were insufficiently proven for safe addition to the language. However, at the first committee meeting of the C++20 delivery cycle, in Toronto in the summer of 2017, motion 11, “Move to apply the changes in P0734 (Wording Paper, C++ extensions for Concepts) to the C++ working paper,” was passed to joyous applause.
As an aside, this was my first committee meeting. I had attended study group meetings before, and national body meetings, but this was the first time I had put myself in the same room as the people who shape the standard. Concepts were not the only thing to make significant advance. Motion 12 advanced Modules for balloting among the national bodies, motion 13 advanced the Coroutines TS and motion 22 appointed an editing committee, including me, to verify the correctness of the Ranges TS. Clearly C++20 was going to be a great leap forward. This was not what I was expecting for my first visit, but history is made by those who turn up. Should you ever find yourself at your first committee meeting, come and find me and then volunteer for everything.
Returning to concepts, let’s consider the problem they are trying to solve by examining the following function template:
template <typename T>
T const& lesser(T const& t1, T const& t2) {
return t1 < t2 ? t1 : t2;
}
With any luck, you have never written this code before and always used std::min from the <algorithm> header. We have used the name lesser since min is enormously overloaded in every implementation.
The tricky part is that this function can only be invoked with certain types: if you pass a couple of std::unordered_map<string, string> references to this function, the compiler will tell you in no uncertain terms that this is not going to fly. There is no match for operator< with these operand types. The error output is a little verbose, but we can see what is going on. Here is an edited sample of some error output from GCC:
<source>: In instantiation of 'const T& lesser(const T&, const T&)
[with T = std::unordered_map<int, int>]':
<source>:14:31: required from here
<source>:6:15: error: no match for 'operator<' (operand types are
'const std::unordered_map<int, int>' and 'const std::unordered_map<int, int>')
6 | return t1 < t2 ?t1 : t2;
| ~~~^~~~
In file included from …:
<filename>:1149:5: note: candidate:
'template<class _IteratorL, class _IteratorR, class _Container>
bool __gnu_cxx::operator<(
const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&,
const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)'
1149 | operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
| ^~~~~~~~
This is saying that while trying to instantiate the function template lesser, using std::unordered_map<int, int> as the template parameter, the compiler could see no available operator<. Then it lists all the candidate operators (I stopped at one, but when I tried this in Compiler Explorer it listed quite a lot of candidates) to demonstrate that there was nothing available.
This simple error, in this four-line function, produced 122 lines of error output. As you scale up to more likely functions, this error output increases considerably, and it becomes ever harder for you to identify what the root cause of the problem is. If there is a hefty call stack of function templates between your first instantiation and the error, you may spend quite a while spelunking through the output.
This problem has always been with us, but there are ways of mitigating it. While it is infeasible to overload your function for every conceivable type, you could overload for a set of types using std::enable_if. You have to really hate yourself and your coworkers to do this, but it looks like this:
template <typename T,
std::enable_if_t<std::is_arithmetic<T>::value, bool> = true>
T const& lesser(T const& t1, T const& t2);
The name std::is_arithmetic lives in the <type_traits> header, along with a selection of other traits like std::is_const and std::is_trivially_constructible. This overload will be selected for any arithmetic type (integral or floating point). This is not immediately apparent unless you are familiar with this idiom. I consider this “expert-level” programming; when I am teaching, I leave this until my students are completely familiar with default template parameters and the principle of Substitution Failure Is Not An Error, or SFINAE.
We won’t go into detail about this technique here. We can do better now.
Constraining your parameters
The problem with the std::enable_if idiom is that it is a verbose, library-level way of constraining your function. The constraint is camouflaged inside a soup of punctuation that looks like transmission line noise. The important part of the constraint is the name std::is_arithmetic. The rest is simply scaffolding to overcome the shortcomings of the language.
What you really want to be able to say is something like
template <typename std::is_arithmetic T> T const& lesser(T const& t1, T const& t2);
This syntax is clearer. The constraint is right next to the type. Unfortunately, it is not valid C++. It is ambiguous to parse and becomes cluttered if there is more than one constraint to apply. Let’s try another version:
template <typename T> where std::is_arithmetic<T>::value T const& lesser(T const& t1, T const& t2);
The constraint gets its own line between the template introduction and the function name. Neither is this valid C++: the keyword where is rather too reminiscent of SQL, so we substitute requires, like this:
template <typename T> requires std::is_arithmetic_v<T> T const& lesser(T const& t1, T const& t2);
This is now valid C++20. If we want something a little more constrained, we can simply add constraints to the requires clause, like this:
template <typename T> requires std::is_trivially_constructible_v<T> and std::is_nothrow_move_constructible_v<T> T f1(T t1, T t2);
You might pause at the use of the word “and” in that example. If it’s a logical conjunction, wouldn’t && be more appropriate?
It’s a matter of taste and style. You can use both. If you want to use punctuation rather than “and” you are entirely able so to do. However, I find unambiguous English clearer than symbols.
This syntax still looks quite busy. The template introduction is required to highlight that the declaration is a function template, but the presence of constraints also implies that the declaration is a function template. Do we really need both? Can’t we have a syntax like:
T f2(std::is_arithmetic<T> t1, std::is_arithmetic<T> t2);
That looks to me like a function that takes a type that must be arithmetic. Unfortunately, again we have a parsing problem. The first instance of T looks like a definition, not a return type. It comes out of nowhere, but we can replace it with auto since this is a function template and we can safely assume the definition is visible and implies the return type. The subsequent uses of T also pose a problem. How do we signify that we are passing a constrained type?
C++14 introduced the notion of generic lambda expressions. Rather than specify a type for each parameter, you could specify auto instead and let the compiler infer the type. We can use the same form here:
auto f3(std::equality_comparable auto t1, std::equality_comparable auto t2);
There is a subtle change here: there is no longer a requirement that t1 and t2 are of the same type, nor that either type matches the return type, as with f1. The only constraint is that they both satisfy std::equality_comparable. If they must both be of the same type, you can advertise the type of t2 as decltype(t1):
auto f3(std::equality_comparable auto t1, decltype(t1) t2);
It is a little ungainly; however, if your function only takes one parameter, then this use of auto becomes a much more attractive spelling.
You will also notice that we are no longer passing std::is_arithmetic, but std::equality_comparable instead. Why is that? The answer is that std::is_arithmetic is a class template, while std::equality_comparable is a concept. This syntax is only available to concepts. We shall see how to satisfy this shortly.
This syntax gives the user more information in much less space. They can read the function signature and see that it is a function template which is constrained on equality-comparable types. Moreover, if they try and call the function using arguments that are not equality comparable, the compiler can say, quite clearly, that the supplied arguments are not equality comparable, as required by the declaration.
Unfortunately, if you want to add additional constraints to your parameters, this syntax will fail you. It would look like this:
auto f4(std::copyable and std::default_initializable auto t);
The presence of the auto is what signifies that a constraint is being specified. The first constraint is ambiguous. The way to solve this is by defining your own concept:
template <typename T> concept cdi = std::copyable <T> and std::default_initializable <T>;
auto f4(cdi auto t);
Of course, cdi is a dreadful name. We may have mentioned this already, but naming is hard. Concepts are particularly ticklish. A name like is_copyable_and_default_initializable is a poor name because it simply moves the problem somewhere else. What does that actually mean?
In this case, we know perfectly well what it means: something that is copyable and default initializable is semiregular. This is a well-known part of the taxonomy of types, and the standard library provides this concept along with a selection of others in the <concepts> header. You can find out a little about type taxonomy at Rainer Grimm’s blog.1
1. https://www.modernescpp.com/index.php/c-20-define-the-concept-regular-and-semiregular
The <concepts> header is worth examining because it shows you how concepts build on one another. The concept std::semiregular is composed from the concepts std::copyable and std::default_initializable. The concept std::copyable is composed from std::copy_constructible, std::movable, and std::assignable_from.
It is important to get a grasp of the taxonomy of types, to understand, for example, the difference between regular and semiregular. These terms were introduced by Alex Stepanov, the prime mover behind the Standard Template Library, and he discusses them in his book Elements of Programming.2
2. Stepanov, A, and McJones, P, 2009. Elements of Programming. Boston: Addison-Wesley.
How to abstract your concepts
What we have here is a problem of abstraction. The name is_copyable_and_default_initializable simply restated the question, “What should I call this concept?” That is not abstraction. Raising the level of abstraction means traversing the taxonomy of types and identifying what the name of the thing is that is formed from the intersection of these concepts.
This is a fundamental part of abstraction. Earlier, in Chapter 2.1, we described the difference between encapsulation, data hiding, and abstraction. Naming a concept after the pieces that make it up is merely encapsulation, it is not abstraction. It is not a scalable naming method either. You should expect to compose concepts in the same way that those defined in the <concepts> header are composed. This mechanism of composition of concepts will reveal the level of abstraction at which you are working and will reflect how you have factored your solution domain.
When writing function templates, you are attempting to encapsulate a generic algorithm. The concepts that are appropriate for your function are abstracted from that algorithm. This may mean that some concept names simply reflect the function name. Let’s develop a trivial and naïve sort function:
template <typename InIt>
void sort(InIt begin, InIt end)
{
while (begin != end) // (1)
{
auto src = begin; // (2)
auto next = std::next(begin); // (3)
while (next != end)
{
if (*next < *src) { // (4)
std::iter_swap(src++, next++);
}
}
--end;
}
}
This is a bubble sort, which takes quadratic time, so we wouldn’t expect to see this in production code, but it serves our purposes. What do we know about the required capabilities of the template parameter?
At (1), there is an equality comparison between two instances of InIt. That means they need to be equality comparable. At (2), there is a copy construction, so they need to be copy constructible. At (3), we call std::next which means that they need to be incrementable. At (4), we require dereferencing and comparison of the iterated type. Let’s see what we have available to us from the standard and try and name this set of type requirements.
As it turns out, we have an embarrassment of riches. The standard library has been sprinkled with concepts, and there is an entire header devoted to some fundamental concepts. For example, at point (1) we need to be able to compare the iterators. This means we need std::equality_comparable from the <concepts> header. At point (2) the assignment is supported with the concept std::copy_constructible, while (3) is supported by std::incrementable, which lives in the <iterator> header.
Things get interesting at (4). We need to dereference and compare the values indicated by the iterator, then we need to be able to dereference the iterator and swap the indicated values. This indirect behavior is supported by std::indirectly_readable from <iterator> and std::swappable from <concepts>. Comparing the values is slightly more work: we need to invoke a comparison predicate relating two operands. And again <concepts> comes to the rescue with std::invocable, which is required by std::predicate, which is required by std::relation, which is required by std::strict_weak_order.
This gives us a great starting point for our concept for the parameters of this function template.
template <typename R, typename T , typename U> concept sort_concept = std::equality_comparable<T, U> and std::copy_constructible<T> and std::incrementable<T> and std::indirectly_readable<T> and std::swappable<T> and std::strict_weak_order<R, T, U>;
void sort(sort_concept auto begin, sort_concept auto end);
We hope you agree that sort_concept is a terrible name.
How about sortable?
Performing that substitution, our function signature looks like:
void sort(sortable auto begin, sortable auto end);
We have eliminated the angle brackets, which is a relief to my eyes. We know it’s a function template because of the name-auto-name parameter list. If we pass something that does not satisfy the sortable concept, the compiler will be able to say “this type is not sortable: it does not satisfy std::swappable,” for example.
It should not surprise you to learn that std::sortable is already a concept, housed in the <iterator> header. You can go to the documentation for std::sortable at cppreference.com3 and look up precisely how it is composed. My decomposition of sortable from the primitive sort function was a first step rather than a complete solution. You will find that there are rather more components to the sortable concept. For example, we omitted std::assignable_from. However, eventually someone would attempt to instantiate the function with a type that didn’t satisfy that concept and compilation would fail. After deciphering the error message, you could improve the definition of sortable by adding that concept.
3. https://en.cppreference.com/w/cpp/iterator/sortable
By specifying a concept for your template arguments, you reduce the punctuation and verbiage, and crystalize the meaning at the point where it is relevant. It highlights the level of abstraction at which you are operating. This makes your API clearer, more expressive, and more usable, with better documentation, better error messages, and more precise overloading.4
4. Bjarne Stroustrup: Thriving in a crowded and changing world: C++ 2006-2020. ACM/SIGPLAN History of Programming Languages conference, HOPL-IV. London. June 2020. https://www.stroustrup.com/hopl20main-p5-p-bfc9cd4--final.pdf
Factoring via concepts
Note that the concept name in the above example came from the algorithm, not the type. Concepts are found in algorithms, not types. This is further highlighted by the answer to the question, “How do I make domain-specific concepts?”
For example, if you have a bunch of handy function templates for doing interesting things with payroll, they may all require that an instance of the template type parameter can perform the appropriate payroll queries. The keyword requires is used to define fundamental concepts like this:
template <typename T>
concept payroll_queryable =
requires (T p) { p.query_payroll(); };
void current_salary(payroll_queryable auto employee);
The concept is abstracted from a thing that can be done, not a property of the type. It describes a behavior, not a property. Beware of overconstraint, though. Consider if the function were implemented like this:
void current_salary(payroll_queryable auto employee)
{
std::cout << "unimplemented
";
}
This invocation would generate a compiler error:
current_salary("Beth");
Even though the function template implementation makes no use of the satisfactions offered by the concept, the compiler will still tell you the associated constraints are not satisfied.
As you implement your solution and find abstractions. you can describe them not just in terms of types and functions, but types and behaviors. The beauty of concepts is that they allow you to build a taxonomy for your solution domain. Just as you aren’t limited by types defined by the standard, nor are you limited to the concepts defined by the standard. You can define your own concepts, just as you can define your own types, and use them to clarify the design of your library, conveying its full meaning and utility. The process of breaking down your solution domain into manageable pieces, of finding the factors, is greatly aided by having a mechanism by which you can identify behaviors as well as types.
The only thing harder than naming is taxonomy, which is finding the names of names. Concepts allow you to bring identifiers for the behaviors of your solution domain to the surface. Of course, you don’t need to go mad and identify everything, nor should you. Concepts constrain template parameters, so unless your program consisted entirely of function templates you would not be able to make use of them all. This is reminiscent of the argument against object-oriented programming that speaks about modeling every last detail. However, for optimal clarity, specify constraints in the form of concepts for all your template arguments.
Summary
Whenever I start teaching about C++, one of the first things I say is that there are two things to worry about: state and execution. Behind all the syntactic noise of class declarations and access levels and function template specializations and const qualification, C++ source files define objects and functions. Linkers link objects and functions into a single binary. Operating systems bind together files and processes. CS courses teach you data structures and algorithms. Now there is another pairing to think about: types and concepts.
As you write function templates, examine what you are doing with your parameters and abstract your constraints from them. Identify the requirements and reuse a concept, or form a new one, to describe them at the point at which you take the argument.
Use concepts to advertise to your users what types can be passed, and to aid the compiler in providing appropriate diagnostic messages.
Use standard concepts where possible, reverting to domain-specific concepts where necessary. Standard concepts are interoperable and generate less friction when it comes to understanding what they imply.
The Core Guidelines has several things to say about concepts, including
• T.10: “Specify concepts for all template arguments”
• T.11: “Whenever possible use standard concepts”
• T.26: “Prefer to define concepts in terms of use-patterns rather than simple syntax”
• T.121: “Use template metaprogramming primarily to emulate concepts”
They are one of the big features of C++20 and the process of their development has already generated some insights into their correct use. As usage spreads through the C++ community, keep an eye on blogs and the Core Guidelines for updates.