Date: Tue, 9 Oct 2001 11:18:16 -0700 (PDT)
From: Hannah C. Tang <hctang@cs.washington.edu>
To: cse326 <cse326@cs.washington.edu>
Subject: C++ Templates


While you're all waiting for the programming assignment to be published, I
thought I'd send out some information about C++ templates, which, while
incredibly powerful, are fairly awkward in C++.  So, take a deep breath,
and plow on ....



Templates: An introduction

Some functions have the same semantic meaning for some (if not all) data 
types.  For instance, a swap() function should do the same thing for all 
data types that can be passed in.  In an ideal world, it would not be 
necessary to rewrite this function for each possible type.  In C++, this 
is handled by templates.

C++ templates allow you to define a generalized function or class --
delaying the specification of one (or more) types -- until compile-time.


Declaring a template

Declaring a function or a class to be templated requires the "template"  
& "typename" keywords, and one (or more) "placeholder variables".  These
placeholder variables represent the type which the function/class will be
instantiated on.  Note that your generalized templated function/class
doesn't really represent a function/class; a "real" function/class
knows, for example, the type of its parameters.  To state this point
again: generalized templated functions/classes are not compilable.  More 
on this later.


A basic example

A swap function for ints might look like this:
  void
  swap( int& a, int& b )
  {
       int temp = a;
       a = b;
       b = temp;
  }
  

A templated swap function would thus look like:
  template< typename TemplateType >
  void
  swap( TemplateType& a, TemplateType& b )
  {
       TemplateType temp = a;
       a = b;
       b = temp;
  }


Template syntax

From the above example, you should be able to deduce that the syntax for
declaring a templated function/class is:
  template< typename T >
  // Function definition or class specification as usual

To use a templated function/class, the syntax is simple: specify in
angle brackets the type which you would like the general function/class to
be templatized on:
  int i, j;
  swap< int >( i, j );
or:
  vector< char > charVector;

The trickiest is the syntax for defining a templated class member.  
Assume you have the following templated class:
  template< typename T >
  class Example
  {
  public:
     void      SetValue( const T& newValue );
  private:
     T         m_value;
  };

In the non-templated world, the definition of SetValue would look 
something like:
  void
  Example::SetValue( const SomeDataType& newValue )
  {
      m_value = newValue;
  }

(Note that the "Example::" prior to "SetValue" indicates that SetValue()  
is a member of the Example class.)  In the templated world, it is
necessary to specify that you are defining a templated function. This
requires the "template < typename T >"  which we saw above.  

However, is SetValue() a member of the generalized templated class?  
The answer is no: it is a member of a specific Example class.  If we had
an Example class which was templatized on doubles, and another Example
class which was templatized on chars, the compiler would generate two
copies of SetValue() -- one which was templatized on doubles, and another
version which was templatized for chars.  So it is necessary to specify
that SetValue() is a member of a specific class -- it is a member of the
Example class which is templatized on the placeholder variable.  This
class is called Example< T > (similar to vector< char > above).  Thus, the
definition of SetValue would look like: 
  template< typename T >
  void
  Example< T >::SetValue( const T& newValue )
  {
      m_value = newValue;
  }


Template gotchas

As if the syntax wasn't bad enough, things get worse.  Remember that no
object code is produced for generalized templated functions/classes.  
It is only when they are specialized (as in the above two examples when
we created an int swap() and a char vector) that object code is generated.
Since object code is generated by the compiler, if no object code is
generated, this means that templated functions/classes which are not
specialized anywhere are never compiled.  This means that a function like:
  template< typename T >
  void
  HelloWorld( T t )
  {
     Foo f = t;          // Note: no "Foo" type defined!
     Bar b = aVariable;  // No aVariable located in this scope!
     double d = "Hello World!"; // This shouldn't compile at all
  }

could get past the compiler if it was never instantiated.  Even worse:  
since no object code is generated by the compiler, when the linker 
attempts to link your (non-existant) object files together, it will 
fail, probably complaining about "unresolved external symbols" or 
"undefined references".  The process of generating real object code 
out of specialized templates, called "instantiation", never happened.


Working around template problems

The problems described above can be worked around by one simple solution: 
forcing the instantiation of templated functions/classes.  The syntax
for doing this is:
  template ClassName< Type >
  template FuncName< Type >( /* Function  arguments */ );

The following lines forces the compiler to instantiate two Example
templates: one templatized on ints, and the other on strings.  It also
instantiates two swap() functions on doubles and char:
  template Example< int >;
  template Example< string >;
  template swap< double >( double a, double b );
  template swap< char >( char a, char b );

Thought this was too easy?  It is.  The compiler can only instantiate 
templates when the template definitions are available to it in 
the same file.  If you are writing good C++ code, your templated class 
definitions (found in your .cpp or .cc files) are in one file, whereas the 
instantiations will be in another (in the .cpp or .cc files which 
#include your .h's).

There are two solutions:
  (1) Write all of your code in your .h file:

  template< typename T >
  class Example
  {
  public:
     void      SetValue( const T& newValue )
     {
          m_value = newValue;
     }

  private:
     T         m_value;
  };


 (2) Put all of your instantiations and definitions together in a seperate
file.  This second solution is the cleaner one.  Here is an example:

	In Example.h:
  template< typename T >
  class Example
  {
  public:
     void      SetValue( const T& newValue );

  private:
     T         m_value;
  };

	In Example.cc
  template< typename T >
  void
  Example< T >::SetValue( const T& newValue )
  {
      m_value = newValue;
  }

	In ExampleInstantiations.cc
#include "Example.cc"   // Note that this is the .cc file!
template Example< int >
template Example< string >

To compile and build this, then, you will need to compile the 
class instantiation file, not the class implementation file.  Your compile 
line would thus look like:
  g++ -Wall -ansi -g ExampleInstantiations.cc main.cc
and definitely NOT like:
  g++ -Wall -ansi -g Example.cc main.cc


To recap

- Template declarations look like:
   template< typename T >
   // Function/Class declaration as normal
- Template use looks like:
   FunctionName< Type >( /* Function arguments */  );
   ClassName< Type >;
- Template instantiation looks like:
   template FunctionName< Type > ( /* Function arguments */ );
   template ClassName< Type >


Hannah

PS -- All of this information is available (in a more graphical format) at 
the ACM tutorials page:
  http://www.cs.washington.edu/orgs/acm/tutorials/
That webpage is, incidentally, where I learned all my template stuff.  =)

PPS -- For a more detailed templates (and Makefile!) example, look in 
  the course web under "Computing Info"

PPPS -- Congratulations on finishing this email!