Templates and Generic Programming
Both object-oriented programming (OOP) and generic programming deal with types that are not known at the time the program is written. The distinction between the two is that OOP deals with types that are not known until run time, whereas in generic programming the types become known during compilation.
For example, the library provides a single, generic definition of each container, such as vector. We can use that generic definition to define many different types of vectors, each of which differs from the others as to the type of elements the vector contains.
Templates are the foundation for generic programming in C++. A template is a blueprint or formula for creating classes or functions. When we use a generic type, such as vector, or a generic function, such as find, we supply the information needed to transform that blueprint into a specific class or function. That transformation happens during compilation.
Defining a Template
Imagine that we want to write a function to compare two values and indicate whether the first is less than, equal to, or greater than the second. In practice, we’d want to define several such functions, each of which will compare values of a given type.
// compare string
int compare(const string &v1, const string &v2)
// compare double
int compare(const double &v1, const double &v2)
These functions are nearly identical: The only difference between them is the type of their parameters. The function body is the same in each function.
Function Templates
Rather than defining a new function for each type, we can define a function template. A function template is a formula from which we can generate type-specific versions of that function. The template version of compare looks like:
template <typename T>
int compare(const T& l, const T& r) {
if (r < l) {
return 1;
}
if (l < r) {
return -1;
}
return 0;
}
A template definition starts with the keyword template followed by a template parameter list, which is a comma-separated list of one or more template parameters bracketed by the < and > .
The template parameter list acts much like a function parameter list. A function parameter list defines local variable(s) of a specified type but does not say how to initialize them. At run time, arguments are supplied that initialize the parameters.
When we call a function template, the compiler (ordinarily) uses the arguments of the call to deduce the template argument(s) for us. That is, when we call compare, the compiler uses the type of the arguments to determine what type to bind to the template parameter T. For example, in this call
std::cout << compare(4.5, 1.0) << std::endl;
the arguments have type double. The compiler will deduce int as the template argument and will bind that argument to the template parameter T.
Our compare function has one template type parameter. In general, we can use a type parameter as a type specifier in the same way that we use a built-in or class type specifier. In particular, a type parameter can be used to name the return type or a function parameter type, and for variable declarations or casts inside the function body:
template <typename T> T foo(T* p) {
T tmp = *p; // tmp will have the type to which p points
// ...
return tmp;
}
Each type parameter must be preceded by the keyword class or typename:
// error: must precede U with either typename or class
template <typename T, U> T calc(const T&, const U&);
These keywords have the same meaning and can be used interchangeably inside a template parameter list. A template parameter list can use both keywords:
// ok: no distinction between typename and class in a template parameter list
template <typename T, class U> calc (const T&, const U&);
It may seem more intuitive to use the keyword typename rather than class to designate a template type parameter. After all, we can use built-in (nonclass) types as a template type argument. Moreover, typename more clearly indicates that the name that follows is a type name. However, typename was added to C++ after templates were already in widespread use; some programmers continue to use class exclusively.
In addition to defining type parameters, we can define templates that take nontype parameters. A nontype parameter represents a value rather than a type. Nontype parameters are specified by using a specific type name instead of the class or typename keyword.
As an example, we can write a version of compare that will handle string literals. Such literals are arrays of const char. Because we cannot copy an array, we’ll define our parameters as references to an array. Because we’d like to be able to compare literals of different lengths, we’ll give our template two nontype parameters. The first template parameter will represent the size of the first array, and the second parameter will represent the size of the second array:
template<unsigned N, unsigned M>
int compare(const char(&p1)[N], const char(&p2)[M]) {
// note need incloude string.h first
return strcmp(p1, p2);
}
A function template can be declared inline or constexpr in the same ways as nontemplate functions. The inline or constexpr specifier follows the template parameter list and precedes the return type:
// ok: inline specifier follows the template parameter list
template <typename T> inline T min(const T&, const T&);
// error: incorrect placement of the inline specifier
inline template <typename T> T min(const T&, const T&);
Simple though it is, our initial compare function illustrates two important principles for writing generic code:
- The function parameters in the template are references to const.
- The tests in the body use only < comparisons.
However, by writing the code using only the < operator, we reduce the requirements on types that can be used with our compare function. Those types must support <, but they need not also support >.
In fact, if we were truly concerned about type independence and portability, we probably should have defined our function using the less
template <class T>
int compare(const T& l, const T& r) {
if (std::less<T>()(l, r)) {
return -1;
}
if (std::less<T>()(r, l)) {
return 1;
}
return 0;
}
The problem with our original version is that if a user calls it with two pointers and those pointers do not point to the same array, then our code is undefined.
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. Instead, as we’ve seen many times, to use a class template we must supply additional information inside angle brackets following the template’s name.
Like function templates, class templates begin with the keyword template followed by a template parameter list. In the definition of the class template (and its members), we use the template parameters as stand-ins for types or values that will be supplied when the template is used
// in Blob.h
#pragma once
#include<vector>
#include<memory>
template <typename T> class Blob {
public:
typedef T value_type;
typedef typename std::vector<T>::size_type size_type;
// constructors
Blob();
Blob(std::initializer_list<T> il);
// number of elements in the Blob
size_type size() const {
return data->size();
}
bool empty() const {
return data->empty();
}
// add and remove elements
void push_back(const T& t) {
data->push_back(t);
}
// move version;
void push_back(T&& t) {
data->push_back(std::move(t));
}
void pop_back() {
data->pop_back();
}
// element access
T& back() {
return data->back();
}
T& operator[](size_type i) {
std::string msg = "error";
check(i, msg);
return (*data)[i];
}
private:
std::shared_ptr<std::vector<T>> data;
void check(size_type i, const std::string& msg) const;
};
template<typename T>
Blob<T>::Blob()
:data(std::make_shared<std::vector<T>>()) {
}
template<typename T>
Blob<T>::Blob(std::initializer_list<T> il)
: data(std::make_shared<std::vector<T>>(il)) {
}
template<typename T>
void Blob<T>::check(size_type i, const std::string& msg) const {
if (i > data->size()) {
throw std::out_of_range(msg);
}
}
it’s worth to note in this program, I define the function in Blob.h file instead of bolb.cpp, you can try write template functions in bolb.cpp file see what happened.
As we’ve seen many times, when we use a class template, we must supply extra information. We can now see that that 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.
When the compiler instantiates a class from our Blob template, it rewrites the Blob template, replacing each instance of the template parameter T by the given template argument, which in this case is int. The compiler generates a different class for each element type we specify:
// these definitions instantiate two distinct Blob types
Blob<string> names; // Blob that holds strings
Blob<double> prices;// different element type
There is one exception to the rule that we must supply template arguments when we use a class template type. Inside the scope of the class template itself, we may use the name of the template without arguments:
#pragma once
#include"Blob.h"
template <typename T> class BlobPtr {
public:
BlobPtr() : curr(0) {}
BlobPtr(Blob<T>& a, size_t sz = 0) :
wptr(a.data), curr(sz) {
}
T& operator*() const {
auto p = check(curr, "dereference past end");
return (*p)[curr]; // (*p) is the vector to which this object points
}
// increment and decrement
BlobPtr& operator++(); // prefix operators
BlobPtr& operator--();
private:
// check returns a shared_ptr to the vector if the check succeeds
std::shared_ptr<std::vector<T>>
check(std::size_t, const std::string&) const;
// store a weak_ptr, which means the underlying vector might be destroyed
std::weak_ptr<std::vector<T>> wptr;
std::size_t curr; // current position within the array
};
Notice: the prefix increment and decrement members of BlobPtr return BlobPtr&, not BlobPtr<T>&. When we are inside the scope of a class template, the compiler treats references to the template itself as if we had supplied template arguments matching the template’s own parameters. That is, it is as if we had written:
BlobPtr<T>& operator++();
BlobPtr<T>& operator--();
When we define members outside the body of a class template, we must remember that we are not in the scope of the class until the class name is seen:
template<typename T>
inline BlobPtr<T>& BlobPtr<T>::operator++() {
BlobPtr ret = *this; // save the current value
++* this; // advance one element; prefix ++ checks the increment
return ret; // return the saved state
}
template<typename T>
inline BlobPtr<T>& BlobPtr<T>::operator--() {
BlobPtr ret = *this; // save the current value
--* this; // advance one element; prefix ++ checks the increment
return ret; // return the saved state
}
Because the return type appears outside the scope of the class, we must specify that the return type returns a BlobPtr instantiated with the same type as the class. Inside the function body, we are in the scope of the class so do not need to repeat the template argument when we define ret. When we do not supply template arguments, the compiler assumes that we are using the same type as the member’s instantiation. Hence, the definition of ret is as if we had written:
BlobPtr<T> ret = *this;
When a class contains a friend declaration, the class and the friend can independently be templates or not. A class template that has a nontemplate friend grants that friend access to all the instantiations of the template. When the friend is itself a template, the class granting friendship controls whether friendship includes all instantiations of the template or only specific instantiation(s).
