Templates allow us to create data structures without defining the type of data that lives in the structure.
For example, we could make a list data structure. It could be a list of integers, a list of floats, a list of MyClass, and so on. C++ allows us to make the list structure without defining the type of data inside it.
Here's a list node containing data whose type is some unspecified class T. This is a ``template''.
template< class T > class Lnode { public: T data; private: Lnode< T > *next; };
In the declaration of ``Lnode'' above, there's a public part that is data of type T and a private part that is a pointer to an Lnode of type T.
In declaring a variable from a template class, we must specify the type of data, T, in the template class. To create a list node ``n'' containing an integer, we use
Lnode< int > n;
To create one containing an instance of MyClass, we use
Lnode< MyClass > n;
A pointer to a list node of type T would be declared as
Lnode< T > *p;
template< class T > class List { public: int empty(); void add( T data ); T remove(); List() { sentinel = new Lnode< T >(); sentinel->next = sentinel; } private: Lnode< T >* sentinel; };
This class supports three functions: empty() returns 0 or 1; add(data) adds data of type T to the list; remove() removes data from the list and returns it (the return type is T). The constructor List() creates a sentinel node and points it to itself.
Some things to note:
Recall that functions defined inside the class declaration are compiled ``in-line'', which is to say their code is put in place of a function call. This takes more space, but saves the time of the function call. For this reason, we typically put large functions outside the class defintion.
Here's how we might define the add() function outside the template class declaration. This just creates a new Lnode and adds it to the head of the list.
template< class T > void List< T >::add( T data ) { Lnode< T > *p; p = new Lnode< T >(); p->data = data; p->next = sentinel->next; sentinel->next = p; }
Template code can get a bit messy, as you can see above. However, the only differences between it and normal code are that
Here's how we might define the remove() function.
template< class T > T List< T >::remove() { T data; Lnode< T > *node; if (sentinel->next == sentinel) { cerr << "ERROR: `remove' called with empty list.\n"; exit(1); } node = sentinel->next; data = node->data; sentinel->next = node->next; delete node; return data; }
#include "list.h" main() { List< int > list1; List< float > list2; list1.add( 5 ); list2.add( 2.7 ); cout << list1.remove(); ... etc ... }
Typically, you put all your template code in a single *.h file and include it as shown above. This file should contain the class declaration and the function definitions that appear outside the class declaration.
Why all in one file? In the example above, C++ had to create code for the add(), remove(), and empty() functions for both ints and floats. To create the code, C++ needed to know the function definitions. Since C++ typically creates functions for a template class when it sees a declaration of an instance of that class, it must know the function definitions at that time. Thus, they must appear in the *.h file.
If you declare an instance of List< int > in several different *.C files, C++ will create code for add(), remove(), and empty() in each of those *.C files. It doesn't know any better, since the C++ files are compiled separately. This is wasteful.
The GNU version of C++ provides a mechanism to avoid this. Here's an except from the man page for gcc, describing one of the switches that can be included on the command line of g++:
This means that if you compile with-fexternal-templates Produce smaller code for template declarations, by generating only a single copy of each template function where it is defined (C++ only). To use this option successfully, you must also mark all files that use templates with either `#pragma implementation' (the definition) or `#pragma interface' (declarations). When your code is compiled with `-fexternal-templates', all template instan- tiations are external. You must arrange for all necessary instantiations to appear in the implementation file; you can do this with a typedef that ref- erences each instantiation needed. Conversely, when you compile using the default option `-fno-external-templates', all template instantiations are explicitly internal.
and include the lineg++ -fexternal-templates ...
in your *.h file, C++ will not create code when it encounters an instance of a template class.#pragma interface
However, the code must be created somewhere. This means that you need another *.C file (typically with the same base name as your *.h file) that causes the code to be created. Such a *.C file must contain
and must include a typedef for each type of template you need. For example, assuming the list.h file has #pragma interface in it, we cause code to be created for two types of list by compiling the following list.C file:#pragma implementation
The object file, list.o, will contain code for the functions add(), remove(), and empty() for both types of List. In the elevator assignment, you were given a complete definition of a List template class in list.h and list.C.#pragma implementation #include "list.h" typedef List< int > dummy1; typedef List< float > dummy2;