Template

Templates are useful to avoid multiple implementations of identical objects (e.g., data structure). But the problem is any class using such classes may have to be templated themselves. Too many templates slow down compilation and ‘code bloat’. For example, if the program use 3 instances of queue: queue<float>, queue<int> and queue<Event>, the program will have 3 slightly different versions of the queue<> code. This wasn't a problem with older-style C++ libraries which used polymorphic collections based on virtual functions.


Template vs virtual function:

Of course, virtual functions and templates are not always interchangeable. For polymorphic collection, template is not an option.


A template parameter can be
  1. template type parameter representing a type

    The keyword class or typename indicate that the parameter name that follows represents a potential built-in or user-defined type (typename was added later to allow the parsing of template definitions).

  2. template nontype parameter representing a constant expression

    The parameter name represents a potential value. This value represents a constant in the template definition (possible to evaluate it at compile-time). Value of non-const object is not a constant expression but its address is.

template<class Type, int size>
Type min(Type (&arr)[size]);

template<int size>
class Buf { };
template<int *p>
class BufPtr { };
int size_val = 1024;
const int c_size_val = 1024;
Buf<c_size_val> buf1;
Buf<sizeof(size_val)> buf2;
Buf<size_val> buf3; // error: cannot be evaluated at compile-time
BufPtr<&size_val> bp;

When the template is instantiated, the template parameter will be replaced by the constant value. If an object, function, or type having the same name as the template parameter is declared in global scope, the global scope name is hidden.

Nontype parameter allows lvalue transformation (lvalue-to-rvalue conversion, array-to-pointer conversion, function-to-pointer conversion), qualification conversion, promotion and integral conversion. However, 0 to NULL pointer is not allowed.
void foo(char*);
void bar(void*);
typedef void (*PFV)(void*);
const unsigned int x = 1024;
template <class Type, unsigned int size, PFV handler>
class Array { };
Array<int, 1024U, bar> a1; // ok: no conversion needed
Array<int, 1024U, foo> a2; // error: foo != PFV
Array<int, x, bar> a3; // ok: no conversion needed
Array<int, 1024, bar> a4; // ok: integral conversion
Array<int, 1024, 0> a5; // error: 0 is of type int

Function template is an algorithm that is used to automatically generate particular instances of a function varying by type. The programmer parameterizes all or a subset of the types in the interface (parameter, return types or type of local variables) of a function whose body remains invariant.

Function template will be instantiated for its first use (Recall that two uses of a function are to invoke it or to take its address). Template argument deduction is the automatic process of determining the types and values of the template arguments from the type of the function arguments is called.
int ia[] = { 10, 7, 14, 3, 25 };
double da[8] = { 10.3, 7.2, 14.0, 3.8, 25.7, 6.4, 5.5, 16.8 };
typedef int (&rai)[10];
typedef double (&rad)[20];
void func(int (*)(rai));
void func(double (*)(rad));
template<class Type, int size>
Type min(Type (&arr)[size]);
template<class Type>
Type min2(Type* array, int size);
template<class Type>
Type min3(const Type* array, int size);
template<class Type>
Type min4(Array<Type>& array);
template<class Type>
class Array;
template<class Type>
class ArrayRC : public Array<Type>;
template<class T>
T min5(T, T);
template<class T>
T min6(T, short);

int i = min(ia); // Type=>int, size=>5
int (*pf)(int (&)[10]) = &min;
int i1 = min(da); // ok, return double convert to int
int i2 = min2(ai, 4); // ok: array-to-pointer conversion
int *pi = &ia;
int i3 = min3(pi, 4); // ok: qualification conversion to const int*
ArrayRC<int> ia_rc(ia, 4);
min4(ia_rc); // ok: convert to Array<int>

void f(int pval[9])
{
  int i = min(pval); // error: Type (&)[] != int*
  unsigned int ui;
  min5(ui, 1024); // error: cannot instantiate min5(unsigned int, int)
                  // no automatic promotion or standard conversion
  min6(ui, 1024); // ok: min6(unsigned int, short)
                  // automatic standard conversion int=>short
  func(&min); // error: which instantiation of min()?
  func(static_cast<double(*)(rad)>(&min)); // ok
}
To specify the template arguments explicitly
// T1 not appear in the function template parameter list
template<class T1, class T2, class T3>
T1 sum(T2, T3);

min5<unsigned int>(ui, 1024); // ok: min5(unsigned int, unsigned int)
func(&min<double, 20>); // ok
char ch, ui_type ui;
ui_type loc1 = sum(ch, ui); // error: T1 cannot be deduced
ui_type loc2 = sum<ui_type>(ch, ui); // ok: dedude T2 and T3
// error: only trailing arguments can be omitted
ui_type loc3 = sum<ui_type, , ui_type>(ch, ui);
Use explicit template arguments only when they are absolutely necessary to resolve ambiguities or to use where the template arguments cannot be deduced because
Class template
Template member vs member template:
  1. Template member - Member of a class template.
    template <typename Type>
    class ClassName
    {
      Type* member_;	// template member
      void Func(T&) const;  // template member
    };
    
  2. Member template - Template declared within a class or class template.
    template <class T>
    class Array
    {
      std::vector<T> vec_;
    public:
      // ...
    
      // Asymmetric assignment operator, member template
      template <class T2>
      Array<T>& operator=(const Array<T2>& original);
    };
    
    template <class T>
      template <class T2> // member template
    Array<T>& Array<T>::operator=(const Array<T2>& original)
    {
      if (this == &original) return *this;
    
      vec_.clear();
      for (size_t i=0; i<original.size(); i++)
        vec_.push_back(original[i]); // implicit conversion of T2 to T1
    
      return *this;
    }
    
    // usage in application
    Array<int> ai;
    Array<double> ad;
    ai.AddElement(10);
    ai.AddElement(20);
    ad = ai; // ad contains elements 10.0 and 20.0
    
Member template (nested class or member function) within the class template means that an instantiation of class contains a potentially infinite number of member. It is only instantiated when is used in a program.
Array<int>& Array<int>::operator=(const Array<int>& original);
Array<int>& Array<int>::operator=(const Array<ClassName>& original);
// ...
Any member function, include constructor, can be defined as member template.

Compile time of tempate-intensive library is long because of headers. C++ does not have a very effective module system. As a result, vast amounts of header have to be parsed and analyzed for every compilation unit. Template libraries are especially bad, because of the requirement that the full template implementation be available at compile time. So instead of template declarations, headers provide template definitions.

Another question is, when should templates be instantiated? There are two common approaches:

  1. For each compilation unit, generate all template instances which are used. This leads to duplicate template instances. If files foo1.cpp and foo2.cpp both use list<int>, then there will be two instantiations of list<int>, one in foo1.o and another in foo2.o. Some linkers will automatically throw out the duplicate instances.
  2. Don't do any instantiation. Instead, wait until link time to determine which template instances are required, and go back to generate them. This is called prelinking. Unfortunately, prelinking can require recompiling entire program several times. For very large programs, this can cause long compile times.
Template compilation model specifies the requirements for the way programs that define and use templates must be organized. C++ supports two template compilation models:
  1. inclusion model - include the definition of the template in every file in which a template is instantiated, usually by placing the definition within a header file like inline functions. The header file can then be included in many program files.

    Instantiation of particular instance of template (for example instance of type int) only once. However, when and where the instantiation actually takes place is up to the implementation. Explicit instantiation declaration can control when and where to improve compilation speed.

    The drawbacks are:
  2. separation model - declarations placed in header file and definitions in implementataion file like the non-inline function declarations and definitions.
    // template2.h
    template<typename Type>
    Type min( Type t1, Type t2 );
    // template2.cpp
    export template<typename Type>
    Type min(Type t1, Type t2)
    {
      // ...
    }
    
    // queue.h
    export template <class Type>
    class Queue {
    public:
      Type& remove();
      void add(const Type &);
      // ....
    };
    // queue.cpp
    #include "queue.h"
    template <class Type>
    Type& Queue<Type>::remove()
    {
      // ...
    }
    template <class Type>
    void Queue<Type>::add(const Type &val)
    {
      // ...
    }
    
    // usage in application
    #include "template2.h"
    #include "queue.h"
    int i, j;
    double d = min(i, j); // ok: requires an instantiation
    Queue<int> *p_qi = new Queue<int>; // instantiation of Queue<int>
    p_qi->add(ival); // instantiation of Queue<int>::add(const int&)
    
    The export keyword indicates to the compiler that the template definition might be needed to generate template instantiations used in other files. The compiler must then ensure that the template definition is available when these instantiations are generated. The template must be defined as an exported template only once in a program.

    However, not all compilers support the separation model. Those that support it do not always support it well. To support the separation model, more-sophisticated programming environments are needed and they are not available on all C++ implementations.


Define constraints on template parameters:
template<class T1, class T2>
struct Can_copy {
  static void constraints(T1 a, T2 b) { T2 c = a; b = a; }
  Can_copy() { void(*p)(T1,T2) = constraints; }
};

template<class Container>
void draw_all(Container& c)
{
  typedef typename Container::value_type T;
  Can_copy<T, Shape*>(); // accept containers of only Shape*
  // statements ...
}
Can_copy is an assertion (at compile time) checks that a T1 can be assigned to a T2 (Shape* or a pointer to a class publicly derived from Shape* or a type with a user-defined conversion to Shape*). The definition has the desirable properties that: The idea is very general, more general than language facilities that have been proposed and provided specifically for constraints checking.
template<class T, class B>
struct Derived_from {
  static void constraints(T* p) { B* pb = p; }
  Derived_from() { void(*p)(T*) = constraints; }
};
template<class T1, class T2 = T1>
struct Can_compare {
  static void constraints(T1 a, T2 b) { a==b; a!=b; a<b; }
  Can_compare() { void(*p)(T1,T2) = constraints; }
};
template<class T1, class T2>
struct Can_copy {
  static void constraints(T1 a, T2 b) { T2 c = a; b = a; }
  Can_copy() { void(*p)(T1,T2) = constraints; }
};
template<class T1, class T2, class T3 = T1>
struct Can_multiply {
  static void constraints(T1 a, T2 b, T3 c) { c = a*b; }
  Can_multiply() { void(*p)(T1,T2,T3) = constraints; }
};

struct B { };
struct D : B { };
struct DD : D { };
struct X { };

int main()
{
  Derived_from<D,B>();
  Derived_from<DD,B>();
  Derived_from<X,B>();
  Derived_from<int,B>();
  Derived_from<X,int>();

  Can_compare<int,float>();
  Can_compare<X,B>();
  Can_multiply<int,float>();
  Can_multiply<int,float,double>();
  Can_multiply<B,X>();
	
  Can_copy<D*,B*>();
  Can_copy<D,B*>();
  Can_copy<int,B*>();
  return 0;
}

Suggestions for reducing code bloat:
template<int i>
struct D {
  D(void*);
  operator int();
};

template<int p, int i>
struct IsPrime {
  enum { prim = (p%i) && IsPrime<(i>2 ? p : 0), i-1>::prim };
};

template<int i>
struct PrimePrint {
  PrimePrint<i-1> a;
  enum { prim = IsPrime<i,i-1>::prim };
  void f() { D<i> d = prim; }
};

template<>
struct IsPrime<0, 0> { enum { prim = 1 }; };
template<>
struct IsPrime<0, 1> { enum { prim = 1 }; };
template<>
struct PrimePrint<2> {
  enum { prim = 1 };
  void f() { D<2> d = prim; }
};

void foo()
{
  PrimePrint<10> a;
}
In some sense, this is not a very useful program, since it won't compile. The compiler spits out errors:
prime.cpp 15: Cannot convert 'enum' to 'D<2>' in function PrimePrint
prime.cpp 15: Cannot convert 'enum' to 'D<3>' in function PrimePrint
prime.cpp 15: Cannot convert 'enum' to 'D<5>' in function PrimePrint
prime.cpp 15: Cannot convert 'enum' to 'D<7>' in function PrimePrint
prime.cpp 15: Cannot convert 'enum' to 'D<11>' in function PrimePrint
prime.cpp 15: Cannot convert 'enum' to 'D<13>' in function PrimePrint
prime.cpp 15: Cannot convert 'enum' to 'D<17>' in function PrimePrint
prime.cpp 15: Cannot convert 'enum' to 'D<19>' in function PrimePrint

This program tricks the compiler into printing out a list of prime numbers at compile time. It turns out that C++ templates are an interpreted programming "language" all on their own. There are analogues for the common control flow structures: if/else/else if, for, do..while, switch, and subroutine calls.

template<int N>
struct Factorial {
  enum { value = N * Factorial<N-1>::value };
};
template<>
struct Factorial<1> {
  enum { value = 1 };
};

// example use 
const int fact5 = Factorial<5>::value;

Factorial<5>::value is evaluated to 5! = 120 at compile time. The recursive template acts like a while loop, and the specialization of Factorial<1> stops the loop.

Are there any limits to what computations one can do with templates at compile time? In theory, no. It is possible to implement a Turing machine using template instantiation. The implications are that

In practice, there are very real resource limitations which constrain what one can do with template metaprograms. Most compilers place a limit on recursive instantiation of templates; but there are still useful applications.

Index