CSC270 November 25 tutorial - C++ Templates

Templates allow us to create data structures without defining the type of data that lives in the structure.

List Node Template

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;

Linked List Template

It's no use having a list node without a linked list. Here's a linked list template:
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:

Function Definitions for Template Classes

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;
}

Using Template Classes in Your Code

Template classes are used much like normal classes. The only difference is that declaration of a class instance must include the template type, T. This is great from the point of view of someone using the template, since they can easily use the template on various data types.
#include "list.h"

main()
{
  List< int > list1;
  List< float > list2;

  list1.add( 5 );
  list2.add( 2.7 );

  cout << list1.remove();

  ... etc ...
}

What File Contains the Template?

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.

A More Efficient Alternative

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++:

-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.
This means that if you compile with
g++ -fexternal-templates ...
and include the line
#pragma interface
in your *.h file, C++ will not create code when it encounters an instance of a template class.

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

#pragma implementation
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
#include "list.h"

typedef List< int > dummy1;
typedef List< float > dummy2;
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.