# Chapter 16. Templates and Generic Programming
Templates are the foundation for generic programming in C++. |A template is a blueprint or formula for creating classes or functions.
## 16.1 Defining a Template
### 16.1.1 Function Templates
A function template is a formula from which we can generate type-specific versions of that function.
```cpp
template <typename T>
int compare(const T &v1, const T &v2) {
if (v1 < v2) return -1;
if (v2 < v1) return 1;
return 0;
}
```
In a template definition, the template parameter list cannot be empty.
The compiler uses the deduced template parameters`9s) to instantiate a specific version of the function for us.
**Nontype Template Parameters**
These compiler-generated functions are generally referred to as an instantiation of the template.
```cpp
template<unsigned N, unsigned M>
int compare(const char (&p1)[N], const char (&p2)[M]) {
return strcmp(p1, p2);
}
compare("hi", "mom");
// int compare(const char (&p1)[3], const char (&p2)[4]);
```
Template arguments used for nontype template parameters must be constant expressions.
The `inline` or `constexpr` specifier follows the template parameter list and precedes the return type:
```cpp
template <typename T> inline T min(const T&, const T&)
```
When the compiler sees the definition of a template, it does not generate code. It generates code only when we instantiate a specific instance of the template.
Definitions of function templates and member functions of class templates are ordinarily put into header files.
The fact that code is not generated until a template is instantiated affects when we learn about compilation errors in the code inside the template.
The first stage is when we compile the template itself. The compiler generally can't find many errors at this stage. The compiler can detect syntax errors - such as forgetting a semicolon or misspelling a variable name - but not much else.
The third time when errors are detected is during instantiation. It is only then that type-related errors can be found.
### 16.1.2 Class Templates
A class template is a blueprint for generating classes. Class templates differ from function templates in that the compiler cannot deduce the template parameter type(s) for a class template. To use a class template we must supply additional information inside angle brackets following the template's name.
Extra information is a list of explicit template arguments that are bound to the template's parameters. The compiler uses these template arguments to instantiate a specific class from the template.
As with any class, we can define the member functions of a class template either inside or outside of the class body. As with any other class, members defined inside the class body are implicitly inline.
A member function defined outside the class template body starts with the keyword template followed by the class' template parameter list.
```cpp
tempalte <typename T>
ret-type Blob<T>::member-name(parm-list)
```
By default, a member of an instantiated class template is instantiated only if the member is used.
```cpp
tempalte <typename T>
bool operator==(const Blob<T>&, const Blob<T>&);
template <typename T> class Blob {
friend bool operator==<T>(const Blob<T>&, const Blob<T>&);
};
template <typename T> class Pal;
class C {
template <typename T> friend class Pal2;
};
template <typenamte T> class C2 {
template <typename X> friend class Pal2;
};
```
To allow all instantiations as friends, the friend declaration must use template parameter(s) that differ from those used by the class itself.
Under the new standard, we can make a template type parameter a friend:
```cpp
template <typename Type> class Bar {
friend Type;
};
```
We can define a typedef that refers to that instantiated class:
```cpp
typedef Blob<string> StrBlob;
```
The new standard lets us define a type alias for a class template:
```cpp
template<typename T> using twin = pair<T, T>;
twin<string> authors;
```
Each instantiation of `Foo` has its own instance of the static members.
### 16.1.3 Template Parameters
A template parameter name has no intrinsic meaning. Template parameters follow normal scoping rules. A name used as a template parameter may not e reused within the template:
```cpp
typedef double A;
template <typename A, typename B> void f(A a, B b) {
A tmp = a;
double B; // error: redeclares template parameter B
}
// error: illegal reuse of template parameter name V
template <typename V, typename V>
```
A template declaration must include the template parameter:
```cpp
template <typename T> int compare(const T&, const T&);
```
When we want to inform the compiler that a name represents a type, we must use the keyword `typename`, not `class`.
### 16.1.4 Member Templates
A class - either an ordinary class or a class template - may have a member function that is itself a template.
```cpp
template <typename T> void operator() (T *p) const;
double* p = new double;
DebugDelete d; // an object that can act like a delete expression
d(p); // calls DebugDelete::operator()(double*), with deletes p
int* ip = new int;
// calls operator()(int*) on a temporary DebugDelete object
DebugDelete()(ip);
```
Because calling a `DebugDelete` object deletes its given pointer, we can also use `DebugDelete` as the deleter of a `unique_ptr`.
```cpp
unique_ptr<int, DebugDelete> p(new int, DebugDelete());
```
We can also define a member template of a class template.
```cpp
template <typename T> class Blob {
template <typename It> Blob(It b, It e);
};
```
When we define a member template outside the body of a class template, we must provide the template parameter list for the class template and for the function template.
```cpp
tempalte <typename T>
template <typename It>
Blob<T>::Blob(It b, It e) : data(std::make_shared<std::vector<T>>(b, e)) {}
```
### 16.1.5 Controlling Instantiations
Under the new standard, we can avoid this overhead through an explicit instantiation. An explicit instantiation has the form.
```cpp
extern template declaration;
template declaration;
```
When the compiler sees an extern template declaration, it will not generate code for that instantiation in that file.
## 16.2 Template Argument Deduction
The process of determining the template arguments from the function arguments is known as template argument deduction.
### 16.2.1 Conversions and Template Type Parameters
* const conversions: A function parameter that is a reference to a const can be passed a reference to a nonconst object.
* Array- or function-to-pointer conversions: If the function parameter is not a reference type, then the normal pointer conversion will be applied to arguments of the array or function type. An array argument will be converted to a pointer to its first element.
```cpp
template <typename T> T fobj(T, T);
template <typename T> T fref(const T&, const T&);
string s1("a value");
fobj(s1, s2);
fref(s1, s2);
int a[10], b[42];
fobj(a, b); // calls f(int*, int*)
fref(a, b); // error: array types don't match
```
`const` conversions and array or function to pointer are the only automatic conversions for arguments to parameters with template types.
```cpp
long lng;
compare(lng, 1024); // error: cannot instantiate compare(long, int)
```
If we want to allow normal conversions on the arguments, we can define the function with two type parameters:
```cpp
template <typename A, typename B>
int flexibleCompare(const A& v1, const B& v2) {}
```
A function template can have parameters that are defined using ordinary types.
### 16.2.2 Function-Template Explicit Arguments
```cpp
template <typename T1, typename T2, typename T3>
T1 sum(T2, T3);
auto val3 = sum<long long>(i, lng); // long long sum(int, long)
```
In this case, there is no argument whose type can be used to deduce the type of `T1`.
```cpp
// poor design: users must explicitly specify all three template parameters
template <typename T1, typename T2, typename T3>
T3 alternative_sum(T2, T1);
// error: can't infer initial template parameters
auto val3 = alternative_sum<long long)(i, lng);
// ok: all three parameters are explicitly specified
auto val2 = alternative_sum<long long, int , long>(i, lng);
```
### 16.2.3 Traling Return Types and Type Transformation
Using an explicit template argument to represent a template function's return type works well when we want to let the user determine the return type.
```cpp
template <typename It>
??? &fcn(It beg, It end) {
return *beg;
}
```
To define this function, we must use a trailing return type.
```cpp
template <typename It>
auto fcn(It beg, It end) -> decltype(*beg) {
return *beg;
}
```
Type transformation template are defined in the `type_traits` header.
```cpp
remove_reference<decltype(*beg)>::type
```
### 16.2.4 Function Pointers and Argument Deduction
When we initialize or assign a function pointer from a function template, the compiler uses the type of the pointer to deduce the template argument(s).
```cpp
template <typename T> int compare(const T&, const T&);
// pf1 points to the instantiation int compare(const int&, const int&)
int (*pf1)(const int&, const int&) = compare;
```
### 16.2.5 Template Argument Deduction and References
```cpp
template <typename T> void f1(T&); // argument must be an lvalue
f1(5);
template <typename T> void f2(const T*); // can take an rvlue;
f2(5); / a const& parameter can be bound to an rvlau; T is int
```
When a function parameter is an rvalue reference, normal binding rules say that we can pass an rvalue to this parameter.
```cpp
template <typename T> void f3(T&&);
f3(42);
```
* `X& &`, `X& &&`, and `X&& &` all collapse to type `X&`
* The type `X&& &&` collapses to `X&&`
```cpp
template <typename T> void f3(T&& val) {
T t = val;
t = fcn(t);
if (val == t) { /* ... */ }
}
```
When we call f3 on an rvalue, T is int. In this case, the local variable `t` has type `int` and is initialized by copying the value of the parameter `val`. When we assign to `t`, the parameter `val` remains unchanged.
```cpp
template <typename T> void f(T&&); // binds to non const rvalue;
template <typename T> void f(const T&) // lvalues and const rvalue;
```
### 16.2.6 Understanding std::move
The standard defines move the follows:
```cpp
template <typename T>
typename remove_reference<T>::type&& move(T&& t) {
return static_cast<typename remove_reference<T>::type&&>(t);
}
```
### 16.2.7 Forwarding
A function parameter that is an rvalue reference to a template type parameter preserves the constness and lvalue/rvalue property of its corresponding arguments. `forward` returns an rvalue reference to that explicit argument type.
When used with a function parameter that is an rvalue reference to the template type parameter (T&&), forward preserves all the details about an argument's type.
## 16.3 Overloading and Templates
Function matching is affected by the presence of function templates in the following ways:
* The candidate functions for a call include any function-template instantiation for which template argument deduction succeeds.
* The candidate function templates are always viable because template argument deduction will have eliminated any templates that are not viable.
* As usual, the viable functions are ranked by the conversions, if any, needed to make the call.
* Also as usual, if exactly one function provides a better match than any of the others, that function is selected. However, if there are several functions that provide an equally good match, then:
* If there is only one nontemplate function in the set of equally good matches, the nontemplate function is called.
* If there are no nontemplate functions in the set, but there are multiple function templates, and one of these templates is more specialized than any of the others, the more specialized function template is called.
* Otherwise, the call is ambiguous.
When there are several overloaded templates that provide an equally good match for a call, the most specialized version if preferred.
## 16.4 Variadic Templates
A variadic template is a template function or class that can take a varying number of parameter. The varying parameters are known as a parameter pack. There are two kinds of parameter packs: A template parameter pack represents zero or more template parameters, and a function parameter pack represents zero or more function parameters.
```cpp
template <typename T, typename... Args>
void foo(const T &t, const Args& ... rest);
int i = 0; double d = 3.14; string s = "how now brown cow";
foo(i, s, 42, d);
foo(s, 42, "hi");
foo(d, s);
foo("hi");
```
`sizeof...` returns a constant expression and does not evaluate its argument:
```cpp
template<typename ...Args> void g(Args ... args) {
cout << sizeof...(Args) << endl; // number of type parameters
cout << sizeof...(args) << endl; // number of function parameters
}
```
### 16.4.1 Writing a Variadic Function Template
Variadic functions are often recursive. The first call processes the first argument in the pack and calls itself on the remaining arguments.
```cpp
template<typename T>
ostream &print(ostream &os, const T& t) {
return os << t;
}
template <typanem T, typename... Args>
ostream &print(ostream& os, const T& t, const Args&.. rest) {
os << t << ", ";
return print(os, rest...);
}
```
### 16.4.2 Pack Expansion
Expanding a pack separates the pack into its constituent element, applying the pattern to each element as it does so.
```cpp
template <typename T, typename... Args>
ostream & print(ostream &os, const T& t, const Args&... rest) {
os << t << ", ";
return print(os, rest...);
}
```
The first expansion expands the template parameter pack and generates the function parameter list for print. The second expansion appears in the call to print.
```cpp
template <typename... Args>
ostream &errorMsg(ostream& os, const Args&... rest) {
return print(os, debug_rep(rest)...);
}
```
That pattern says that we want to call `debug_rep` on each element in the function parameter pack rest. In contrast, the following pattern would fail to compile:
```cpp
print(os, debug_rep(rest...)); // error: no matching function to call
```
### 16.4.3 Forwarding Parameter Packs
`&&` means that each function parameter will be an rvalue reference to its corresponding argument.
```cpp
std::forward<Args>(args)...
```
expands both the template parameter pack, `Args`, and the function parameter pack, `args`. This pattern generates elements with the form:
```cpp
std::forward<Ti>(ti);
```
where `Ti` represents the type of the ith element in the template parameter pack and `ti` represents the ith element in the function parameter pack.
```cpp
svec.emplace_back(10, 'c'); /add ccccccccc as new last element
```
the pattern in the call to construct will expand to
```cpp
std::forward<int>(10), std::forward<char>(c);
```
## 16.5 Template Specializations
```cpp
// first version; can compare any two types
template <typename T> int compare(const T&, const T&);
// second version to handle string literals
template<size_t N, size_t M>
int compare(const char (&)[N], const char (&)[M]);
const char *p1 = "hi", *p2 = "mom";
compare(p1, p2);
compare("hi", "mom");
```
To handle character pointers, we can define a template specialization of the first version of compare.
To indicate that we are specializing a template, we use the keyword template followed by an empty pair of angle brackets(< >). The empty brackets indicate that arguments will be supplied for all the template parameters of the original template:
```cpp
tempalte<>
int compare(const char* const &p1, const char* const &p2);
```
It is important to realize that specialization is an instantiation; it is not an overloaded instance of the function name.
Specializations instantiate a template; they do not overload it. As a result, specializations do not affect function matching.
To enable users of `Sales_data` to use the specialization of hash, we should define this specialization in the `Sales_data` header.
A class template partial specialization is itself a template. We can partially specialize only a class template. We cannot partially specialize a function template.
```cpp
template <class T> struct remove_reference {
typedef T type;
}
template <class T> struct remove_reference<T&> // lvalue references
{ typedef T type; }
template <class T> struct remove_reference<T&&> // rvalue references
{ typedef T type; }
// decltype(42) is int, uses the original template
remove_reference<decltype(42)>::type a;
// decltype(i) is int&, uses first (T&) partial specilization
remove_reference<decltype(i)>::type b;
// decltype(std::move(i)) is int&&, uses second partial specialization
remove_reference<decltype(std::move(i))>::type c;
```
Rather than specializing the whole template, we can specialize just specific member function(s).
```cpp
template <typename T> struct Foo {
Foo(const T& t = T()) : mem(t) { }
};
template <>
void Foo<int>::Bar() {}
```
- Introduction
- Chapter 1. Getting Start
- Chapter 2. Variables and Basic Types
- Chapter 3. String, Vectors, and Arrays
- Chapter 4. Expressions
- Chapter 5. Statements
- Chapter 6. Functions
- Chapter 7. Classes
- Chapter 8. The IO Library
- Chapter 9. Sequential Containers
- Chapter 10. Generic Algorithms
- Chapter 11. Associative Container
- Chapter 12. Dynamic Memory
- Chapter 13. Copy Control
- Chapter 14. Overloaded Operations and Conversions
- Chapter 15. Object-Oriented Programming
- Chapter 16. Template Argument Deduction
- Chapter 17. Specialized Library Facilities
- Chapter 18. Tools for Large Programs
- Chapter 19. Specialized Tools and Techniques