The C++ Programming Language (2013)
Part III: Abstraction Mechanisms
23. Templates
Your quote here.
– B. Stroustrup
• Introduction and Overview
• A Simple String Template
Defining a Template; Template Instantiation
• Type Checking
Type Equivalence; Error Detection
• Class Template Members
Data Members; Member Functions; Member Type Aliases; static Members; Member Types; Member Templates; Friends
• Function Templates
Function Template Arguments; Function Template Argument Deduction; Function Template Overloading
• Template Aliases
• Source Code Organization
Linkage
• Advice
23.1. Introduction and Overview
Templates provide direct support for generic programming (§3.4) in the form of programming using types as parameters. The C++ template mechanism allows a type or a value to be a parameter in the definition of a class, a function, or a type alias. Templates provide a straightforward way to represent a wide range of general concepts and simple ways to combine them. The resulting classes and functions can match handwritten, less general code in run-time and space efficiency.
A template depends only on the properties that it actually uses from its parameter types and does not require types used as arguments to be explicitly related. In particular, the argument types used for a template need not be part of an inheritance hierarchy. Built-in types are acceptable and very common as template arguments.
The composition offered by templates is type-safe (no object can be implicitly used in a way that disagrees with its definition), but unfortunately, a template’s requirements on its arguments cannot be simply and directly stated in code (§24.3).
Every major standard-library abstraction is represented as a template (for example, string, ostream, regex, complex, list, map, unique_ptr, thread, future, tuple, and function), and so are the key operations (for example, string comparisons, the output operator <<, complex arithmetic operations, list insertions and deletions, and sort()). This makes the library chapters (Part IV) of this book a rich source of examples of templates and programming techniques relying on them.
Here, templates are introduced with the primary focus on techniques needed for the design, implementation, and use of the standard library. The standard library requires a greater degree of generality, flexibility, and efficiency than does most software. Consequently, techniques that can be used in the design and implementation of the standard library are effective and efficient in the design of solutions to a wide variety of problems. These techniques enable an implementer to hide sophisticated implementations behind simple interfaces and to expose complexity to the user when the user has a specific need for it.
Templates and the fundamental techniques for using them are the focus of this and the following six chapters. This chapter focuses on the most basic template facilities and fundamental programming techniques for using them:
§23.2 A Simple String Template: The basic mechanisms for defining and using class templates are introduced through the example of a string template.
§23.3 Type Checking: The basic rules of type equivalence and type checking as they apply to templates.
§23.4 Class Template Members: How members of a class template are defined and used.
§23.5 Function Templates: How to define and use function templates. How overloading is resolved for function templates and ordinary functions.
§23.6 Template Aliases: Template aliases provide a powerful mechanism for hiding implementation details and cleaning up the notation used for templates.
§23.7 Source Code Organization: How to organize templates into source files.
Chapter 24, Generic Programming, presents the basic technique of generic programming, and the fundamental idea of concepts (requirements on template arguments) is explored:
§24.2 Algorithms and Lifting: An example of the basic technique for developing a generic algorithm from concrete examples.
§24.3 Concepts: Introduces and discusses the fundamental notion of a concept, that is, a set of requirements that a template can impose on its template arguments.
§24.4 Making Concepts Concrete: Presents techniques for using concepts expressed as compile-time predicates.
Chapter 25, Specialization, discusses template argument passing and the notion of specialization:
§25.2 Template Parameters and Arguments: What can be a template argument: types, values, and templates. How to specify and use default template arguments.
§25.3 Specialization: Special versions, called specializations, of a template for a specific set of template arguments can be generated from the templates by the compiler or be provided by the programmer.
Chapter 26, Instantiation, presents issues related to generation of template specialization (instances) and name binding:
§26.2 Template Instantiation: The rules for when and how a compiler generates specializations from a template definition and how to specify them manually.
§26.3 Name Binding: The rules for determining to which entity a name used in a template definition refers.
Chapter 27, Templates and Hierarchies, discusses the relation between the generic programming techniques supported by templates and the object-oriented techniques supported by class hierarchies. The emphasis is on how to use them in combination:
§27.2 Parameterization and Hierarchy: Templates and class hierarchies are two ways of representing sets of related abstractions. How do we choose between them?
§27.3 Hierarchies of Class Templates: Why it is usually a bad idea simply to add template parameters to an existing class hierarchy?
§27.4 Template Parameters as Base Classes: Presents techniques for composing interfaces and data structures for type safety and performance.
Chapter 28, Metaprogramming, concentrates on the use of templates as a means of generating functions and classes:
§28.2 Type Functions: Functions that take types as arguments or return types as results.
§28.3 Compile-time Control Structures: How to express selection and recursion for type functions, and some rules of thumb for their use.
§28.4 Conditional Definition: enable_if: How to conditionally define functions and overload templates using (almost) arbitrary predicates.
§28.5 A Compile-time List: Tuple: How to build and access lists with elements of (almost) arbitrary types.
§28.6 Variadic templates: How (in a statically type-safe manner) to define templates that take arbitrary numbers of template arguments of arbitrary types.
§28.7 SI Units Example: This example uses simple metaprogramming techniques in combination with other programming techniques to provide a library for computations that are (at compile time) checked for correct use of the meters, kilograms, and seconds system of units.
Chapter 29, A Matrix Design, demonstrates how various template features can be used in combination to address a challenging design task:
§29.2 A Matrix Template: How to define an N-dimensional matrix with flexible and type-safe initialization, subscription, and submatrices.
§29.3 Matrix Arithmetic Operations: How to provide simple arithmetic operations on an N-dimensional matrix.
§29.4 Matrix Implementation: Some useful implementation techniques.
§29.5 Solving Linear Equations: An example of simple matrix use.
Templates were introduced early (§3.4.1, §3.4.2) and used throughout this book, so I assume that you have some familiarity with them.
23.2. A Simple String Template
Consider a string of characters. A string is a class that holds characters and provides operations such as subscripting, concatenation, and comparison that we usually associate with the notion of a “string.” We would like to provide that behavior for many different kinds of characters. For example, strings of signed characters, of unsigned characters, of Chinese characters, of Greek characters, etc., are useful in various contexts. Thus, we want to represent the notion of “string” with minimal dependence on a specific kind of character. The definition of a string relies on the fact that a character can be copied, and little else (§24.3). Thus, we can make a more general string type by taking the string of char from §19.3 and making the character type a parameter:
template<typename C>
class String {
public:
String();
explicit String(const C*);
String(const String&);
String operator=(const String&);
// ...
C& operator[](int n) { return ptr[n]; } // unchecked element access
String& operator+=(C c); // add c at end
// ...
private:
static const int short_max = 15; // for the short string optimization
int sz;
C* ptr; // ptr points to sz Cs
};
The template<typename C> prefix specifies that a template is being declared and that a type argument C will be used in the declaration. After its introduction, C is used exactly like other type names. The scope of C extends to the end of the declaration prefixed by template<typename C>. You may prefer the shorter and equivalent form template<class C>. In either case, C is a type name; it need not be the name of a class. Mathematicians will recognize template<typename C> as a variant of the traditional “for all C” or more specifically “for all types C” or even “for all C, such that C is a type.” If you think along those lines, you will note that C++ lacks a fully general mechanism for specifying the required properties of a template parameter C. That is, we can’t say “for all C, such that ...” where the “...” is a set of requirements for C. In other words, C++ does not offer a direct way to say what kind of type a template argument C is supposed to be (§24.3).
The name of a class template followed by a type bracketed by < > is the name of a class (as defined by the template) and can be used exactly like other class names. For example:
String<char> cs;
String<unsigned char> us;
String<wchar_t> ws;
struct Jchar { /* ... */ }; // Japanese character
String<Jchar> js;
Except for the special syntax of its name, String<char> works exactly as if it had been defined using the definition of class String in §19.3. Making String a template allows us to provide the facilities we had for String of char for Strings of any kind of character. For example, if we use the standard-library map and the String template, the word-counting example from §19.2.1 becomes:
int main() // count the occurrences of each word on input
{
map<String<char>,int> m;
for (String<char> buf; cin>>buf;)
++m[buf];
// ... write out result ...
}
The version for our Japanese-character type Jchar would be:
int main() // count the occurrences of each word on input
{
map<String<Jchar>,int> m;
for (String<Jchar> buf; cin>>buf;)
++m[buf];
// ... write out result ...
}
The standard library provides the template class basic_string that is similar to the templatized String (§19.3, §36.3). In the standard library, string is a synonym for basic_string<char> (§36.3):
using string = std::basic_string<char>;
This allows us to write the word-counting program like this:
int main() // count the occurrences of each word on input
{
map<string,int> m;
for (string buf; cin>>buf;)
++m[buf];
// ... write out result ...
}
In general, type aliases (§6.5) are useful for shortening the long names of classes generated from templates. Also, we often prefer not to know the details of how a type is defined, and an alias allows us to hide the fact that a type is generated from a template.
23.2.1. Defining a Template
A class generated from a class template is a perfectly ordinary class. Thus, use of a template does not imply any run-time mechanisms beyond what is used for an equivalent “handwritten” class. In fact, using a template can lead to a decrease of code generated because code for a member function of a class template is only generated if that member is used (§26.2.1).
In addition to class templates, C++ offers function templates (§3.4.2, §23.5). I will introduce most of the “mechanics” of templates in the context of class templates and postpone detailed discussion of function templates to §23.5. A template is a specification of how to generate somethinggiven suitable template arguments; the language mechanisms for doing that generation (instantiation (§26.2) and specialization (§25.3)) don’t care much whether a class or a function is generated. So, unless otherwise stated, the rules for templates apply equally to class templates and function templates. Templates can also be defined as aliases (§23.6), but other plausible constructs, such as namespace templates, are not provided.
There are people who make semantic distinctions between the terms class template and template class. I don’t; that would be too subtle: please consider those terms interchangeable. Similarly, I consider function template interchangeable with template function.
When designing a class template, it is usually a good idea to debug a particular class, such as String, before turning it into a template such as String<C>. By doing so, we handle many design problems and most of the code errors in the context of a concrete example. This kind of debugging is familiar to all programmers, and most people cope better with a concrete example than with an abstract concept. Later, we can deal with any problems that might arise from generalization without being distracted by more conventional errors. Similarly, when trying to understand a template, it is often useful to imagine its behavior for a particular type argument such as char before trying to comprehend the template in its full generality. This also fits with the philosophy that a generic component should be developed as a generalization of one or more concrete examples, rather than simply being designed from first principles (§24.2).
Members of a class template are declared and defined exactly as they would have been for a non-template class. A template member need not be defined within the template class itself. In that case, its definition must be provided somewhere else, just as for non-template class members (§16.2.1). Members of a template class are themselves templates parameterized by the parameters of their template class. When such a member is defined outside its class, it must explicitly be declared a template. For example:
template<typename C>
String<C>::String() // String<C>'s constructor
:sz{0}, ptr{ch}
{
ch[0] = {}; // terminating 0 of the appropriate character type
}
template<typename C>
String& String<C>::operator+=(C c)
{
// ... add c to the end of this string ...
return *this;
}
A template parameter, such as C, is a parameter rather than the name of a specific type. However, that doesn’t affect the way we write the template code using the name. Within the scope of String<C>, qualification with <C> is redundant for the name of the template itself, soString<C>::String is the name for the constructor.
Just as there can be only one function defining a class member function in a program, there can be only one function template defining a class template member function in a program. However, specialization (§25.3) enables us to provide alternative implementations for a template givenspecific template arguments. For functions, we can also use overloading to provide different definitions for different argument types (§23.5.3).
It is not possible to overload a class template name, so if a class template is declared in a scope, no other entity can be declared there with the same name. For example:
template<typename T>
class String { /* ... */ };
class String { /* ... */ }; // error: double definition
A type used as a template argument must provide the interface expected by the template. For example, a type used as an argument to String must provide the usual copy operations (§17.5, §36.2.2). Note that there is no requirement that different arguments for the same template parameter should be related by inheritance. See also §25.2.1 (template type parameters), §23.5.2 (template parameter deduction), and §24.3 (requirements on template arguments).
23.2.2. Template Instantiation
The process of generating a class or a function from a template plus a template argument list is often called template instantiation (§26.2). A version of a template for a specific template argument list is called a specialization.
In general, it is the implementation’s job – not the programmer’s – to ensure that specializations of a template are generated for each template argument list used. For example:
String<char> cs;
void f()
{
String<Jchar> js;
cs = "It's the implementation's job to figure out what code needs to be generated";
}
For this, the implementation generates declarations for classes String<char> and String<Jchar>, for their destructors and default constructors, and for String<char>::operator=(char*). Other member functions are not used and will not be generated. Generated classes are perfectly ordinary classes that obey all the usual rules for classes. Similarly, generated functions are ordinary functions that obey all the usual rules for functions.
Obviously, templates provide a powerful way of generating lots of code from relatively short definitions. Consequently, a certain amount of caution is in order to avoid flooding memory with almost identical function definitions (§25.3). On the other hand, templates can be written to enable otherwise unachievable quality of generated code. In particular, composition using templates combined with simple inlining can be used to eliminate many direct and indirect function calls. For example, that is how simple operations on critical data structures (such as < in a sort() and+ for scalars in a matrix computation) are reduced to single machine instructions in heavily parameterized libraries. Thus, incautious use of templates leading to the generation of very similar large functions can cause code bloat, whereas use of templates to enable inlining of tiny functions can lead to significant code shrinkage (and speedup) compared to alternatives. In particular, the code generated for a simple < or [] is often a single machine instruction, which is both much faster than any function call and smaller than the code needed to invoke a function and receive its result.
23.3. Type Checking
Template instantiation takes a template plus a set of template arguments and generates code from them. Because so much information is available at instantiation time, weaving together the information from the template definition and the template argument types provides wonderful degrees of flexibility and can yield unparalleled run-time performance. Unfortunately, this flexibility also implies complexity of type checking and difficulties for accurate reporting of type errors.
Type checking is done on the code generated by template instantiation (exactly as if the programmer had expanded the templates by hand). This generated code may contain much that the user of a template has never heard of (such as names of details of a template implementation) and often happens uncomfortably late in the build process. This mismatch between what the programmer sees/writes and what the compiler type checks can be a major problem, and we need to design our programs to minimize its consequences.
The fundamental weakness of the template mechanism is that it is not possible to directly express requirements on a template argument. For example, we cannot say:
template<Container Cont, typename Elem>
requires Equal_comparable<Cont::value_type,Elem>() // requirements for types Cont and Elem
int find_index(Cont& c, Elem e); // find the index of e in c
That is, we have no way in C++ itself to directly say that Cont should be a type that can act as a container and that the type Elem should be a type that allows us to compare a value to an element of Cont. Work is being done to make this possible in future versions of C++ (without loss of flexibility, without loss of run-time performance, and without significant increases in compile time [Sutton,2011]), but for now we will have to do without.
The first step in dealing effectively with problems related to template argument passing is to establish a framework and vocabulary for discussing requirements. Think of a set of requirements on template arguments as a predicate. For example, we can think of “C must be a container” as a predicate that takes a type, C, as an argument and returns true if C is a container (however we may have defined “container”) and false if it is not. For example, Container<vector<int>>() and Container<list<string>>() should be true whereas Container<int>() andContainer<shared_ptr<string>>() should be false. We call such a predicate a concept. A concept is not (yet) a language construct in C++; it is a notion that we can use to reason about requirements on template arguments, use in comments, and sometimes support with our own code (§24.3).
For starters, think of a concept as a design tool: specify Container<T>() as a set of comments saying what properties a type T must have for Container<T>() to be true. For example:
• T must have a subscript operator ([]).
• T must have a size() member function.
• T must have a member type value_type which is the type of its elements.
Note that this list is incomplete (e.g., what does [] take as an argument and what does it return?) and fails to address most semantic issues (e.g., what does [] actually do?). However, even a partial set of requirements can be useful; even something very simple allows us to hand-check our usesand catch obvious errors. For example, Container<int>() is obviously false because int does not have a subscript operator. I will return to the design of concepts (§24.3), consider techniques for supporting concepts in code (§24.4), and give an example of a set of useful concepts (§24.3.2). For now, just note that C++ does not directly support concepts, but that does not mean that concepts don’t exist: for every working template, the designer had some concepts in mind for its arguments. Dennis Ritchie famously said, “C is a strongly typed, weakly checked language.” You could say the same about C++’s templates, except that the checking of template argument requirements (concepts) is actually done, but it is done too late in the compilation process and at an unhelpfully low level of abstraction.
23.3.1. Type Equivalence
Given a template, we can generate types by supplying template arguments. For example:
String<char> s1;
String<unsigned char> s2;
String<int> s3;
using Uchar = unsigned char;
using uchar = unsigned char;
String<Uchar> s4;
String<uchar> s5;
String<char> s6;
template<typename T, int N> // §25.2.2
class Buffer;
Buffer<String<char>,10> b1;
Buffer<char,10> b2;
Buffer<char,20–10> b3;
When using the same set of template arguments for a template, we always refer to the same generated type. However, what does “the same” mean in this context? Aliases do not introduce new types, so String<Uchar> and String<uchar> are the same type as String<unsigned char>. Conversely, because char and unsigned char are different types (§6.2.3), String<char> and String<unsigned char> are different types.
The compiler can evaluate constant expressions (§10.4), so Buffer<char,20–10> is recognized to be the same type as Buffer<char,10>.
Types generated from a single template by different template arguments are different types. In particular, generated types from related arguments are not automatically related. For example, assume that a Circle is a kind of Shape:
Shape* p {new Circle(p,100)}; // Circle* converts to Shape*
vector<Shape>* q {new vector<Circle>{}}; // error: no vector<Circle>* to vector<Shape>* conversion
vector<Shape> vs {vector<Circle>{}}; // error: no vector<Circle> to vector<Shape> conversion
vector<Shape*> vs {vector<Circle*>{}}; // error: no vector<Circle*> to vector<Shape*> conversion
Had such conversions been allowed, type errors would have resulted (§27.2.1). If conversions between generated classes are needed, the programmer can define them (§27.2.2).
23.3.2. Error Detection
A template is defined and then later used in combination with a set of template arguments. When the template is defined, the definition is checked for syntax errors and possibly also for other errors that can be detected in isolation from a particular set of template arguments. For example:
template<typename T>
struct Link {
Link* pre;
Link* suc // syntax error: missing semicolon
T val;
};
template<typename T>
class List {
Link<T>* head;
public:
List() :head{7} { } // error: pointer initialized with int
List(const T& t) : head{new Link<T>{0,o,t}} { } // error: undefined identifier o
// ...
void print_all() const;
};
A compiler can catch simple semantic errors at the point of definition or later at the point of use. Users generally prefer early detection, but not all “simple” errors are easy to detect. Here, I made three “mistakes”:
• A simple syntax error: Leaving out a semicolon at the end of a declaration.
• A simple type error: Independently of what the template parameter is, a pointer cannot be initialized by the integer 7.
• A name lookup error: The identifier o (a mistyped 0, of course) cannot be an argument to Link<T>’s constructor because there is no such name in scope.
A name used in a template definition must either be in scope or in some reasonably obvious way depend on a template parameter (§26.3). The most common and obvious ways of depending on a template parameter T are to explicitly use the name T, to use a member of a T, and to take an argument of type T. For example:
template<typename T>
void List<T>::print_all() const
{
for (Link<T>* p = head; p; p=p–>suc) // p depends on T
cout << *p; // << depends on T
}
Errors that relate to the use of template parameters cannot be detected until the template is used. For example:
class Rec {
string name;
string address;
};
void f(const List<int>& li, const List<Rec>& lr)
{
li.print_all();
lr.print_all();
}
The li.print_all() checks out fine, but lr.print_all() gives a type error because there is no << output operator defined for Rec. The earliest that errors relating to a template parameter can be detected is at the first point of use of the template for a particular template argument. That point is called the first point of instantiation (§26.3.3). The implementation is allowed to postpone essentially all checking until the program is linked, and for some errors link time is also the earliest point when complete checking is possible. Independently of when checking is done, the same set of rules is checked. Naturally, users prefer early checking.
23.4. Class Template Members
Exactly like a class, a template class can have members of several kinds:
• Data members (variable and constant); §23.4.1
• Member functions; §23.4.2
• Member type aliases; §23.6
• static members (function and data); §23.4.4
• Member types (e.g., a member class); §23.4.5
• Member templates (e.g., a member class template); §23.4.6.3
In addition, a class template can declare friends, just as an “ordinary class” can; §23.4.7.
The rules for class template members are those for their generated classes. That is, if you want to know what the rules of a template member are, just look for the rules for a member of an ordinary class (Chapter 16, Chapter 17, and Chapter 20); that will answer most questions.
23.4.1. Data Members
As for an “ordinary class,” a class template can have data members of any type. A non-static data member can be initialized in its definition (§17.4.4) or in a constructor (§16.2.5). For example:
template<typename T>
struct X {
int m1 = 7;
T m2;
X(const T& x) :m2{x} { }
};
X<int> xi {9};
X<string> xs {"Rapperswil"};
Non-static data members can be const, but unfortunately not constexpr.
23.4.2. Member Functions
As for an “ordinary class,” a non-static member function of a class template can be defined in-class or outside the class. For example:
template<typename T>
struct X {
void mf1() { /* ... */ } // defined in-class
void mf2();
};
template<typename T>
void X<T>::mf2() { /* ... */ } // defined out of class
Similarly, a member function of a template can be virtual or not. However, a virtual member function cannot also be a member function template (§23.4.6.2).
23.4.3. Member Type Aliases
Member type aliases, whether introduced using using or typedef (§6.5), play a major role in the design of class templates. They define related types of a class in a way that is easy to access from outside the class. For example, we specify a container’s iterator and element types as aliases:
template<typename T>
class Vector {
public:
using value_type = T;
using iterator = Vector_iter<T>; // Vector_iter is defined elsewhere
// ...
};
The template argument name, T, is only accessible to the template itself, so for other code to refer to the element type, we must provide an alias.
Type aliases play a major role in generic programming by allowing the designer of classes to provide common names for types in different classes (and class templates) with common semantics. Type names as member aliases are often referred to as associated types. The value_type anditerator names are borrowed from the standard library’s container design (§33.1.3). If a class is missing a desired member alias, a trait can be used to compensate (§28.2.4).
23.4.4. static Members
A static data or function member that is not defined in-class must have a unique definition in a program. For example:
template<typename T>
struct X {
static constexpr Point p {100,250}; // Point must be a literal type (§10.4.3)
static const int m1 = 7;
static int m2 = 8; // error: not const
static int m3;
static void f1() { /* ... */ }
static void f2();
};
template<typename T> int X<T>::m1 = 88; // error: two initializers
template<typename T> int X<T>::m3 = 99;
template<typename T> void X::<T>::f2() { /* ... */ }
As for non-template classes, a const or conexpr static data member of literal type can be initialized in-class and need not be defined outside the class (§17.4.5, §iso.9.2).
A static member need only be defined if it is used (§iso.3.2, §iso.9.4.2, §16.2.12). For example:
template<typename T>
struct X {
static int a;
static int b;
};
int* p = &X<int>::a;
If this is all the mention of X<int> in a program, we will get a “not defined” error for X<int>::a, but not for X<int>::b.
23.4.5. Member Types
As for an “ordinary class,” we can define types as members. As usual, such a type can be a class or an enumeration. For example:
template<typename T>
struct X {
enum E1 { a, b };
enum E2; // error: underlying type not known
enum class E3;
enum E4 : char;
struct C1 { /* ... */ };
struct C2;
};
template<typename T>
enum class X<T>::E3 { a, b }; // needed
template<typename T>
enum class X<T>::E4 : char { x, y }; // needed
template<typename T>
struct X<T>::C2 { /* ... */ }; // needed
The out-of-class definition of a member enumeration is only allowed for an enumeration for which we know the underlying type (§8.4).
As usual, the enumerators of a non-class enum are placed in the scope of the enumeration; that is, for a member enumeration, the enumerators are in the scope of its class.
23.4.6. Member Templates
A class or a class template can have members that are themselves templates. This allows us to represent related types with a pleasing degree of control and flexibility. For example, complex numbers are best represented as pairs of values of some scalar type:
template<typename Scalar>
class complex {
Scalar re, im;
public:
complex() :re{}, im{} {} // default constructor
template<typename T>
complex(T rr, T ii =0) :re{rr}, im{ii} { }
complex(const complex&) = default; // copy constructor
template<typename T>
complex(const complex<T>& c) : re{c.real()}, im{c.imag()} { }
// ...
};
This allows mathematically meaningful conversions among complex types, while prohibiting the undesirable narrowing conversions (§10.5.2.6):
complex<float> cf; // default value
complex<double> cd {cf}; // OK: uses float to double conversion
complex<float> cf2 {cd}; // error: no implicit double->float conversion
complex<float> cf3 {2.0,3.0}; // error: no implicit double->float conversion
complex<double> cd2 {2.0F,3.0F}; // OK: uses float to double conversion
class Quad {
// no conversion to int
};
complex<Quad> cq;
complex<int> ci {cq}; // error: no Quad to int conversion
Given this definition of complex, we can construct a complex<T1> from a complex<T2> or from a pair of T2 values if and only if we can construct a T1 from a T2. That seems reasonable.
Be warned that the narrowing error in the complex<double> to complex<float> case will not be caught until the instantiation of complex<float>’s template constructors and then only because I used the {} initialization syntax (§6.3.5) in the constructor’s member initializers. That syntax does not allow narrowing.
Using the (old) () syntax would leave us open to narrowing errors. For example:
template<typename Scalar>
class complex { // old style
Scalar re, im;
public:
complex() :re(0), im(0) { }
template<typename T>
complex(T rr, T ii =0) :re(rr), im(ii) { }
complex(const complex&) = default; // copyconstructor
template<typename T>
complex(const complex<T>& c) : re(c.real()), im(c.imag()) { }
// ...
};
complex<float> cf4 {2.1,2.9}; // ouch! narrows
complex<float> cf5 {cd}; // ouch! narrows
I consider this yet another reason to be consistent in the use of the {} notation for initialization.
23.4.6.1. Templates and Constructors
To minimize the chances of confusion, I explicitly added a default copy constructor. Leaving it out would not change the meaning of the definition: complex would still get a default copy constructor. For technical reasons, a template constructor is never used to generate a copy constructor, so without the explicitly declared copy constructor, a default copy constructor would have been generated. Similarly, copy assignments, move constructors, and move assignments (§17.5.1, §17.6, §19.3.1) must be defined as non-template operators or the default versions will be generated.
23.4.6.2. Templates and virtual
A member template cannot be virtual. For example:
class Shape {
// ...
template<typename T>
virtual bool intersect(const T&) const =0; // error: virtual template
};
This must be illegal. If it were allowed, the traditional virtual function table technique for implementing virtual functions (§3.2.3) could not be used. The linker would have to add a new entry to the virtual table for class Shape each time someone called intersect() with a new argument type. Complicating the implementation of the linker in this way was considered unacceptable. In particular, handling dynamic linking would require implementation techniques rather different from what is most commonly used.
23.4.6.3. Use of Nesting
In general, it is a good idea to keep information as local as possible. That way, a name is easier to find and less likely to interfere with anything else in a program. This line of thinking leads to types being defined as members. Doing so is often a good idea. However, for members of class templates we must consider if the parameterization is appropriate for a member type. Formally, a member of a template depends on all of a template’s arguments. That can have unfortunate side effects in cases where the behavior of the member does not in fact use every template argument. A famous example is a link type of a linked list. Consider:
template<typename T, typename Allocator>
class List {
private:
struct Link {
T val;
Link* succ;
Link* prev;
};
// ...
};
Here, Link is an implementation detail of List. Thus, it seems a perfect example of a type best defined in the scope of List and even kept private. This has been a popular design and generally works very well. But surprisingly, it can imply performance cost compared to using a nonlocalLink type. Assume that no member of Link depends on the Allocator parameter, and that we need List<double,My_allocator> and List<double,Your_allocator>. Now List<double,My_allocator>::Link and List<double,Your_allocator>::Link are different types, so code using them cannot (without clever optimizers) be identical. That is, making Link a member when it uses only one of List’s two template parameters implies some code bloat. This leads us to consider a design where Link isn’t a member:
template<typename T, typename Allocator>
class List;
template<typename T>
class Link {
template<typename U, typename A>
friend class List;
T val;
Link* succ;
Link* prev;
};
template<typename T, typename Allocator>
class List {
// ...
};
I made all members of Link private and granted List access. Except for making the name Link nonlocal, this preserves the design intent that Link is an implementation detail of List.
But what if a nested class is not considered an implementation detail? That is, what if we need an associated type that is meant for a variety of users? Consider:
template<typename T, typename A>
class List {
public:
class Iterator {
Link<T>* current_position;
public:
// ... usual iterator operations ...
};
Iterator<T,A> begin();
Iterator<T,A> end();
// ...
};
Here, the member type List<T,A>::Iterator (obviously) does not use the second template argument A. However, because Iterator is a member and therefore formally depends on A (the compiler doesn’t know anything to the contrary), we can’t write a function to process Lists independently of how they were constructed using allocators:
void fct(List<int>::Iterator b, List<int>::Iterator e) // error: List takes two arguments
{
auto p = find(b,e,17);
// ...
}
void user(List<int,My_allocator>& lm, List<int,Your_allocator>& ly)
{
fct(lm.begin(),lm.end());
fct(ly.begin(),ly.end());
}
Instead, we need to write a function template with a dependence on the allocator argument:
void fct(List<int,My_allocator>::Iterator b, List<int,My_allocator>::Iterator e)
{
auto p = find(b,e,17);
// ...
}
However, that breaks our user():
void user(List<int,My_allocator>& lm, List<int,Your_allocator>& ly)
{
fct(lm.begin(),lm.end());
fct(ly.begin(),ly.end()); // error: fct takes List<int,My_allocator>::Iterators
}
We could make fct a template and generate separate specializations for each allocator. However, that would generate a new specialization for every use of Iterator, so this could lead to significant code bloat [Tsafrir,2009]. Again, we solve the problem by moving Link out of the class template:
template<typename T>
struct Iterator {
Link<T>* current_position;
};
template<typename T, typename A>
class List {
public:
Iterator<T> begin();
Iterator<T> end();
// ...
};
This makes iterators for every List with the same first template argument interchangeable as far as their types are concerned. In this case, that was exactly what we wanted. Our user() now works as defined. Had fct() been defined to be a function template, there would have been only one copy (instantiation) of the definition of fct(). My rule of thumb is “Avoid nested types in templates unless they genuinely rely on every template parameter.” This is a special case of the general rule to avoid unnecessary dependencies in code.
23.4.7. Friends
As shown in §23.4.6.3, a template class can designate functions as friends. Consider the Matrix and Vector example from §19.4. Typically, both Matrix and Vector will be templates:
template<typename T> class Matrix;
template<typename T>
class Vector {
T v[4];
public:
friend Vector operator*<>(const Matrix<T>&, const Vector&);
// ...
};
template<typename T>
class Matrix {
Vector<T> v[4];
public:
friend Vector<T> operator*<>(const Matrix&, const Vector<T>&);
// ...
};
The <> after the name of the friend function is needed to make clear that the friend is a template function. Without the <>, a non-template function would be assumed. The multiplication operator can then be defined to access data from Vector and Matrix directly:
template<typename T>
Vector<T> operator*(const Matrix<T>& m, const Vector<T>& v)
{
Vector<T> r;
// ... use m.v[i] and v.v[i] for direct access to elements ...
return r;
}
Friends do not affect the scope in which the template class is defined, nor do they affect the scope in which the template is used. Instead, friend functions and operators are found using a lookup based on their argument types (§14.2.4, §18.2.5, §iso.11.3). Like a member function, a friend function is instantiated only if it is used (§26.2.1).
Like other classes, a class template can designate other classes as friends. For example:
class C;
using C2 = C;
template<typename T>
class My_class {
friend C; // OK: C is a class
friend C2; // OK: C2 is an alias for a class
friend C3; // error: no class C3 in scope
friend class C4; // OK: introduces a new class C4
};
Naturally, the interesting cases are those where the friend depends on a template argument. For example:
template<typename T>
class my_other_class {
friend T; // my argument is my friend!
friend My_class<T>; // My_class with the corresponding argument is my friend
friend class T; // error: redundant "class"
};
As ever, friendship is neither inherited nor transitive (§19.4). For example, C has not become a friend of My_other_class<int> even though My_class<int> is a friend and C is a friend of My_class<int>.
We cannot directly make a template a friend of a class, but we can make a friend declaration a template. For example:
template<typename T, typename A>
class List;
template<typename T>
class Link {
template<typename U, typename A>
friend class List;
// ...
};
Unfortunately, there is no way of saying that Link<X> should only be a friend of List<X>.
Friend classes are designed to allow the representation of small clusters of closely related concepts. A complicated pattern of friendship is almost certainly a design error.
23.5. Function Templates
For many people, the first and most obvious use of templates is to define and use container classes such as vector (§31.4), list (§31.4.2), and map (§31.4.3). Soon after, the need for function templates to manipulate such containers arises. Sorting a vector is a simple example:
template<typename T> void sort(vector<T>&); // declaration
void f(vector<int>& vi, vector<string>& vs)
{
sort(vi); // sort(vector<int>&);
sort(vs); // sort(vector<string>&);
}
When a function template is called, the types of the function arguments determine which version of the template is used; that is, the template arguments are deduced from the function arguments (§23.5.2).
Naturally, the function template must be defined somewhere (§23.7):
template<typename T>
void sort(vector<T>& v) // definition
// Shell sort (Knuth, Vol. 3, pg. 84)
{
const size_t n = v.size();
for (int gap=n/2; 0<gap; gap/=2)
for (int i=gap; i<n; i++)
for (int j=i–gap; 0<=j; j–=gap)
if (v[j+gap]<v[j]) { // swap v[j] and v[j+gap]
T temp = v[j];
v[j] = v[j+gap];
v[j+gap] = temp;
}
}
Please compare this definition to the sort() defined in §12.5. This templatized version is cleaner and shorter because it can rely on more information about the type of the elements it sorts. Typically, it is also faster because it doesn’t rely on a pointer to function for the comparison. This implies that no indirect function calls are needed and that inlining a simple < is easy.
A further simplification is to use the standard-library template swap() (§35.5.2) to reduce the action to its natural form:
if (v[j+gap]<v[j])
swap(v[j],v[j+gap]);
This does not introduce any new overhead. Better yet, the standard-library swap() uses move semantics, so we may see a speedup (§35.5.2).
In this example, operator < is used for comparison. However, not every type has a < operator. This limits the use of this version of sort(), but the limitation is easily avoided by adding an argument (see §25.2.3). For example:
template<typename T, typename Compare = std::less<T>>
void sort(vector<T>& v) // definition
// Shell sort (Knuth, Vol. 3, pg. 84)
{
Compare cmp; // make a default Compare object
const size_t n = v.size();
for (int gap=n/2; 0<gap; gap/=2)
for (int i=gap; i<n; i++)
for (int j=i–gap; 0<=j; j–=gap)
if (cmp(v[j+gap],v[j]))
swap(v[j],v[j+gap]);
}
We can now sort using the default comparison operation (<) or supply our own:
struct No_case {
bool operator()(const string& a, const string& b) const; // compare case insensitive
};
void f(vector<int>& vi, vector<string>& vs)
{
sort(vi); // sort(vector<int>&)
sort<int,std::greater<int>>(vi); // sort(vector<int>&) using greater
sort(vs); // sort(vector<string>&)
sort<string,No_case>(vs); // sort(vector<string>&) using No_case
}
Unfortunately, the rule that only trailing template arguments can be specified leads us to have to specify (rather than deduce) the element type when we specify the comparison operations.
The explicit specification of function template arguments is explained in §23.5.2.
23.5.1. Function Template Arguments
Function templates are essential for writing generic algorithms to be applied to a wide variety of container types (§3.4.2, §32.2). The ability to deduce template arguments for a call from the function arguments is crucial.
A compiler can deduce type and non-type arguments from a call, provided the function argument list uniquely identifies the set of template arguments. For example:
template<typename T, int max>
struct Buffer {
T buf[max];
public:
// ...
};
template<typename T, int max>
T& lookup(Buffer<T,max>& b, const char* p);
Record& f(Buffer<string,128>& buf, const char* p)
{
return lookup(buf,p); // use the lookup() where T is string and i is 128
}
Here, lookup()’s T is deduced to be string and max is deduced to be 128.
Note that class template parameters are never deduced. The reason is that the flexibility provided by several constructors for a class would make such deduction impossible in many cases and obscure in many more. Instead, specialization (§25.3) provides a mechanism for implicitly choosing between alternative definitions of a template. If we need to create an object of a deduced type, we can often do that by calling a function to do the deduction (and creation). For example, consider a simple variant of the standard library’s make_pair() (§34.2.4.1):
template<typename T1, typename T2>
pair<T1,T2> make_pair(T1 a, T2 b)
{
return {a,b};
}
auto x = make_pair(1,2); // x is a pair<int,int>
auto y = make_pair(string("New York"),7.7); // y is a pair<string,double>
If a template argument cannot be deduced from the function arguments (§23.5.2), we must specify it explicitly. This is done in the same way that template arguments are explicitly specified for a template class (§25.2, §25.3). For example:
template<typename T>
T* create(); // make a T and return a pointer to it
void f()
{
vector<int> v; // class, template argument int
int* p = create<int>(); // function, template argument int
int* q = create(); // error: can't deduce template argument
}
This use of explicit specification to provide a return type for a function template is very common. It allows us to define families of object creation functions (e.g., create()) and conversion functions (e.g., §27.2.2). The syntax for static_cast, dynamic_cast, etc. (§11.5.2, §22.2.1), matches theexplicitly qualified function template syntax.
Default template arguments can be used to simplify explicit qualification in some cases (§25.2.5.1).
23.5.2. Function Template Argument Deduction
A compiler can deduce a type template argument, T or TT, and a non-type template argument, I, from a template function argument with a type composed of the following constructs (§iso.14.8.2.1):
Here, args_TI is a parameter list from which a T or an I can be determined by recursive application of these rules, and args is a parameter list that does not allow deduction. If not all parameters can be deduced in this way, a call is ambiguous. For example:
template<typename T, typename U>
void f(const T*, U(*)(U));
int g(int);
void h(const char* p)
{
f(p,g); // T is char, U is int
f(p,h); // error: can't deduce U
}
Looking at the arguments of the first call of f(), we easily deduce the template arguments. Looking at the second call of f(), we see that h() doesn’t match the pattern U(*)(U) because h()’s argument and return types differ.
If a template parameter can be deduced from more than one function argument, the same type must be the result of each deduction. Otherwise, the call is an error. For example:
template<typename T>
void f(T i, T* p);
void g(int i)
{
f(i,&i); // OK
f(i,"Remember!"); // error, ambiguous: T is int or T is const char?
}
23.5.2.1. Reference Deduction
It can be useful to have different actions taken for lvalues and rvalues. Consider a class for holding an {integer,pointer} pair:
template<typename T>
class Xref {
public:
Xref(int i, T* p) // store a pointer: Xref is the owner
:index{i}, elem{p}, owner{true}
{}
Xref(int i, T& r) // store a pointer to r, owned by someone else
:index{i}, elem{&r}, owner{false}
{}
Xref(int i, T&& r) // move r into Xref, Xref is the owner
:index{i}, elem{new T{move(r)}}, owner{true}
{}
~Xref()
{
if(owned) delete elem;
}
// ...
private:
int index;
T* elem;
bool owned;
};
So:
string x {"There and back again"};
Xref<string> r1 {7,"Here"}; // r1 owns a copy of string{"Here"}
Xref<string> r2 {9,x}; // r2 just refers to x
Xref<string> r3 {3,new string{"There"}}; // r3 owns the string{"There"}
Here, r1 picks Xref(int,string&&) because x is an rvalue. Similarly, r2 picks Xref(int,string&) because x is an lvalue.
Lvalues and rvalues are distinguished by template argument deduction: an lvalue of type X is deduced as an X& and an rvalue as X. This differs from the binding of values to non-template argument rvalue references (§12.2.1) but is especially useful for argument forwarding (§35.5.1). Consider writing a factory function that make Xrefs on the free store and returns unique_ptrs to them:
template<typename T>
T&& std::forward(typename remove_reference<T>::type& t) noexcept; // §35.5.1
template<typename T>
T&& std::forward(typename remove_reference<T>::type&& t) noexcept;
template<typename TT, typename A>
unique_ptr<TT> make_unique(int i, A&& a) // simple variant of make_shared (§34.3.2)
{
return unique_ptr<TT>{new TT{i,forward<A>(a)}};
}
We want make_unique<T>(arg) to construct a T from an arg without making any spurious copies. To do that, it is essential that the lvalue/rvalue distinction is maintained. Consider:
auto p1 = make_unique<Xref<string>>(7,"Here");
"Here" is an rvalue, so forward(string&&) is called, passing along an rvalue, so that Xref(int,string&&) is called to move from the string holding "Here".
The more interesting (subtle) case is:
auto p2 = make_unique<Xref<string>>(9,x);
Here, x is an lvalue, so forward(string&) is called, passing along an lvalue: forward()’s T is deduced to string& so that the return value becomes string& &&, which means string& (§7.7.3). Thus, Xref(int,string&) is called for the lvalue x, so that x is copied.
Unfortunately, make_unique() is not part of the standard library, but it is widely supported nevertheless. Defining a make_unique() that can take arbitrary arguments is relatively easy using a variadic template for forwarding (§28.6.3).
23.5.3. Function Template Overloading
We can declare several function templates with the same name and even declare a combination of function templates and ordinary functions with the same name. When an overloaded function is called, overload resolution is necessary to find the right function or function template to invoke. For example:
template<typename T>
T sqrt(T);
template<typename T>
complex<T> sqrt(complex<T>);
double sqrt(double);
void f(complex<double> z)
{
sqrt(2); // sqrt<int>(int)
sqrt(2.0); // sqrt(double)
sqrt(z); // sqrt<double>(complex<double>)
}
In the same way that a function template is a generalization of the notion of a function, the rules for resolution in the presence of function templates are generalizations of the function overload resolution rules. Basically, for each template we find the specialization that is best for the set of function arguments. Then, we apply the usual function overload resolution rules to these specializations and all ordinary functions (§iso.14.8.3):
[1] Find the set of function template specializations (§23.2.2) that will take part in overload resolution. Do this by considering each function template and deciding which template arguments, if any, would be used if no other function templates or functions of the same name were in scope. For the call sqrt(z), this makes sqrt<double>(complex<double>) and sqrt<complex<double>>(complex<double>) candidates. See also §23.5.3.2.
[2] If two function templates can be called and one is more specialized than the other (§25.3.3), consider only the most specialized template function in the following steps. For the call sqrt(z), this means that sqrt<double>(complex<double>) is preferred over sqrt<complex<double>>(complex<double>): any call that matches sqrt<T>(complex<T>) also matches sqrt<T>(T).
[3] Do overload resolution for this set of functions, plus any ordinary functions, as for ordinary functions (§12.3). If a function template’s argument has been determined by template argument deduction (§23.5.2), that argument cannot also have promotions, standard conversions, or user-defined conversions applied. For sqrt(2), sqrt<int>(int) is an exact match, so it is preferred over sqrt(double).
[4] If a function and a specialization are equally good matches, the function is preferred. Consequently, sqrt(double) is preferred over sqrt<double>(double) for sqrt(2.0).
[5] If no match is found, the call is an error. If we end up with two or more equally good matches, the call is ambiguous and is an error.
For example:
template<typename T>
T max(T,T);
const int s = 7;
void k()
{
max(1,2); // max<int>(1,2)
max('a','b'); // max<char>('a','b')
max(2.7,4.9); // max<double>(2.7,4.9)
max(s,7); // max<int>(int{s},7) (trivial conversion used)
max('a',1); // error: ambiguous: max<char,char>() or max<int,int>()?
max(2.7,4); // error: ambiguous: max<double,double>() or max<int,int>()?
}
The problem with the last two calls is that we don’t apply promotions and standard conversions until after template parameters have been uniquely determined. There is no rule telling the compiler to prefer one resolution over the other. In most cases, it is probably good that the language rules leave subtle decisions in the hands of the programmer. The alternative to surprising ambiguity errors is surprising results from unexpected resolutions. People’s “intuitions” about overload resolution differ dramatically, so it is impossible to design a perfectly intuitive set of overload resolution rules.
23.5.3.1. Ambiguity Resolution
We could resolve the two ambiguities by explicit qualification:
void f()
{
max<int>('a',1); // max<int>(int('a'),1)
max<double>(2.7,4); // max<double>(2.7,double(4))
}
Alternatively, we could add suitable declarations:
inline int max(int i, int j) { return max<int>(i,j); }
inline double max(int i, double d) { return max<double>(i,d); }
inline double max(double d, int i) { return max<double>(d,i); }
inline double max(double d1, double d2) { return max<double>(d1,d2); }
void g()
{
max('a',1); // max(int('a'),1)
max(2.7,4); // max(2.7,4)
}
For ordinary functions, ordinary overloading rules (§12.3) apply, and the use of inline ensures that no extra overhead is imposed.
The definition of max() is trivial, so we could have implemented the comparison directly rather than calling a specialization of max(). However, using an explicit specialization of the template is an easy way of defining such resolution functions and can help maintenance by avoiding almost identical code in several functions.
23.5.3.2. Argument Substitution Failure
When looking for a best match for a set of arguments for a function template, the compiler considers whether the argument can be used in the way required by the complete function template declaration (including the return type). For example:
template<typename Iter>
typename Iter::value_type mean(Iter first, Iter last);
void f(vector<int>& v, int* p, int n)
{
auto x = mean(v.begin(),v.end()); // OK
auto y = mean(p,p+n); // error
}
Here, the initialization of x succeeds because the arguments match and vector<int>::iterator has a member called value_type. The initialization of y fails because even though the arguments match, int* does not have a member called value_type, so we cannot say:
int*::value_type mean(int*,int*); // int* does not have a member called value_type
However, what if there were another definition of mean()?
template<typename Iter>
typename Iter::value_type mean(Iter first, Iter last); // #1
template<typename T>
T mean(T*,T*); // #2
void f(vector<int>& v, int* p, int n)
{
auto x = mean(v.begin(),v.end()); // OK: call #1
auto y = mean(p,p+n); // OK: call #2
}
This works: both initializations succeed. But why didn’t we get an error when trying to match mean(p,p+n) with the first template definition? The arguments match perfectly, but by substituting in the actual template argument (int*), we get the function declaration:
int*::value_type mean(int*,int*); // int* does not have a member called value_type
That is garbage, of course: a pointer does not have a member value_type. Fortunately, considering this possible declaration is not by itself an error. There is a language rule (§iso.14.8.2) that says that such a substitution failure is not an error. It simply causes the template to be ignored; that is, the template does not contribute a specialization to the overload set. That done, mean(p,p+n) matches declaration #2, which is called.
Without the “substitution error is not a failure” rule, we would get compile-time errors even when error-free alternatives (such as #2) are available. More, this rule gives us a general tool for selecting among templates. Techniques based on this rule are described in §28.4. In particular, the standard library provides enable_if to simplify conditional definition of templates (§35.4.2).
The rule is known under the unpronounceable acronym SFINAE (Substitution Failure Is Not An Error). SFINAE is often used as a verb with the “F” pronounced as a “v”: “I SFINAEd away that constructor.” That sounds quite impressive, but I tend to avoid this jargon. “The constructor was eliminated by a substitution failure” is clearer for most people and does less violence to the English language.
So, if – in the process of generating a candidate function to resolve a function call – the compiler finds itself generating a template specialization that would be nonsensical, that candidate is not entered into the overloading set. A template specialization is considered nonsensical if it would lead to a type error. In this, we consider only a declaration; template function definitions and the definition of class members are not considered (or generated) unless they are actually used. For example:
template<typename Iter>
Iter mean(Iter first, Iter last) // #1
{
typename Iter::value_type = *first;
// ...
}
template<typename T>
T* mean(T*,T*); // #2
void f(vector<int>& v, int* p, int n)
{
auto x = mean(v.begin(),v.end()); // OK: call #1
auto y = mean(p,p+n); // error: ambiguous
}
The declaration of mean() #1 is fine for mean(p,p+n). The compiler does not start to instantiate the body of that mean() and eliminate it because of the type error.
Here, the result is an ambiguity error. Had mean() #2 not been present, declaration #1 would have been chosen and we would have suffered an instantiation-time error. Thus, a function may be chosen as the best match yet still fail to compile.
23.5.3.3. Overloading and Derivation
The overload resolution rules ensure that function templates interact properly with inheritance:
template<typename T>
class B { /* ... */ };
template<typename T>
class D : public B<T> { /* ... */ };
template<typename T> void f(B<T>*);
void g(B<int>* pb, D<int>* pd)
{
f(pb); // f<int>(pb) of course
f(pd); // f<int>(static_cast<B<int>*>(pd));
// standard conversion D<int>* to B<int>* used
}
In this example, the function template f() accepts a B<T>* for any type T. We have an argument of type D<int>*, so the compiler easily deduces that by choosing T to be int, the call can be uniquely resolved to a call of f(B<int>*).
23.5.3.4. Overloading and Non-Deduced Parameters
A function argument that is not involved in the deduction of a template parameter is treated exactly as an argument of a non-template function. In particular, the usual conversion rules hold. Consider:
template<typename T, typename C>
T get_nth(C& p, int n); // get the nth element
This function presumably returns the value of the nth element of a container of type C. Because C has to be deduced from an actual argument of get_nth() in a call, conversions are not applicable to the first argument. However, the second argument is perfectly ordinary, so the full range of possible conversions is considered. For example:
struct Index {
operator int();
// ...
};
void f(vector<int>& v, short s, Index i)
{
int i1 = get_nth<int>(v,2); // exact match
int i2 = get_nth<int>(v,s); // standard conversion: short to int
int i3 = get_nth<int>(v,i); // user-defined conversion: Index to int
}
This notation is sometimes called explicit specialization (§23.5.1).
23.6. Template Aliases
We can define an alias for a type with the using syntax or with the typedef syntax (§6.5). The using syntax is more general in the important sense that it can be used to define an alias for a template with some of its arguments bound. Consider:
template<typename T, typename Allocator = allocator<T>> vector;
using Cvec = vector<char>; // both arguments are bound
Cvec vc = {'a', 'b', 'c'}; // vc is a vector<char,allocator<char>>
template<typename T>
using Vec = vector<T,My_alloc<T>>; // vector using my allocator (2nd argument is bound)
Vec<int> fib = {0, 1, 1, 2, 3, 5, 8, 13}; // fib is a vector<int,My_alloc<int>>
In general, if we bind all arguments of a template, we get a type, but if we bind only some, we get a template. Note that what we get from using in an alias definition is always an alias. That is, when we use the alias, it is completely equivalent to a use of the original template. For example:
vector<char,alloc<char>> vc2 = vc; // vc2 and vc are of the same type
vector<int,My_alloc<int>> verbose = fib; // verbose and fib are of the same type
The equivalence of the alias and the original template implies that if you specialize the template, you (correctly) get the specializations when you use the alias. For example:
template<int>
struct int_exact_traits { // idea: int_exact_traits<N>::type is a type with exactly N bits
using type = int;
};
template<>
struct int_exact_traits<8> {
using type = char;
};
template<>
struct int_exact_traits<16> {
using type = short;
};
template<int N>
using int_exact = typename int_exact_traits<N>::type; // define alias for convenient notation
int_exact<8> a = 7; // int_exact<8> is an int with 8 bits
If specializations did not get used through the alias, we couldn’t claim that int_exact was simply an alias for int_exact_traits<N>::type; they would behave differently. On the other hand, you cannot define a specialization of an alias. If you had been able to, it would have been rather easy for a human reader to get confused about what was specialized, so no syntax is provided for specializing an alias.
23.7. Source Code Organization
There are three reasonably obvious ways of organizing code using templates:
[1] Include template definitions before their use in a translation unit.
[2] Include template declarations (only) before their use in a translation unit. Include definitions of templates later in the translation unit (potentially after their use).
[3] Include template declarations (only) before their use in a translation unit. Define the templates in some other translation unit.
For technical and historical reasons, option [3], the separate compilation of template definitions and their uses, is not offered. By far the most common approach is to include (usually #include) the definition of the templates you use in every translation unit in which you use them and rely on your implementation to optimize compile times and eliminate object code duplication. For example, I might provide a template out() in a header out.h:
// file out.h:
#include<iostream>
template<typename T>
void out(const T& t)
{
std::cerr << t;
}
We would #include this header wherever out() was needed. For example:
// file user1.cpp:
#include "out.h"
// use out()
and
// file user2.cpp:
#include "out.h"
// use out()
That is, the definition of out() and all declarations on which it depends are #included in several different compilation units. It is up to the compiler to generate code when needed (only) and to optimize the process of reading redundant definitions. This strategy treats template functions the same way as inline functions.
An obvious problem with this strategy is that users may accidentally come to depend on declarations included only for the benefit of the definition of out(). This danger can be limited by taking approach [2] “include template definitions later,” by using namespaces, by avoiding macros, and generally by reducing the amount of information included. The ideal is to minimize a template definition’s dependency on its environment.
To use the “include template definitions later” approach for our simple out() example, we first split out.h into two. The declarations go into a .h file:
// file outdecl.h:
template<typename T>
void out(const T& t);
The definitions go into out.cpp:
// file out.cpp:
#include<iostream>
template<typename T>
void out(const T& t)
{
std::cerr << t;
}
A user now #includes both:
// file user3.cpp:
#include "out.h"
// use out()
#include "out.cpp"
This minimizes the chances of the implementation of the templates having undesirable effects on the user code. Unfortunately, it also increases the chances that something in the user code (say, a macro) will have an undesirable effect on the template definitions.
As ever, non-inline, non-template functions and static members (§16.2.12) must have a unique definition in some compilation unit. This implies that such members are best not used for templates that are otherwise included in many translation units. As shown with out(), the definition of a template function may be replicated in different translation units, so beware of contexts that might subtly change the meaning of a definition:
// file user1.cpp:
#include "out.h"
// use out()
and
// file user4.cpp:
#define std MyLib
#include "out.c"
// use out()
This sneaky and error-prone use of a macro changes the definition of out so that user4.cpp’s definition differs from user1.cpp’s. This is an error, but it is an error that an implementation may not catch. This kind of error can be very hard to detect in large programs, so be careful to minimize context dependencies of templates and be very suspicious about macros (§12.6).
If you need more control over the context of instantiation, you can use explicit instantiation and extern templates (§26.2.2).
23.7.1. Linkage
The rules for linkage of templates are the rules for linkage of the generated classes and functions (§15.2, §15.2.3). This implies that if the layout of a class template or the definition of an inline function template changes, all code that uses that class or function must be recompiled.
For templates defined in header files and included “everywhere” this can imply a lot of recompilation because templates tend to include a lot of information in header files, more than non-template code using .cpp files. In particular, if dynamically linked libraries are used, care has to be taken that all uses of a template are consistently defined.
Sometimes, it is possible to minimize the exposure to changes in complicated template libraries by encapsulating their use in functions with non-template interfaces. For example, I might like to implement some computations using a general numerical library supporting a wide variety of types (e.g., Chapter 29, §40.4, §40.5, §40.6). However, I often know the type used for my calculations. For example, in a program I may consistently use doubles and vector<double>. In that case, I could define:
double accum(const vector<double>& v)
{
return accumulate(v.begin(),v.end(),0.0);
}
Given that, I can use the simple non-templated declaration of accum() in my code:
double accum(const vector<double>& v);
The dependence on std::accumulate has disappeared into a .cpp file that is not seen by the rest of my code. Also, I suffer the compilation-time overhead of a #include<numeric> only in that .cpp file.
Note that I took the opportunity to simplify the interface to accum() compared to std::accumulate(). The generality that is a key attribute of good template libraries can be seen as a source of complexity in a particular application.
I suspect that I would not use this technique for standard-library templates. Those are stable over years and known to the implementations. In particular, I did not bother to try to encapsulate vector<double>. However, for more complex, esoteric, or frequently changing template libraries, such encapsulation can be useful.
23.8. Advice
[1] Use templates to express algorithms that apply to many argument types; §23.1.
[2] Use templates to express containers; §23.2.
[3] Note that template<class T> and template<typename T> are synonymous; §23.2.
[4] When defining a template, first design and debug a non-template version; later generalize by adding parameters; §23.2.1.
[5] Templates are type-safe, but checking happens too late; §23.3.
[6] When designing a template, carefully consider the concepts (requirements) assumed for its template arguments; §23.3.
[7] If a class template should be copyable, give it a non-template copy constructor and a non-template copy assignment; §23.4.6.1.
[8] If a class template should be movable, give it a non-template move constructor and a non-template move assignment; §23.4.6.1.
[9] A virtual function member cannot be a template member function; §23.4.6.2.
[10] Define a type as a member of a template only if it depends on all the class template’s arguments; §23.4.6.3.
[11] Use function templates to deduce class template argument types; §23.5.1.
[12] Overload function templates to get the same semantics for a variety of argument types; §23.5.3.
[13] Use argument substitution failure to provide just the right set of functions for a program; §23.5.3.2.
[14] Use template aliases to simplify notation and hide implementation details; §23.6.
[15] There is no separate compilation of templates: #include template definitions in every translation unit that uses them; §23.7.
[16] Use ordinary functions as interfaces to code that cannot deal with templates; §23.7.1.
[17] Separately compile large templates and templates with nontrivial context dependencies; §23.7.