Templates

Templates are a C++ feature that allow you to write families of functions or types. One common example in game programming is the 3D vector class. For example, in one game, it might store vector information as floats most of the time since they take up less memory. However, in one part of the physics engine, it needs additional accuracy for the computations so it does everything with doubles. Without templates you might end up developing two vector classes and a lot of functions that were the same except for the type used.

struct Vector3Float {
  float x;
  float y;
  float z;
};
 
struct Vector3Double {
  double x;
  double y;
  double z;
};
 
float dot_product(const Vector3Float & lhs, const Vector3Float & rhs) {
  return lhs.x * rhs.x + lhs.y * rhs.y + lhs.z * rhs.z;
}
 
double dot_product(const Vector3Double & lhs, const Vector3Double & rhs) {  
  // exactly the same as the above except for the types it takes
  return lhs.x * rhs.x + lhs.y * rhs.y + lhs.z * rhs.z;
}

So instead of duplicating all that code for the different types, you can write class and function templates.

template <typename T>
struct Vector3 {
  T x;
  T y;
  T z;
};
 
template <typename T> 
T dot_product(const Vector3<T> & lhs, const Vector3<T> & rhs) {
  return lhs.x * rhs.x + lhs.y * rhs.y + lhs.z * rhs.z;
}

The first definition defines a class template Vector3<>. Vector3<> can be instantiated with different types. For example, you can have a Vector3 of floats or a Vector3 of doubles. When you refer to a specific template instantiation, you put the template arguments in angle brackets after the template class' name. For example Vector3<float> or Vector3<double>. You can even have a Vector3<bool>, though that rarely makes sense, or a Vector3<long double>. The second definition defines a function template dot_product<>(). This function takes Vector3<> arguments that depend on what template argument the dot_product<>() function is instantiated with.

Vector3<float> a;
Vector3<float> b;
float dot = dot_product<float>(a, b);

One convenient thing about function templates is that if the compiler can figure out what the template arguments should be from the function arguments, then you don't need to explicitly specify the template argument for the function.

Vector3<float> a;
Vector3<float> b;
float dot = dot_product(a, b); // compiler can figure out this should be dot_product<float>()
                               //   by itself

However, there are cases where the compiler can't figure out what the template arguments should be.

template <typename T>
T multiply(T a, T b) {
  return a * b;
}
 
multiply(5, 5);           // good; compiler knows that it should be multiply<int>()
multiply(5, 4.0);         // confusion; compiler can't decide between multiply<int>()
                          //   and multiply<double>()
multiply<double>(5, 4.0); // good; explicit template argument

When you declare a template type parameter you can use both the typename keyword and the class keyword. [6]

template <typename T>
struct Vector3 {
  T x;
  T y;
  T z;
};
 
// means exactly the same thing
template <class T>
struct Vector3 {
  T x;
  T y;
  T z;
};

Template arguments don't need to be primitives like float or double, they can also be class types, or even template instantiations.

class Rational {
  // implements rational numbers
};
Rational operator*(const Rational & lhs, const Rational & rhs) {
  // stuff
}
Rational operator+(const Rational & lhs, const Rational & rhs) {
  // stuff
}
 
Vector3<Rational> a;                 // a vector of rational numbers
Rational dot_a = dot_product(a, a);  // happily calculates the dot product in terms of Rationals
 
Vector3<Vector3<float> > b;               // I don't know what this would mean, but you can do it
Vector3<float> dot_b = dot_product(b, b); // but this will blow up since Vector3<float> doesn't 
                                          //   define either binary operator * or operator+
                                          //   which are both used to calculate the dot product

One note about syntax: when instantiating a template with a template instantiation, you should put a space between the angle brackets at the end of the declaration. In the above example, you need a space between the > for the Vector3<float> and the closing > for the Vector3<Vector3<float> >. If you leave the space in, the compiler will interpret the brackets as operator >> instead, which will make the declaration illegal. [7]

A class template can have virtual functions and you can define member function templates for both class templates and normal classes. However, you cannot have a templated virtual function.

struct BaseClass {
  virtual void update(void);
};
 
template <typename T>
struct TemplateClass : BaseClass {
  virtual void update(void); // OK
};
 
struct NonTemplateClass {
  template <typename T>
  void twiddle(T t); // OK
 
  template <typename T>
  virtual void twaddle(T t); // Error
};

Also, the compiler often can only do limited checking on the body of a class or function template until it is instantiated. With some compilers, the best they can do is detect unbalanced parenthesis or brackets inside function definitions. For example, MSVC 7.1 will let this code compile unless you try to instantiate it:

template <typename T>
T function(const T & a, const T & b) {
  return a -- b; 
}

Dependent Names

Inside the definition of a template class or function, there are some identifiers that are called dependent names. Basically anything that depends on the template parameters is a dependent name. So if the template parameter list looks like template <typename T, typename U> then T and U are dependent names.

template <typename T>
void some_function(const T & t) {
  T temp = 0;            // T is a dependent name, but so is temp
  Vector3<T> vec;        // Both Vector3<T> and vec are dependent names
  temp += vec.x * vec.x; // vec.x is a dependent name since it depends on vec 
  Vector3<float> fred;   // no dependent names here
  foo();                 // nor here
}

Names that refer to types are called dependent types. In the above example, T and Vector3<T> are dependent types. Other dependent names are called type dependent expressions. temp, vecand vec.x are all type dependent expressions. In most cases, it's easy for the compiler to determine if something should be a dependent type or a type dependent expression. However, there is one place where there is an ambiguity: if the :: operator is used on a dependent type. In this case it could be either a nested type or typedef or it could be a static member variable. In this case, the compiler will assume that the name refers to a static member variable unless you tell it that it should be a type name. This is done with the typename keyword. In this case, you cannot substitute the class keyword.

template <typename T>
void function1(T t) {
  typename T::some_type variable; // T::some_type interpreted as a nested type
  variable = T::some_value;       // no typename keyword, T::some_value is interpreted as
                                  //   a static member variable
}
 
template <typename T>
struct Vector3 {
  // stuff
  typedef T member_type;
};
 
void function2(void) {
  Vector3<float>::member_type some_variable; // no typename needed, not a template function
}
 
template <typename T> 
void function3(void) {
  Vector3<float>::member_type some_variable;             // no typename needed, Vector3<float>
                                                         //   doesn't depend on T
  Vector3<T>::member_type some_other_variable;           // error: need typename because
                                                         //   Vector3<T> depends on T
  typename Vector3<T>::member_type yet_another_variable; // good; typename keyword used
}
 
template <class T>
class AnotherTemplateClass {
  Vector3<double>::member_type     some_variable;    // good, Vector3<double> doesn't depend on T
  typename Vector3<T>::member_type another_variable; // also good, typename used and Vector3<T>
                                                     //   depends on T
};

The difference between dependent names and non-dependent names shows up in another different way: non-dependent names are looked up when the template is defined, and dependent names are looked up when the template is instantiated.

void foo(int bar);
 
template <typename T>
void function(T t) {
  foo(t); // not a dependent name so it always refers to the
          //   foo(int) above (assuming that no other foo()s
          //   have been defined previously)
}
 
void foo(double bar);
 
void other_function(void) {
  foo(1);        // calls foo(int)
  foo(1.0);      // calls foo(double)
  function(1);   // calls foo(int)
  function(1.0); // also calls foo(int)
}

This rule was introduced so that code between the point of the template definition and the point of instantiation won't accidentally change the meaning of a template. However, it has one nasty side effect: member function calls to base classes may not be looked up properly.

template <typename T>
struct A {
  void foo(void);
};
 
template <typename T>
struct B : A<T> {
  void bar(void) {
    foo(); // may cause a compiler error
  }
};

Inside B<T>::bar() foo() appears to be a non-dependent name, so it's looked up as a global function. If no global function is found, then the compiler may generate an error. [8] In order to get the compiler to search for the name at the point of instantiation, when the base class will be resolved, you need to get foo() to look like a dependent name. The easiest method is to replace the call to foo() with this->foo(). Since the class is a instance of a class template, this is a dependent name, and thus so is this->foo().

Compilation

One other tricky detail about templates is that class templates and function templates are not actual classes or functions. Only specific instances are classes and functions. This means, for example, you can't create a pointer to a function template. And because they aren't actual classes or functions, the compiler doesn't generate code for the class or function template, it only generates code for the specific instantiations. This means that even though you can separate templates function declarations from their definitions, you usually can't put the definitions in a separate source file.

// header file
template <typename T>
struct SomeClass {
  void some_member_function(void);
};
//---------------------------------
 
// some_file.cpp
SomeClass<int> s;
s.some_member_function();
//---------------------------------
 
// some_other_file.cpp
template <typename T>
void SomeClass<T>::some_member_function(void) {
  // do something
}

This will most likely cause unresolved symbol linker errors. Basically the problem is that in some_file.cpp the compiler says it needs the definition for SomeClass<int>::some_member_function(). However, in some_other_file.cpp when the function is defined, the compiler doesn't know it needs to create a instantiation of that function for int. There are three ways to deal with the problem. The first way is to put the definition of the function in the header with the template declaration, or in some other inline file that the header includes.

// header file
template <typename T>
struct SomeClass {
  void some_member_function(void);
};
 
#include "some_class.inl"
//---------------------------------
 
// some_file.cpp
SomeClass<int> s;
s.some_member_function();
//---------------------------------
 
// some_class.inl
template <typename T>
void SomeClass<T>::some_member_function(void) {
  // do something
}

This allows the compiler to generate code for the function calls in much the same way that inline functions work. [9]

The second way is called explicit template instantiation. With this method, you keep the template function definitions in a separate source file, but then you tell the compiler which template instantiations you need.

// header file
template <typename T>
struct SomeClass {
  void some_member_function(void);
};
template <typename T>
T another_function(T t);
//---------------------------------
 
// some_file.cpp
SomeClass<int> s;
s.some_member_function();
another_function(1.0f);
//---------------------------------
 
// some_other_file.cpp
template <typename T>
void SomeClass<T>::some_member_function(void) {
  // do something
}
template <typename T>
T another_function(T t) {
  return t + t;
}
template SomeClass<int>; // explicit template instantiation for a class
template float another_function<float>(float); // for a function

Of course this means that every time a different template instantiation is require you'll need to modify the source file with the definitions in it.

The third way is to use the export keyword. Unfortunately, the export keyword is implemented in very few compilers, so chances are you won't have the opportunity to use it. [10]

Templates and the Standard Library

Templates are important to the standard library since the vast majority of the C++ standard library consists of class and function templates. For a simple example, take std::swap<>(). std::swap<>() is a function template who's job is to swap the value of two objects. One implementation of std::swap<>() looks like:

template <typename T>
void swap(T & a, T & b) {
  T temp = a;
  a = b;
  b = temp;
}

Also, some parts of the standard library that look like non-templated classes are actually typedefs for specific instantiations of class templates. For example, std::string is actually a typedef for std::basic_string<char>.

One interesting side effect of this is that it means that most of the source code of the standard library is available to you in the headers. Usually it's hard to read, but most of it is there for you to see how things are implemented.

Exceptions