Cam's Cyberspace

Recent Notes

Templates and Generic Programming

Properties3
descriptionTemplates as a compile-time code-generation model rather than a type feature: what instantiation actually triggers, why template libraries are header-only, and how C++20 concepts turn duck typing into a checkable interface.
tagscs, languages, type-theory
aliases

11 min read

std::vector<int> and std::vector<std::string> are unrelated types that share no code at runtime and no source text at compile time other than the one definition they were both stamped from. That stamping is what a template is. The syntax looks like a generic type in the sense a Java or C# programmer means, and the compilation model underneath is closer to a macro expander with a type-aware front end.

The comparison across languages, monomorphization against type erasure, is in Generics: Monomorphization vs Erasure. This note is about the C++ mechanism: what gets generated, when, and what C++20 added to make the requirements on the argument stateable.

The idea

A template is not code. It is a description from which code may be generated, and the generation is demand-driven at a finer grain than most people assume. cppreference states that instantiation of a class template does not instantiate any of its member functions unless they are also used. So a member function of a class template can contain an expression that would be ill-formed for the type you instantiated with, and the program compiles cleanly as long as nobody calls it. That laziness is why C++ generics were historically checked at the point of use rather than the point of definition, and it is the exact hole concepts were designed to close.

What a template declares

cppreference lists what a template can define: a family of classes (class template), which may be nested classes; a family of functions (function template), which may be member functions; an alias to a family of types (alias template, since C++11); a family of variables (variable template, since C++14); and a concept (since C++20).

Templates are parameterized by one or more template parameters of three kinds: type template parameters, non-type template parameters, and template template parameters. Type parameters are the familiar typename T. Non-type parameters carry values, which is what makes std::array<int, 8> a distinct type from std::array<int, 9>. Template template parameters take a template itself as the argument.

When template arguments are provided, or, for function and class templates (since C++17), deduced, they are substituted for the template parameters to obtain a specialization of the template, meaning a specific type or a specific function lvalue. Specializations may also be provided explicitly, and the asymmetry there is worth memorizing: cppreference states that full specializations are allowed for class, variable, and function templates, while partial specializations are only allowed for class templates and variable templates. Function templates cannot be partially specialized; you overload instead.

Instantiation is the interesting part

The rule cppreference gives for when generation happens: when a class template specialization is referenced in a context that requires a complete object type, or when a function template specialization is referenced in a context that requires a function definition to exist, the template is instantiated, meaning the code for it is actually compiled, unless the template was already explicitly specialized or explicitly instantiated.

Three consequences follow, and each one shows up in real build problems.

Members are instantiated separately. Instantiation of a class template does not instantiate any of its member functions unless they are also used. This is why you can put a std::vector of a non-copyable type in a variable and only get a compile error at the line where you copy it.

Identical instantiations are merged. At link time, identical instantiations generated by different translation units are merged. Fifty translation units that each use std::vector<int>::push_back each emit it, and the linker collapses them into one. Without that rule, templates would produce a duplicate-symbol error on the first nontrivial use.

Definitions must be visible where instantiation occurs. cppreference states that the definition of a class template must be visible at the point of implicit instantiation, which is why template libraries typically provide all template definitions in the headers, giving most boost libraries as an example of header-only distribution. This is the single biggest practical difference between generic code in C++ and generic code in a language with a real module-level compilation boundary; see Module Systems and Namespacing for what C++ traded away here.

There was an attempt to escape this. cppreference records that export was an optional modifier, removed in C++11, which declared a template as exported, so that files instantiating exported templates did not need to include their definitions, with the declaration being sufficient. It also records why it did not survive: implementations of export were rare and disagreed with each other on details.

The problem concepts solve

Before C++20 a template’s requirements on its argument were implicit in its body. std::sort needs random access iterators, but nothing in its declaration said so, so passing a std::list iterator failed somewhere deep inside the implementation.

cppreference shows both diagnostics for std::sort(l.begin(), l.end()) on a std::list<int>. Without concepts the compiler reports invalid operands to a binary expression involving std::_List_iterator<int>, points at a line inside std::__lg(__last - __first) * 2), and then, in cppreference’s own annotation, produces “50 lines of output”. With concepts the diagnostic is two lines: it cannot call std::sort with std::_List_iterator<int>, with the note that concept RandomAccessIterator<std::_List_iterator<int>> was not satisfied.

The difference is not cosmetic. cppreference states that violations of constraints are detected at compile time, early in the template instantiation process. The failure moves from inside the implementation to the call boundary, which is where the mistake actually is.

Concepts as named requirements

cppreference defines a concept as a named set of requirements whose definition must appear at namespace scope, with the form:

template < template-parameter-list >
concept concept-name = constraint-expression;

Each concept is a predicate, evaluated at compile time, and becomes a part of the interface of a template where it is used as a constraint. The interface phrasing is the design claim: a constraint is not an assertion buried in the body, it is something a caller can read and a compiler can check before entering the body.

cppreference’s worked declaration is Hashable, satisfied by any type T such that for values a of type T the expression std::hash<T>{}(a) compiles and its result is convertible to std::size_t:

template<typename T>
concept Hashable = requires(T a)
{
    { std::hash<T>{}(a) } -> std::convertible_to<std::size_t>;
};

It then gives four spellings of the same constraint on a function template, which are worth knowing because all four appear in real code: template<Hashable T> void f(T) {}, a requires Hashable<T> clause after the parameter list, a trailing requires Hashable<T> clause after the parameter list of the function, and the abbreviated form void f(Hashable auto). With struct meow {} declared, the example compiles f("abc"s) because std::string satisfies Hashable and comments out f(meow{}) as an error because meow does not.

Two restrictions cppreference calls out. Concepts cannot recursively refer to themselves and cannot be constrained, so both concept V = V<T*>; and a concept definition whose own template parameter is constrained are errors. And explicit instantiations, explicit specializations, and partial specializations of concepts are not allowed, on the stated grounds that the meaning of the original definition of a constraint cannot be changed. A concept means one thing everywhere, permanently.

How constraints are actually checked

A constraint is a sequence of logical operations and operands specifying requirements on template arguments, and cppreference lists three kinds (four since C++26): conjunctions, disjunctions, atomic constraints, and fold expanded constraints.

The atomic constraint is the base case, and its satisfaction rule is the one that replaces the old SFINAE machinery. Satisfaction is checked by substituting the parameter mapping and template arguments into the expression, and if the substitution results in an invalid type or expression, the constraint is not satisfied. Not an error: unsatisfied. Otherwise the expression, after any lvalue-to-rvalue conversion, must be a prvalue constant expression of type bool, and the constraint is satisfied if and only if it evaluates to true.

The type requirement is strict in a way that bites. cppreference states the type of the expression after substitution must be exactly bool and no conversion is permitted, and demonstrates with a struct S that has constexpr operator bool() const. The call f(0) is an error because S<int>{} does not have type bool when checking the constrained overload, and cppreference’s annotation adds the sting: this happens even though the unconstrained void f(int) is a better match. A malformed constraint on a candidate you did not want is still a hard error.

Disjunctions short-circuit, and cppreference is explicit that this is about substitution and not merely evaluation: a disjunction is satisfied if either constraint is satisfied, disjunctions are evaluated left to right and short-circuited, and if the left constraint is satisfied, template argument substitution into the right constraint is not attempted. Ordering the cheap or safe alternative first is therefore semantically meaningful, beyond being faster.

Logically equivalent is not the same constraint

cppreference states that a constrained declaration may only be redeclared using the same syntactic form, with no diagnostic required. Declaring template<Incrementable T> void f(T) requires Decrementable<T>; twice is fine, but adding a third declaration written as template<typename T> requires Incrementable<T> && Decrementable<T> void f(T); is ill-formed, no diagnostic required, despite being logically equivalent. Even swapping the order across two declarations of g is ill-formed, because one has Incrementable<T> && Decrementable<T> and the other has Decrementable<T> && Incrementable<T>. Constraint identity is syntactic. Two atomic constraints are identical only if they are formed from the same expression at the source level and their parameter mappings are equivalent.

Why a one-operation concept is usually wrong

The C++ Core Guidelines rule T.20 uses concept Addable = requires(T a, T b) { a + b; };, labeled “bad; insufficient,” to constrain an algo that adds two numbers. algo(7, 9) gives 16 as intended. algo("7"s, "9"s) gives "79", and the guideline’s comment is that maybe the concatenation was expected, but more likely it was an accident. It then points out that Addable violates the mathematical rule that addition is supposed to be commutative. The fix is to require a complete set: concept Number = requires(T a, T b) { a + b; a - b; a * b; a / b; };, after which the string call is an error because string is not a Number. The guideline’s summarizing note is the one to keep, and cppreference quotes it directly: the ability to specify meaningful semantics is a defining characteristic of a true concept, as opposed to a syntactic constraint. The enforcement rule that follows is to flag single-operation concepts when used outside the definition of other concepts.

The intent, as cppreference puts it, is to model semantic categories such as Number, Range, and RegularFunction rather than syntactic restrictions such as HasPlus and Array. A concept that checks only that an operator exists will accept every type that happens to spell that operator, which is how you end up sorting with a comparison that is not an ordering, or “adding” strings. The compiler can check the syntax. Only the concept’s name and documentation carry the semantics, which puts C++20 concepts in the same position as Rust traits without laws or Haskell type classes without laws; see Type Classes and Traits.

Sources

  • “Templates,” cppreference.com. https://en.cppreference.com/w/cpp/language/templates.html . Supports the five kinds of entity a template defines, the three kinds of template parameter, substitution producing a specialization, full versus partial specialization availability, the implicit instantiation trigger, member functions not being instantiated unless used, link-time merging of identical instantiations, the requirement that a class template definition be visible at the point of implicit instantiation and the resulting header-only convention, and the removed export modifier with the reason implementations disagreed.
  • “Constraints and concepts,” cppreference.com. https://en.cppreference.com/w/cpp/language/constraints.html . Supports concepts as named sets of requirements defined at namespace scope, concepts as compile-time predicates forming part of a template’s interface, the Hashable example and the four constraint spellings, the std::sort diagnostic comparison, constraint violations being detected early in instantiation, the ban on recursive or constrained concept definitions and on specializing concepts, the kinds of constraint, atomic-constraint satisfaction with substitution failure meaning unsatisfied, the exact-bool requirement and the S<T>{} error example, short-circuited disjunctions skipping substitution, the same-syntactic-form redeclaration rule with its ill-formed-no-diagnostic-required examples, identity of atomic constraints, and the semantic-categories intent quoting core guideline T.20.
  • “C++ Core Guidelines,” isocpp.github.io. https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines . Supports rule T.20 in full: the insufficient Addable concept, the algo calls yielding 16 and "79", the commutativity objection, the four-operation Number concept rejecting string, the note that specifying meaningful semantics defines a true concept, and the enforcement rule flagging single-operation concepts.

Graph View

Backlinks