The essentials of C++, Chapter 10 Templates
The Essentials of C++, David hunter
Chapter 10. Templates
10.1 Class Templates
-
Templates allow for the creation of generic program constructs. As the name suggests, templates do no define executable code, but define a form from which code can be generated. Templates must be “instantiated” to create usable program usits (classes, functions, and so forth).
-
A template has the form template
construct. For example, the following defines a template for a vector class.
template<class t>
class vector {
public:
vector() {contents = NULL;}
vector(int in_size) : size(in_size) { contents = new t[size];}
vector(int in_size, t initial_value)
~vector() { delete[] contents; }
// return reference to specified element
t& operator[](int index);
protected:
int size;
t *contents;
};
// Note that each method implementation must be preceeded by its own template statement
template <class t>
vector<t>::vector(int in_size, t initial_value) : size(in_size)
{
contents = new t[size];
for (int i = 0; i <= size-1; ++i)
contents[i] = initial_value;
};
template<class t>
t& vector<t>::operator[](int index)
{
assert((index >= 0) && (index <= size));
return contents[index];
}
-
In this example, t is a template parameter that represents the data type that is to be stored in the vector. The term “class” is somewhat misleading here. In this context, “class” means “any C++ data type”.
-
The template is used to generate particular vector classes by specifying vector
in a declaration where type is a type identifier specifying the type of value to be sotred in the vector. This notation causes the template to be instantiated for that particular type, in effect causing the compiler to generate a class definition by replacing the template parameter with the specified type identifier. The method is illustrated in the example shown.
void main()
{
// a is a vector of integers
vector<int> a(100);
// b is a vector of floats
vector<float> b(50);
// ...
}
- Since it is tedious to write vector
whenever a vector is declared, it is common practice to use a typedef statement to associate type identifiers with template instantiations, as shown below.
typedef vector<int> int_vector;
typedef vector<float> float_vector;
// ...
int main()
{
int_vector a(100);
float_vector b(50);
// ...
return 0;
}
-
Since templates are definitions only and do not themselves cause object code to be generated, they should be placed in “.h” files when used as part of a larger program. That is, in the case of the vector template both the class specification and the method implementations should be placed in the “.h” file.
-
A template identifier (“vector” for example) can never be written without the required template parameters. This is because there is no class called “vector.” Rather, “vector” is an outline from which a class can be generated. Therefore, in writing the implementation of the vector methods, it is necessary to write vector
::operator[](int index) and precede this by a statement specifying the template parameters. -
Templates are very convenient, but programmers must be careful when using them. They may not be as “generic” as they seem. For example, the vector template will instantiate correctly only for data types for which the assignment operator is defined. This is because the assignment operator is used with a t type variable in the implementation of the “initial value” constructor method.
-
Since the assignment operator will not work with arrays, the following sequence would not compile:
typedef float matrix[100][100];
typedef vector<matrix, 50> // ERROR!
- Should one wish to do this, the assignment operator must first be overloaded to work with matrix types.
10.2 Function Templates
- Templates can also be used to write “generic” functions. For example, one could define a generic sort function template:
template <class t>
void sort(t *a, int size)
{
// ...
// insert your favoriate sorting
// algorithm here
// ...
}
- The C++ compiler is intelligent enough to automatically instantiate a function template when it encounters a template function call. Thus, given the template above the following code sequence would be permissible:
int a[100];
float x[50];
// ...
// put some values in the arrays
// ...
sort(a, 100);
sort(x, 50);
-
The compiler realizes that the call sort(a, 100) requires an instantiation of sort
and does so automatically. Similarly, the call sort(x, 50) causes an instantiation of the sort template with parameter float. -
Function templates can have the same sort of hidden dependencies that class templates can have. For example, just as the vector template works only for classes for which assignment is defined, the sort template would presumably only work for data types for which the relvant comparison operator is defined (“<” or “>” depending upon how the osrt is implemented).
10.3 Templates for Derived Classes
- In order to illustrate the use of templates with derived classes, a subclass of vectors is defined below which allows for the programmer to specify upper and lower bounds for the vector’s indices.
template <class t>
class indexed_vector : public vector<t> {
public:
indexed_vector() : lower(0), upper(0) {}
indexed_vector(int first, int last) : vector<t> (last - first + 1), lower(first), upper(last) {}
indexed_vector(int first, int last, t initial_value) : vector<t> (last - first + 1, initial_value), lower(first), upper(last) {}
t& operator[](int index);
protected:
int lower, upper;
};
template<class t>
t& indexed_vector<t>::operator[](int index)
{
return vector<t>::operator[](index-lower);
}
10.4 Templates for Recursive Classes
- The code below illustrates the use of templates in creating recursive structures, in this case the List class seen earier. Readers should again note that wherever a class name is required a template parameter must be provided. A typedef is used in List to avoid the necessity of writing ListCell
whenever a reference to that class is needed.
template<class t>
class ListCell;
template<class t>
class ListCell {
friend List<t>;
public:
ListCell(t c, ListCell<t> *p = NULL) : contents(c), Next(p) {}
ListCell() : contents('\0'), Next(NULL) {}
ListCell(const ListCell<t>& lc) : contents(lc.contents), Next = lc.Next {}
ListCell<t>& operator= (const ListCell<t>& lc) {
contents = lc.contents;
Next = lc.Next;
return *this;
};
t GetContents(){ return contents; }
ListCell<t>* GetNext(){ return Next; }
~ListCell() {}
protected:
t contents;
ListCell<t> Next;
};
template<class t>
class List {
typedef ListCell<t> tCell;
friend ListIter<t>;
public:
List() {First = NULL;}
List(const List<t>&);
List(t>& operator= (List<t>& 1);
void add(t c) { First = new tCell(c, First); };
void remove(t);
int IsIn(t);
~List();
protected:
tCell* First;
};
template<class t>
List<t>::List(const List<t>& l)
{
if (l.First == NULL)
First = NULL;
else
{
First = new tCell(l.First->contents, NULL);
tCell *p1 = l.First->Next;
tCell *p2 = First;
while (p1 != NULL)
{
cout << p1->contents;
p2->Next = new tCell(p1->contents, NULL);
p2 = p2->Next;
P1 = p1->Next;
}
}
}
// and so on for other List<t> methods
template<class t>
class ListIter {
public:
ListIter() { ptr = NULL; }
ListIter(List<t>& l) { ptr = l.First; }
void reset (List<t>& l) { ptr = l.First; }
t operator()()
void operator++()
void operator=(t x) { ptr->contents = x; }
int operator!() { return ptr != NULL; }
protected:
ListCell<t>* ptr;
};
template<class t>
char ListIter<t>::operator()()
{
if (ptr != NULL)
return ptr->GetContents();
else
return NULL;
};
template<class t>
void ListIter<t>::operator++()
{
if (ptr != NULL) ptr = ptr->GetNext();
};
int main()
{
List<char> l;
l.add('a');
l.add('b');
l.add('c');
for (ListIter<char> i(l); !i; ++i)
cout << 'x' << i.get();
return 0;
}