1. Homepage of Dr. Zoltán Porkoláb
    1. Home
    2. Archive
  2. Teaching
    1. Timetable
    2. Bolyai College
    3. C++ (for foreign studenst)
    4. Imperative programming (BSc)
    5. Multiparadigm programming (MSc)
    6. Programming (C in English)
    7. Project tools (BSc)
    8. Software technology lab
    9. Theses proposals (BSc and MSc)
  3. Research
    1. CodeChecker
    2. CodeCompass
    3. Templight
    4. Projects
    5. Publications (up to 2011)
    6. PhD students
  4. Affiliations
    1. Dept. of Programming Languages and Compilers
    2. Ericsson Hungary Ltd

16. Templates

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) specialization
x = max( y, z);  // instantiates double max(double,double) specialization

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; // different than c1
C<int, 25-15>   c3; // same type as of c2

Explicit specialization

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 explicitly

User 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
const char *s1 = "Hello";
const char *s2 = "world";

template <>    // user specialization
const char *max<const char *>( const char *s1, const char *s2)
{
  return  strcmp( s1, s2) < 0;
}

std::cout << max( s1, s2) << std::endl;   // uses user specialization

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 a user 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 T>
T max( T a, T b)
{
  if ( a > b )
    return a;
  else
    return b;
}
template <class R, class T, class S>
R max( T a, S b)
{
  if ( a > b )
    return a;
  else
    return b;
}
template <>    // user specialization
const char *max<const char *>( const char *s1, const char *s2)
{
  return  strcmp( s1, s2) < 0;
}

i = max(3,4);                            // line 1
x = max<double>(3.14, 4);                // line 9
const char *m = max( "hello", "world");  // 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 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 template functions. 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
template <typename T>
Matrix<T>::Matrix( const Matrix& rhs) {  ... }
^          ^             ^
|          |             |
class   constr name   inside Matrix namespace this is Matrix<T>

Since class template parameters regularly cannot be deduced from constructor parameters, objects from template classes must be explicitly specialized:

1
2
3
4
5
6
7
8
9
#include "matrix.h"

int main()
{
  matrix<int>  m(10,20);

  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
117
118
119
120
121
122
// vector.h
#ifndef VECTOR_H
#define VECTOR_H

#include <stdexcept>

template <typename T>
class Vector
{
public:
  Vector();     // constructor

  Vector(const Vector& rhs);            // copy constructor
  Vector& operator=(const Vector& rhs); // assignment operator

  ~Vector();    // destructor

  int     size() const;    // actual size 

  T& operator[](int i);        // unchecked access
  T  operator[](int i) const;  // unchecked access, const member

  void    push_back(T d);       // append to 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 is in the same header file
template <typename T>
Vector<T>::Vector()
{
  _capacity = 4;
  _size = 0;
  _ptr = new T[_capacity];
}
template <typename T>
Vector<T>::Vector(const Vector& rhs)
{
  copy(rhs);
}
template <typename T>
Vector<T>& Vector<T>::operator=(const Vector& rhs)
{
  if ( this != &rhs )  // avoid x = x
  {
    release();
    copy(rhs);
  }
  return *this;  // for x = y = z
}
template <typename T>
Vector<T>::~Vector()
{
  release();
}
template <typename T>
void Vector<T>::copy(const Vector& rhs)
{
  _capacity = rhs._capacity;
  _size = rhs._size;
  _ptr = new T[_capacity];

  for (int i = 0; i < _size; ++i)
    _ptr[i] = rhs._ptr[i];
}
template <typename T>
void Vector<T>::release()
{
  delete [] _ptr;
}
template <typename T>
void Vector<T>::grow()
{
  T *_oldptr = _ptr;
  _capacity = 2 * _capacity;
  _ptr = new T[_capacity];

  for ( int i = 0; i < _size; ++i)
    _ptr[i] = _oldptr[i];

  delete [] _oldptr;
}
template <typename T>
int Vector<T>::size() const
{
  return _size;
}
template <typename T>
T& Vector<T>::operator[](int i)
{
  return _ptr[i];
}
template <typename T>
T Vector<T>::operator[](int i) const
{
  return _ptr[i];
}
template <typename T>
void Vector<T>::push_back(T d)
{
  if ( _size == _capacity )
    grow();

  _ptr[_size] = d;
  ++_size;
}
template <typename T>
void Vector<T>::pop_back()
{
  if ( 0 == _size )
    throw std::out_of_range("vector empty");

  --_size;
}
#endif /* VECTOR_H */
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");
}
Financed from the financial support ELTE won from the Higher Education Restructuring Fund of the Hungarian Government.