16. Templates
Video: cpp-mat-ea16.mkv
Independent concepts should be independently represented and should be combined only when needed. Otherwise unrelated concepts are bundled together or unnecessarry dependencies are created.
In modern programming languages generics provide a simple way to represent a wide range of general concepts parameterized by type(s) and a simple ways to combine them. In C++ generics are implemented as templates.
The standard library – which requires a greater degree of generality, flexibility and efficiency – is a good example of template collection.
Alternative implementation ideas
Suppose we want to implement a max function to select the greater value for many different types.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int max( int a, int b)
{
if ( a > b )
return a;
else
return b;
}
double max( double a, double b)
{
if ( a > b )
return a;
else
return b;
}
... and so on ...
How can we minimize the copy-paste effect? Just overloading many functions different only in the type of the parameter is not maintainable.
Preprocessor macro
One natural attempt is to use the preprocessor macro.
#define MAX(a,b) ((a) > (b) ? (a) : (b))The parentheses are necessary because of the possible context of the macro expansion. Still, macros have side effects:
x = MAX(a++,b);After the expansion become:
x = ((a++) > (b) ? (a++) : (b))so when a++ > b the increment of a will be executed twice.
Even when we avoid these issues, the macro is processed by the preprocessor, therefore it cannot communicate with the type system.
Templates
Ada designers described generic program units as: a restricted form of context-sensitive macro facility, and the designers of C++ claims: templates are clever kind of macros that obeys the scope, naming, and type rules of C++.
1
2
3
4
5
6
7
8
template <typename T> // same as: <class T>
T max( T a, T b)
{
if ( a > b )
return a;
else
return b;
}
The template parameter can be a type, a const expression, or a pointer to an external object or function.
Instantiation, parameter deduction
Template is not a function, template is a pattern to generate a function The concrete function is the specialization created by automatic instantiation.
1
2
3
4
5
int i, j = 3, k = 4;
double x, y = 5.1, z = 3.14;
i = max( j, k); // instantiates int max(int,int)
x = max( y, z); // instantiates double max(double,double)
The compiler deduces the parameter types, then creates a specific version. The compiler instantiates the specialization with concrete types. Parameter deduction happens during compilation time.
Templates must be placed into header files, since the compiler must read their source.
Type exquivalence:
Templates are the same type only if all type parameters are equivalent.
1
2
3
C<char,10> c1;
C<int, 10> c2; // c2 different type than c1
C<int, 25-15> c3; // c3 is the same type as of c2
Specializations
1
2
3
4
5
6
7
8
9
int i = 3, j = 4, k;
double x = 3.14, y = 4.14, z;
const int ci = 6;
k = max( i, j); // -> max(int, int)
z = max( x, y); // -> max(double, double)
k = max( i, ci); // -> max(int, int)
z = max( i, x); // -> error
In the last case the parameter deduction failes, since there is contradiction between the type of i and x. This causes a compile time error.
To fix the problem, we try introduce an other version of max with more parameters.
1
2
3
4
5
6
7
8
9
10
template <class R, class T, class S>
R max( T a, S b)
{
if ( a > b )
return a;
else
return b;
}
z = max( i, x); // error, no parameter deduction on
// return value: impossible to deduce R
Unfortunately, this does not work, since there is no parameter deduction on the return type, therefore R is not deducible. The information on R should be presented explicitly:
1
2
3
z = max<double>( i, x); // ok, return type is double
z = max<int>( i, x); // ok, return type is int
z = max<int,double,int>( i, x); // ok R, T, S is given
Explicit (full) specialization
In the earlier examples, the different versions of max used the same algorithm, only the parameters were different. There are cases, when the algorithm should be different for specific types.
1
2
3
4
5
6
7
8
9
10
11
const char *s1 = "Hello";
const char *s2 = "world";
template <> // full specialization
const char *max<const char *>(const char *s1,const char *s2)
{
return str::strcmp( s1, s2) < 0;
}
// uses full specialization
std::cout << max( s1, s2) << std::endl;
The earlier templates would match for max(const char *, const char *), but the usage of operator< would be misleading to compare pointers. Therefore we define an explicit (full) specialization, that matches for this case.
Template overloading
We can use all the templates introduced earlier together. The compiler will apply the most specialized version to instantiate.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template <class R, class T, class S> // most generic version
R max( T a, S b) // return type must be given explicitly
{
if ( a > b )
return a;
else
return b;
}
template <class T> // this specalisation used when the
T max( T a, T b) // parameters have the same type
{
if ( a > b )
return a;
else
return b;
}
template <> // explicit specialization, only for const char*
const char *max<const char *>( const char *s1, const char *s2)
{
return str::strcmp( s1, s2) < 0; // body can be different
}
int i = max(3,4); // uses line 1
double x = max<double>(3.14, 4); // uses line 9
const char *m = max( "hello", "world"); // uses line 17
Class templates
Class templates define patterns for classes.
1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T> // class template
class Matrix
{
public:
Matrix( int cols, int rows) : _t ( new T[cols * rows] ) {}
Matrix( const Matrix& rhs);
Matrix& operator=(const Matrix& rhs);
~Matrix();
// ...
private:
T* _t;
// ..
};
All of the memberfunctions of class templates are function templates. Therefore we have to put both the class template declaration and all memberfunction implementations into header files.
Template member functions have special syntax:
1
2
3
4
5
6
template <typename T>
Matrix<T>::Matrix( const Matrix& rhs) { ... }
^ ^ ^
| | |
class constructor name inside Matrix namespace
Martrix is Matrix<T>
Since class template parameters regularly cannot be deduced from constructor parameters, objects from template classes must be explicitly specialized. (Since C++17 this is not mandatory, sometimes we can use Class Template Deduction, but that is complex, and here we will not discuss it.)
1
2
3
4
5
6
7
8
9
#include "matrix.h"
int main()
{
Matrix<int> m(10,20); // Matrix object int specialization
m.at(2,3) = 1;
cout << m(2,3) << endl;
}
Class template specialization
We can specialize class templates writing a completely new version for a specific template parameter. The specialization does not need to be follow the interface of the generic version (although this is not a good design decision).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <>
class Matrix<bool>
{
public:
// possibly different interface
// ...
private:
// possibly completely different implementations
// ...
};
void f()
{
Matrix<int> mi(10,20); // use generic version
Matrix<double> md(20,40); // use generic version
Matrix<bool> mb(20,40); // use bool specialization
// ...
}
The complete example
Here we provide the template version of the vector class we implemented in Chapter 15.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// vector.h
#ifndef VECTOR_H
#define VECTOR_H
#include <cassert>
template <typename T>
class Vector
{
public:
Vector(); // constructor
Vector(const Vector& rhs); // copy constructor
Vector& operator=(const Vector& rhs); // assignment op.
~Vector(); // destructor
int size() const; // actual number of elements
T& operator[](int i); // unchecked access
T operator[](int i) const; // unchecked access, const
void push_back(T d); // append to the end
void pop_back(); // remove from end;
private:
int _size; // actual number of elements
int _capacity; // buffer size
T* _ptr; // pointer to buffer
void copy(const Vector& rhs); // private helper function
void release(); // private helper function
void grow(); // reallocate buffer
};
// the implementation goes into the same header file
template <typename T>
Vector<T>::Vector()
{
_capacity = 4; // initial buffer capacity
_size = 0; // initial size
_ptr = new T[_capacity]; // buffer dynamically allocated in heap
}
template <typename T>
Vector<T>::Vector(const Vector& rhs)
{
copy(rhs); // create and copy resources
}
template <typename T>
Vector<T>& Vector<T>::operator=(const Vector& rhs)
{
if ( this != &rhs ) // avoid x = x
{
release(); // drop old resources
copy(rhs); // create and copy new resources
}
return *this; // return this object for x = y = z
}
template <typename T>
Vector<T>::~Vector()
{
release(); // drop old resources
}
template <typename T>
void Vector<T>::copy(const Vector& rhs)
{
_capacity = rhs._capacity;
_size = rhs._size;
_ptr = new T[_capacity]; // create buffer in the heap
for (int i = 0; i < _size; ++i) // copy elements
_ptr[i] = rhs._ptr[i];
}
template <typename T>
void Vector<T>::release()
{
delete [] _ptr; // free the buffer from heap
}
template <typename T>
void Vector<T>::grow() // extend the buffer when full
{
T *_oldptr = _ptr; // to remember the old buffer
_capacity = 2 * _capacity; // double the buffer capacity
_ptr = new T[_capacity]; // allocate with new capacity
for ( int i = 0; i < _size; ++i) // copy elements from
_ptr[i] = _oldptr[i]; // old to new buffer
delete [] _oldptr; // delete the old buffer, keep the new
}
template <typename T>
int Vector<T>::size() const
{
return _size;
}
template <typename T>
T& Vector<T>::operator[](int i)
{
return _ptr[i]; // access element, no index check
}
template <typename T>
T Vector<T>::operator[](int i) const
{
return _ptr[i]; // same as above, but for constants
}
template <typename T>
void Vector<T>::push_back(T d)
{
if ( _size == _capacity ) // buffer is full
grow(); // increase the capacity
_ptr[_size] = d; // write to the next free position
++_size; // one more element inserted
}
template <typename T>
void Vector<T>::pop_back()
{
assert( _size > 0 );
--_size; // we have one element less
}
#endif /* VECTOR_H */
The client code to test our template class is te following.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <string>
#include "vector.h"
template <typename T>
void print(const vec<T>& v, char *name)
{
std::cout << s << " = [ ";
for (int i = 0; i < v.size(); ++i )
std::cout << v[i] << " ";
std::cout << "]" << std::endl;
}
int main()
{
Vector<int> x; // declare and fill x
for (int i = 0; i < 10; ++i )
x.push_back(i);
Vector<double> y; // declare and fill y
for (int i = 0; i < 15; ++i )
y.push_back(i+20.5);
std::string s;
vector<std::string> z; // declare and fill z
for (char ch = 'a'; ch < 'z'; ++ch )
{
s += ch;
z.push_back(s);
}
print(x,"x");
print(y,"y");
print(z,"z");
}