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:

• Template may give you faster code. But they almost always give you more code. (They don't give you more code if you only use one instance of the template).
• Virtual functions give you less code, but slower code. The slow-down is negligible if the body of the function is big, or the function isn't called often.

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.

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.

• The type of a function argument need not exactly match the type of the corresponding function parameter. Lvalue transformation (lvalue-to-rvalue conversion, array-to-pointer conversion, function-to-pointer conversion), qualification conversion and conversion to a base class instantiated from a class template are allowed.
• When the address of a function template instantiation is taken, the context must be such that it allows a unique type or value to be determined for a template argument, else compile-time error is generated.

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
}

// 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);

• easier to let the compiler determine
• if modify the declarations so that the types of the function arguments in a call to a function template instantiation change, compiler will automatically instantiate a function template with a different set of template arguments.

• The name of a template parameter cannot be used as the name for a class member/ typedef declared within the class template definition.
• Can have default arguments like function default arguments (rightmost first).
• The shorthand notation (without template header before class template name) can only be used within the definition of the class template itself and definitions of its member functions. If it is used as a type specifier in another class template definition, the template header still need to be specified.
• Unlike template arguments for function template instantiations, the template arguments for class template instantiations are never deduced from the context in which a class template instantiation is used. They need to specified explicitly.
• Class template is instantiated only when the name of an instantiation is used in a context that requires definition to exist - when an object of the class template is defined (require to know its size). Declaring pointer or reference to the class won't instantiate the template, but dereference the pointer (e.g. to call the member function) will.
• Member function, static data members and nested types of class template is not instantiated automatically when the class template is instantiated. It is instantiated only if it is used by the program (for function, recall, invokes the function or takes its address).
• Three kinds of friend declarations (function or class) of class template are non-template friend (one friend to all instantiations of the class template), bound friend (one-to-one mapping) and unbound friend (one-to-many mapping. For each type class template instantiation, all instantiations of friend declarations are friends). Friend operator overloading function generally is the first kind.

  template <class Type>
  class ClassName {
  public:
    // ...
    friend ostream& operator<<(ostream& outStream, const ClassName<Type>& c);
  };
  template <class Type>
  ostream& operator<<(ostream& outStream, const ClassName<Type>& c)
  {
    // ...
  }
  

• Each instantiation of the class template has its own set of static data members.
• Nested class of class template is automatically a class template (one-to-one mapping) but is not instantiated automatically when the enclosing class template is instantiated.
• Public nested type (or an enumerator of a nested enumeration) can be used outside its class definition. Although enumerator has the same value in each instantiation, code that refers to it must specify to which particular instance of template it belongs.

  Buffer::Buf_vals bfv1; // error: which instantiation of Buffer?
  Buffer::Buf_vals bfv2; // ok
  

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
   

Array<int>& Array<int>::operator=(const Array<int>& original);
Array<int>& Array<int>::operator=(const Array<ClassName>& original);
// ...

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.

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:
   • Definition of a template describes implementation details that should be hide from user.
   • Compiling the same template definitions across multiple files add unnecessarily compile time.
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.

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

• Express constraints without declaring or copying variables, thus the writer of a constraint doesn't have to make assumptions about how a type is initialized, whether objects can be copied, destroyed, etc. (unless, of course, those are the properties being tested by the constraint)
• No code is generated for a constraint using current compilers.
• Current compilers give acceptable error messages for a failed constraint, including the word "constraints" (to give the reader a clue), the name of the constraints and the specific error that caused the failure (e.g. "cannot initialize Shape* by double*")

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

• Every extra template parameter is another opportunity for code bloat. If you use many different instantiations of a "kitchen-sink" template class, you should consider eliminating some of the template parameters in favour of virtual functions, member templates, etc.

  list<double, Allocator<double> > A;
  list<double, MyAllocator<double> > B;
  

  Separate versions of the list code will be generated for both A and B, even though most of them will be identical. The same flexibility could be accomplished with:

  list<double> A(Allocator<double>());
  list<double> B(MyAllocator<double>());
  

  where Allocator and MyAllocator are polymorphic.
• Put function bodies outside template classes.

  template<class TNumtype>
  class Array3D {
  public:
    // Make sure this array is the same size as some other array
    template<class TNumtype2> bool ShapeCheck(Array3D<TNumtype2>& B);
  private: 
    int base[3];	// starting index values
    int extent[3];// length in each dimension
  };
  
  template<class TNumtype> template<class TNumtype2>
  bool Array3D<TNumtype>::ShapeCheck(Array3D<TNumtype2>& B)
  {
    for (int i=0; i<3; i++)
      if ((base[i] != B.base(i)) || (extent[i] != B.extent(i)))
        return false;
    return true;
  }
  

  Clearly all of these instances are identical, because ShapeCheck() doesn't use the template parameters TNumtype and TNumtype2. To avoid having duplicate instances, move ShapeCheck() into a base class which doesn't have a template parameter, or into a global function.

  class Array3DBase {
  public:
    bool ShapeCheck(Array3DBase& B);
  private: 
    int base[3];	// starting index values
    int extent[3];// length in each dimension
  };
  
  template<class TNumtype>
  class Array3D : public Array3DBase
  {
    // ...
  };
  

  Since ShapeCheck() is now in a non­templated class, there will only be one instance of it. For C++ compiler writer, note, this problem could be solved automatically by doing a liveness analysis on template parameters.

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

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

• any arbitrary computation can be carried out by a C++ compiler
• whether a C++ compiler will ever halt when processing a given program is undecidable