8
Concepts and Generic Programming
Programming: you have to start with interesting algorithms.
– Alex Stepanov
-
Use of Concepts; Concept-Based Overloading; Valid Code; Definition of Concepts; Concepts and auto; Concepts and Types
8.1 Introduction
What are templates for? In other words, what programming techniques are made effective by templates? Templates offer:
The ability to pass types (as well as values and templates) as arguments without loss of information. This implies great flexibility in what can be expressed and excellent opportunities for inlining, of which current implementations take great advantage.
Opportunities to weave together information from different contexts at instantiation time. This implies optimization opportunities.
The ability to pass values as template arguments. This implies opportunities for compile-time computation.
In other words, templates provide a powerful mechanism for compile-time computation and type manipulation that can lead to very compact and efficient code. Remember that types (classes) can contain both code (§7.3.2) and values (§7.2.2).
The first and most common use of templates is to support generic programming, that is, programming focused on the design, implementation, and use of general algorithms. Here, “general” means that an algorithm can be designed to accept a wide variety of types as long as they meet the algorithm’s requirements on its arguments. Together with concepts, the template is C++’s main support for generic programming. Templates provide (compile-time) parametric polymorphism.
8.2 Concepts
Consider the sum() from §7.3.1:
template<typename Sequence, typename Value>
Value sum(const Sequence& s, Value v)
{
for (const auto& x : s)
v+=x;
return v;
}This sum() requires that
its first template argument is some kind of sequence of elements, and
its second template argument is some kind of number.
To be more specific, sum() can be invoked for a pair of arguments:
A sequence, Seq, that supports begin() and end() so that the range-for will work (§1.7; §14.1).
An arithmetic type, Value, that supports += so that elements of the sequence can be added.
We call such requirements concepts.
Examples of types that meet this simplified requirement (and more) for being a sequence (also called a range) include the standard-library vector, list, and map. Examples of types that meet this simplified requirement (and more) for being an arithmetic type include int, double, and Matrix (for any reasonable definition of Matrix). We could say that the sum() algorithm is generic in two dimensions: the type of the data structure used to store elements (“the sequence”) and the type of elements.
8.2.1 Use of Concepts
Most template arguments must meet specific requirements for the template to compile properly and for the generated code to work properly. That is, most templates should be constrained templates (§7.2.1). The type-name introducer typename is the least constraining, requiring only that the argument be a type. Usually, we can do better than that. Consider that sum() again:
template<Sequence Seq, Number Num>
Num sum(const Seq& s, Num v)
{
for (const auto& x : s)
v+=x;
return v;
}That’s much clearer. Once we have defined what the concepts Sequence and Number mean, the compiler can reject bad calls by looking at sum()’s interface only, rather than looking at its implementation. This improves error reporting.
However, the specification of sum()’s interface is not complete: I “forgot” to say that we should be able to add elements of a Sequence to a Number. We can do that:
template<Sequence Seq, Number Num>
requires Arithmetic<range_value_t<Seq>,Num>
Num sum(const Seq& s, Num n);The range_value_t (§16.4.4) of a sequence is the type of the elements in that sequence; it comes from the standard library where it names the type of the elements of a range (§14.1). Arithmetic<X,Y> is a concept specifying that we can do arithmetic with numbers of types X and Y. This saves us from accidentally trying to calculate the sum() of a vector<string> or a vector<int*> while still accepting vector<int> and vector<complex<double>>. Typically, when an algorithm requires arguments of differing types, there is a relationship between those types that it is good to make explicit.
In this example, we needed only +=, but for simplicity and flexibility, we should not constrain our template argument too tightly. In particular, we might someday want to express sum() in terms of + and = rather than +=, and then we’d be happy that we used a general concept (here, Arithmetic) rather than a narrow requirement to “have +=.”
Partial specifications, as in the first sum() using concepts, can be very useful. Unless the specification is complete, some errors will not be found until instantiation time. However, even partial specifications express intent and are essential for smooth incremental development where we don’t initially recognize all the requirements we need. With mature libraries of concepts, initial specifications will be close to perfect.
Unsurprisingly, requires Arithmetic<range_value_t<Seq>,Num> is called a requirements-clause. The template<Sequence Seq> notation is simply a shorthand for an explicit use of requires Sequence<Seq>. If I liked verbosity, I could equivalently have written
template<typename Seq, typename Num>
requires Sequence<Seq> && Number<Num> && Arithmetic<range_value_t<Seq>,Num>
Num sum(const Seq& s, Num n);On the other hand, we could also use the equivalence between the two notations to write:
template<Sequence Seq, Arithmetic<range_value_t<Seq>> Num> Num sum(const Seq& s, Num n);
In code bases where we cannot yet use concepts, we have to make do with naming conventions and comments, such as:
template<typename Sequence, typename Number>
// requires Arithmetic<range_value_t<Sequence>,Number>
Number sum(const Sequence& s, Number n);Whatever notation we choose, it is important to design a template with semantically meaningful constraints on its arguments (§8.2.4).
8.2.2 Concept-based Overloading
Once we have properly specified templates with their interfaces, we can overload based on their properties, much as we do for functions. Consider a slightly simplified standard-library function advance() that advances an iterator (§13.3):
template<forward_iterator Iter>
void advance(Iter p, int n) // move p n elements forward
{
while (n--)
++p; // a forward iterator has ++, but not + or +=
}
template<random_access_iterator Iter>
void advance(Iter p, int n) // move p n elements forward
{
p+=n; // a random-access iterator has +=
}The compiler will select the template with the strongest requirements met by the arguments. In this case, a list only supplies forward iterators, but a vector offers random-access iterators, so we get:
void user(vector<int>::iterator vip, list<string>::iterator lsp)
{
advance(vip,10); // uses the fast advance()
advance(lsp,10); // uses the slow advance()
}Like other overloading, this is a compile-time mechanism implying no run-time cost, and where the compiler does not find a best choice, it gives an ambiguity error. The rules for concept-based overloading are far simpler than the rules for general overloading (§1.3). Consider first a single argument for several alternative functions:
If the argument doesn’t match the concept, that alternative cannot be chosen.
If the argument matches the concept for just one alternative, that alternative is chosen.
If arguments from two alternatives match a concept and one is stricter than the other (match all the requirements of the other and more), that alternative is chosen.
If arguments from two alternatives are equally good matches for a concept, we have an ambiguity.
For an alternative to be chosen it must be
a match for all of its arguments, and
at least an equally good match for all arguments as other alternatives, and
a better match for at least one argument.
8.2.3 Valid Code
The question of whether a set of template arguments offers what a template requires of its template parameters ultimately boils down to whether some expressions are valid.
Using a requires-expression, we can check if a set of expressions is valid. For example, we might try to write advance() without the use of the standard-library concept random_access_iterator:
template<forward_iterator Iter>
requires requires(Iter p, int i) { p[i]; p+i; } // Iter has subscripting and integer addition
void advance(Iter p, int n) // move p n elements forward
{
p+=n;
}No, that requires requires is not a typo. The first requires starts the requirements-clause and the second requires starts the requires-expression
requires(Iter p, int i) { p[i]; p+i; }A requires-expression is a predicate that is true if the statements in it are valid code and false if not.
I consider requires-expressions the assembly code of generic programming. Like ordinary assembly code, requires-expressions are extremely flexible and impose no programming discipline. In some form or other, they are at the bottom of most interesting generic code, just as assembly code is at the bottom of most interesting ordinary code. Like assembly code, requires-expressions should not be seen in ordinary code. They belong in the implementation of abstractions. If you see requires requires in your code, it is probably too low level and will eventually become a problem.
The use of requires requires in advance() is deliberately inelegant and hackish. Note that I “forgot” to specify += and the required return types for the operations. Therefore, some uses of the version of advance() will pass concept checking and still not compile. You have been warned! The proper random-access version of advance() is simpler and more readable:
template<random_access_iterator Iter>
void advance(Iter p, int n) // move p n elements forward
{
p+=n; // a random-access iterator has +=
}Prefer use of properly named concepts with well-specified semantics (§8.2.4) and primarily use requires-expressions in the definition of those.
8.2.4 Definition of Concepts
We find useful concepts, such as forward_iterator in libraries, including the standard library (§14.5). As for classes and functions, it is usually easier to use a concept from a good library than to write a new one, but simple concepts are not hard to define. Names from the standard library, such as random_access_iterator and vector, are in lower case. Here, I use the convention to capitalize the names of concepts I have defined myself, such as Sequence and Vector.
A concept is a compile-time predicate specifying how one or more types can be used. Consider first one of the simplest examples:
template<typename T>
concept Equality_comparable =
requires (T a, T b) {
{ a == b } -> Boolean; // compare Ts with ==
{ a != b } -> Boolean; // compare Ts with !=
};Equality_comparable is the concept we use to ensure that we can compare values of a type equal and non-equal. We simply say that, given two values of the type, they must be comparable using == and != and the result of those operations must be Boolean. For example:
static_assert(Equality_comparable<int>); // succeeds
struct S { int a; };
static_assert(Equality_comparable<S>); // fails because structs don't automatically get == and !=The definition of the concept Equality_comparable is exactly equivalent to the English description and not any longer. The value of a concept is always bool.
The result of an { ... } specified after a -> must be a concept. Unfortunately, there isn’t a standard-library boolean concept, so I defined one (§14.5). Boolean simply means a type that can be used as a condition.
Defining Equality_comparable to handle nonhomogeneous comparisons is almost as easy:
template<typename T, typename T2 =T>
concept Equality_comparable =
requires (T a, T2 b) {
{ a == b } -> Boolean; // compare a T to a T2 with ==
{ a != b } -> Boolean; // compare a T to a T2 with !=
{ b == a } -> Boolean; // compare a T2 to a T with ==
{ b != a } -> Boolean; // compare a T2 to a T with !=
};The typename T2 =T says that if we don’t specify a second template argument, T2 will be the same as T; T is a default template argument.
We can test Equality_comparable like this:
static_assert(Equality_comparable<int,double>); // succeeds static_assert(Equality_comparable<int>); // succeeds (T2 is defaulted to int) static_assert(Equality_comparable<int,string>); // fails
This Equally_comparable is almost identical with the standard-library equality_comparable (§14.5).
We can now define a concept that requires arithmetic to be valid between numbers. First we need to define Number:
template<typename T, typename U = T>
concept Number =
requires(T x, U y) { // Something with arithmetic operations and a zero
x+y; x-y; x*y; x/y;
x+=y; x-=y; x*=y; x/=y;
x=x; // copy
x=0;
};This makes no assumptions about the result types, but that’s adequate for simple uses. Given one argument type, Number<X> checks whether X Has the desired properties of a Number. Given two arguments, Number<X,Y> checks that the two types can be used together with the required operations. From that, we can define our Arithmetic concept (§8.2.1):
template<typename T, typename U = T> concept Arithmetic = Number<T,U> && Number<U,T>;
For a more complex example, consider a sequence:
template<typename S>
concept Sequence = requires (S a) {
typename range_value_t<S>; // S must have a value type
typename iterator_t<S>; // S must have an iterator type
{ a.begin() } -> same_as<iterator_t<S>>; // S must have a begin() that returns an iterator
{ a.end() } -> same_as<iterator_t<S>>;
requires input_iterator<iterator_t<S>>; // S's iterator must be an input_iterator
requires same_as<range_value_t<S>, iter_value_t<S>>;
};For a type S to be a Sequence, it must provide a value type (the type of its elements; see §13.1) and an iterator type (the type of its iterators). Here, I used the standard-library associate types range_value_t<S> and iterator_t<S> (§16.4.4) to express that. It must also ensure that there exist begin() and end() functions that return S’s iterators, as is idiomatic for standard-library containers (§12.3). Finally, S’s iterator type must be at least an input_iterator, and the value types of the elements and the iterator must be the same.
The hardest concepts to define are the ones that represent fundamental language concepts. Consequently, it is best to use a set from an established library. For a useful collection, see §14.5. In particular, there is a standard-library concept that allows us to bypass the complexity of the definition of Sequence:
template<typename S> concept Sequence = input_range<S>; // simple to write and general
Had I restricted my notion of “S’s value type to S::value_type, I could have used a simple Value_type:
template<class S> using Value_type = typename S::value_type;
That’s a useful technique for expressing simple notions concisely and for hiding complexity. The definition of the standard value_type_t is fundamentally similar, but a bit more complicated because it handles sequences that don’t have a member called value_type (e.g., built-in arrays).
8.2.4.1 Definition Checking
The concepts specified for a template are used to check arguments at the point of use of the template. They are not used to check the use of the parameters in the definition of the template. For example:
template<equality_comparable T>
bool cmp(T a, T b)
{
return a<b;
}Here the concept guarantees the presence of == but not <:
bool b0 = cmp(cout,cerr); // error: ostream doesn't support == bool b1 = cmp(2,3); // OK: returns true bool b2 = cmp(2+3i,3+4i); // error: complex<double> doesn't support <
The check of concepts catches the attempt to pass the ostreams, but accepts the ints and the complex<double>s because those two types support ==. However, int supports < so cmp(2,3) compiles, whereas cmp(2+3i,3+4i) is rejected when the body of cmp() is checked and instantiated for complex<double> that does not support <.
Delaying the final check of the template definition until instantiation time gives two benefits:
We can use incomplete concepts during development. That allows us to gain experience while developing concepts, types, and algorithms, and to gradually improve checking.
We can insert debug, tracing, telemetry, etc. code into a template without affecting its interface. Changing an interface can cause massive recompilation.
Both are important when developing and maintaining large code bases. The price we pay for that important benefit is that some errors, such as using < where only == is guaranteed, are caught very late in the compilation process (§8.5).
8.2.5 Concepts and auto
The keyword auto can be used to indicate that an object should have the type of its initializer (§1.4.2):
auto x = 1; // x is an int
auto z = complex<double>{1,2}; // z is a complex<double>However, initialization doesn’t just take place in the simple variable definitions:
auto g() { return 99; } // g() returns an int
int f(auto x) { /* ... */ } // take an argument of any type
int x = f(1); // this f() takes an int
int z = f(complex<double>{1,2}); // this f() takes a complex<double>The keyword auto denotes the least constrained concept for a value: it simply requires that it must be a value of some type. Taking an auto parameter makes a function into a function template.
Given concepts, we can strengthen requirements of all such initializations by preceding auto by a concept. For example:
auto twice(Arithmetic auto x) { return x+x; } // just for numbers
auto thrice(auto x) { return x+x+x; } // for anything with a +
auto x1 = twice(7); // OK: x1==14
string s "Hello ";
auto x2 = twice(s); // error: a string is not Arithmetic
auto x3 = thrice(s); // OK x3=="Hello Hello Hello "In addition to their use for constraining function arguments, concepts can constrain the initialization of variables:
auto ch1 = open_channel("foo"); // works with whatever open_channel() returns
Arithmetic auto ch2 = open_channel("foo"); // error: a channel is not Arithmetic
Channel auto ch3 = open_channel("foo"); // OK: assuming Channel is an appropriate concept
// and that open_channel() returns oneThis comes in very handy to counter overuse of auto and to document requirements on code using generic functions.
For readability and debugging it is often important that a type error is caught as close to its origin as possible. Constraining a return type can help:
Number auto some_function(int x)
{
// ...
return fct(x); // an error unless fct(x) returns a Number
// ...
}Naturally, we could have achieved that by introducing a local variable:
auto some_function(int x)
{
// ...
Number auto y = fct(x); // an error unless fct(x) returns a Number
return y;
// ...
}However, that’s a bit verbose and not all types can be cheaply copied.
8.2.6 Concepts and Types
A type
Specifies the set of operations that can be applied to an object, implicitly and explicitly
Relies on function declarations and language rules
Specifies how an object is laid out in memory
A single-argument concept
Specifies the set of operations that can be applied to an object, implicitly and explicitly
Relies on use patterns reflecting function declarations and language rules
Says nothing about the layout of the object
Enables the use of a set of types
Thus, constraining code with concepts gives more flexibility than constraining with types. In addition, concepts can define the relationship among several arguments. My ideal is that eventually most functions will be defined as template functions with their arguments constrained by concepts. Unfortunately, the notational support for that is not yet perfect: we have to use a concept as an adjective, rather that a noun. For example:
void sort(Sortable auto&); // 'auto' required void sort(Sortable&); // error: 'auto' required after concept name
8.3 Generic Programming
The form of generic programming directly supported by C++ centers around the idea of abstracting from concrete, efficient algorithms to obtain generic algorithms that can be combined with different data representations to produce a wide variety of useful software [Stepanov,2009]. The abstractions that represent the fundamental operations and data structures are called concepts.
8.3.1 Use of Concepts
Good, useful concepts are fundamental and are discovered more than they are designed. Examples are integer and floating-point number (as defined even in Classic C [Kernighan,1978]), sequence, and more general mathematical concepts, such as ring and vector space. They represent the fundamental concepts of a field of application. That is why they are called “concepts.” Identifying and formalizing concepts to the degree necessary for effective generic programming can be a challenge.
For basic use, consider the concept regular (§14.5). A type is regular when it behaves much like an int or a vector. An object of a regular type
can be default constructed.
can be copied (with the usual semantics of copy, yielding two objects that are independent and compare equal) using a constructor or an assignment.
can be compared using == and !=.
doesn’t suffer technical problems from overly clever programming tricks.
A string is another example of a regular type. Like int, string is also totally_ordered (§14.5). That is, two strings can be compared using <, <=, >, >=, and <=> with the appropriate semantics.
A concept is not just a syntactic notion, it is fundamentally about semantics. For example, don’t define + to divide; that would not match the requirements for any reasonable number. Unfortunately, we do not yet have any language support for expressing semantics, so we have to rely on expert knowledge and common sense to get semantically meaningful concepts. Do not define semantically meaningless concepts, such as Addable and Subtractable. Instead, rely on domain knowledge to define concepts that match fundamental concepts in an application domain.
8.3.2 Abstraction Using Templates
Good abstractions are carefully grown from concrete examples. It is not a good idea to try to “abstract” by trying to prepare for every conceivable need and technique; in that direction lies inelegance and code bloat. Instead, start with one – and preferably more – concrete examples from real use and try to eliminate inessential details. Consider:
double sum(const vector<int>& v)
{
double res = 0;
for (auto x : v)
res += x;
return res;
}This is obviously one of many ways to compute the sum of a sequence of numbers.
Consider what makes this code less general than it needs to be:
Why just ints?
Why just vectors?
Why accumulate in a double?
Why start at 0?
Why add?
Answering the first four questions by making the concrete types into template arguments, we get the simplest form of the standard-library accumulate algorithm:
template<forward_iterator Iter, Arithmetic<iter_value_t<Iter>> Val>
Val accumulate(Iter first, Iter last, Val res)
{
for (auto p = first; p!=last; ++p)
res += *p;
return res;
}Here, we have:
The data structure to be traversed has been abstracted into a pair of iterators representing a sequence (§8.2.4, §13.1).
The type of the accumulator has been made into a parameter.
The type of the accumulator must be arithmetic .
The type of the accumulator must work with the iterator’s value type (the element type of the sequence).
The initial value is now an input; the type of the accumulator is the type of this initial value.
A quick examination or – even better – measurement will show that the code generated for calls with a variety of data structures is identical to what you get from hand-coded examples. Consider:
void use(const vector<int>& vec, const list<double>& lst)
{
auto sum = accumulate(begin(vec),end(vec),0.0); // accumulate in a double
auto sum2 = accumulate(begin(lst),end(lst),sum);
// ...
}The process of generalizing from a concrete piece of code (and preferably from several) while preserving performance is called lifting. Conversely, the best way to develop a template is often to
first, write a concrete version
then, debug, test, and measure it
finally, replace the concrete types with template arguments.
Naturally, the repetition of begin() and end() is tedious, so we can simplify the user interface a bit:
template<forward_range R, Arithmetic<value_type_t<R>> Val>
Val accumulate(const R& r, Val res = 0)
{
for (auto x : r)
res += x;
return res;
}A range is a standard-library concept representing a sequence with begin() and end() (§13.1). For full generality, we can abstract the += operation also; see §17.3.
Both the pair-of-iterators and the range version of accumulate() are useful: the pair-of-iterators version for generality, the range version for simplicity of common uses.
8.4 Variadic Templates
A template can be defined to accept an arbitrary number of arguments of arbitrary types. Such a template is called a variadic template. Consider a simple function to write out values of any type that has a << operator:
void user()
{
print("first: ", 1, 2.2, "hello
"s); // first: 1 2.2 hello
print("
second: ", 0.2, 'c', "yuck!"s, 0, 1, 2, '
'); // second: 0.2 c yuck! 0 1 2
}Traditionally, implementing a variadic template has been to separate the first argument from the rest and then recursively call the variadic template for the tail of the arguments:
template<typename T>
concept Printable = requires(T t) { std::cout << t; } // just one operation!
void print()
{
// what we do for no arguments: nothing
}
template<Printable T, Printable... Tail>
void print(T head, Tail... tail)
{
cout << head << ' '; // first, what we do for the head
print(tail...); // then, what we do for the tail
}The Printable... indicates that Tail is a sequence of types. The Tail... indicates that tail is a sequence of values of the types in Tail. A parameter declared with a ... is called a parameter pack. Here, tail is a (function argument) parameter pack where the elements are of the types found in the (template argument) parameter pack Tail. So, print() can take any number of arguments of any types.
A call of print() separates the arguments into a head (the first) and a tail (the rest). The head is printed and then print() is called for the tail. Eventually, of course, tail will become empty, so we need the no-argument version of print() to deal with that. If we don’t want to allow the zero-argument case, we can eliminate that print() using a compile-time if:
template<Printable T, Printable... Tail>
void print(T head, Tail... tail)
{
cout << head << ' ';
if constexpr(sizeof...(tail)> 0)
print(tail...);
}I used a compile-time if (§7.4.3), rather than a plain run-time if, to avoid a final call print() from being generated. Given that, the “empty” print() need not be defined.
The strength of variadic templates is that they can accept any arguments you care to give them. Weaknesses include
The recursive implementations can be tricky to get right.
The type checking of the interface is a possibly elaborate template program.
The type checking code is ad hoc, rather than defined in the standard.
The recursive implementations can be surprisingly expensive in compile time and compiler memory requirements.
Because of their flexibility, variadic templates are widely used in the standard library, and occasionally wildly overused.
8.4.1 Fold Expressions
To simplify the implementation of simple variadic templates, C++ offers a limited form of iteration over elements of a parameter pack. For example:
template<Number... T>
int sum(T... v)
{
return (v + ... + 0); // add all elements of v starting with 0
}This sum() can take any number of arguments of any types:
int x = sum(1, 2, 3, 4, 5); // x becomes 15
int y = sum('a', 2.4, x); // y becomes 114 (2.4 is truncated and the value of 'a' is 97)The body of sum uses a fold expression:
return (v + ... + 0); // add all elements of v to 0
Here, (v+...+0) means add all the elements of v starting with the initial value 0. The first element to be added is the “rightmost” (the one with the highest index): (v[0]+(v[1]+(v[2]+(v[3]+(v[4]+0))))). That is, starting from the right where the 0 is. It is called a right fold. Alternatively, we could have used a left fold:
template<Number... T>
int sum2(T... v)
{
return (0 + ... + v); // add all elements of v to 0
}Now, the first element to be added is the “leftmost” (the one with the lowest index): (((((0+v[0])+v[1])+v[2])+v[3])+v[4]). That is, starting from the left where the 0 is.
Fold is a very powerful abstraction, clearly related to the standard-library accumulate(), with a variety of names in different languages and communities. In C++, the fold expressions are currently restricted to simplify the implementation of variadic templates. A fold does not have to perform numeric computations. Consider a famous example:
template<Printable ...T>
void print(T&&... args)
{
(std::cout << ... << args) << '
'; // print all arguments
}
print("Hello!"s,' ',"World ",2017); // (((((std::cout << "Hello!"s) << ' ') << "World ") << 2017) << '
');Why 2017? Because fold() was added to C++ in 2017 (§19.2.3).
8.4.2 Forwarding Arguments
Passing arguments unchanged through an interface is an important use of variadic templates. Consider a notion of a network input channel for which the actual method of moving values is a parameter. Different transport mechanisms have different sets of constructor parameters:
template<concepts::InputTransport Transport>
class InputChannel {
public:
// ...
InputChannel(Transport::Args&&... transportArgs)
: _transport(std::forward<TransportArgs>(transportArgs)...)
{}
// ...
Transport _transport;
};The standard-library function forward() (§16.6) is used to move the arguments unchanged from the InputChannel constructor to the Transport constructor.
The point here is that the writer of InputChannel can construct an object of type Transport without having to know what arguments are required to construct a particular Transport. The implementer of InputChannel needs only to know the common user interface for all Transport objects.
Forwarding is very common in foundational libraries where generality and low run-time overhead are necessary and very general interfaces are common.
8.5 Template Compilation Model
At the point of use, the arguments for a template are checked against its concepts. Errors found here will be reported immediately. What cannot be checked at this point, such as arguments for unconstrained template parameters, is postponed until code is generated for the template with a set of template arguments: “at template instantiation time.”
An unfortunate side effect of instantiation-time type checking is that a type error can be detected uncomfortably late (§8.2.4.1). Also, late checking often results in spectacularly bad error messages because the compiler does not have type information giving hints to the programmer’s intent and often detects a problem only after combining information from several places in the program.
The instantiation-time type checking provided for templates checks the use of arguments in the template definition. This provides a compile-time variant of what is often called duck typing (“If it walks like a duck and it quacks like a duck, it’s a duck”). Or – using more technical terminology – we operate on values, and the presence and meaning of an operation depend solely on its operand values. This differs from the alternative view that objects have types, which determine the presence and meaning of operations. Values “live” in objects. This is the way objects (e.g., variables) work in C++, and only values that meet an object’s requirements can be put into it. What is done at compile time using templates mostly does not involve objects, only values. The exception is local variables in a constexpr function (§1.6) that are used as objects inside the compiler.
To use an unconstrained template, its definition (not just its declaration) must be in scope at its point of use. When using header files and #include, this means that template definitions are found in header files, rather than .cpp files. For example, the standard header <vector> holds the definition of vector.
This changes when we start to use modules (§3.2.2). Using modules, the source code can be organized in the same way for ordinary functions and template functions. A module is semi-compiled into a representation that makes it fast to import and use. Think of that representation as an easily traversed graph containing all available scope and type information and supported by a symbol table allowing quick access to individual entities.
8.6 Advice
[1] Templates provide a general mechanism for compile-time programming; §8.1.
[2] When designing a template, carefully consider the concepts (requirements) assumed for its template arguments; §8.3.2.
[3] When designing a template, use a concrete version for initial implementation, debugging, and measurement; §8.3.2.
[4] Use concepts as a design tool; §8.2.1.
[5] Specify concepts for all template arguments; §8.2; [CG: T.10].
[6] Whenever possible use named concepts (e.g., standard-library concepts); §8.2.4, §14.5; [CG: T.11].
[7] Use a lambda if you need a simple function object in one place only; §7.3.2.
[8] Use templates to express containers and ranges; §8.3.2; [CG: T.3].
[9] Avoid “concepts” without meaningful semantics; §8.2; [CG: T.20].
[10] Require a complete set of operations for a concept; §8.2; [CG: T.21].
[11] Use named concepts §8.2.3.
[12] Avoid requires requires; §8.2.3.
[13] auto is the least constrained concept §8.2.5.
[14] Use variadic templates when you need a function that takes a variable number of arguments of a variety of types; §8.4.
[15] Templates offer compile-time “duck typing”; §8.5.
[16] When using header files, #include template definitions (not just declarations) in every translation unit that uses them; §8.5.
[17] To use a template, make sure its definition (not just its declaration) is in scope; §8.5.
[18] Unconstrained templates offer compile-time “duck typing”; §8.5.