Chapter 6. Template Metaprogramming

Table of Contents

Template basics
Tempalte basics
Possible solutions
Instantiation
Instantiation, template argument deduction
Explicit specialization
Template overloading
Template classes
Parametric polymorphism
Template class specialization
Partial specialization
Default Parameter
Generics in other languages
ADA generic
Functional languages
Generic in Java
Tricky basics
Dependent name
Using this
Member templates
Template template parameters
Explicit call of default constructor
Explicite Template Instantiation
C++ Template Metaprogramming
Metaprogramming
Partial evaluation
Static metaprogramming
Turing-completeness of C++ templates
Factorial function
Meta Control Structures
Template Recursion
Metafunctions as Parameter
Problems with lazy instantiation
Motivation
Expression Templates
Uneffective object-oriented code
Recursive Templates
Minimal Implementation
Expression Templates in Java
Bubble Sort
Mixins
What is a Mixin?
Mixin issues
Liskov substitutional principle
Traits
An example for traits
Policy classes
More traits
Character Trait
Case Insensitive String with Traits
Problem with traits
Loki
Int2Type
Type2Type
Type Select
Typelist
Loki Utilities
Typelist Manipulation
Usage Example for Loki
Static interface checking
Interface Checking
Promotion
Conversion Checking
Inheritance
Compile-Time Assertion
 

I always knew C++ templates were the work of the Devil, and now I'm sure...

 
--Cliff Click cited by Todd Veldhuisen 

Template basics

 

Your quote here.

 
--B. Stroustrup 

Tempalte basics

Independent concepts should be independently represented and should be combined only when needed.

Otherwise unrelated concepts are bundled together or unnecessarry dependencies are created.

Templates provide a simple way to represent a wide range of general concepts and simple ways to combine them.

A standard library requires a greater degree of generality, flexibility and efficiency.


int max( int a, int b)
{
if ( a > b )
return a;
else
return b;
}

double max( double a, double b)
{
if ( a > b )
        return a;
    else
        return b;
}

Possible solutions

Prepocessor macro:

Ada designers described generic program units as: "a restricted form of context-sensitive macro facility"

Designers of C++: "a clever kind of macro that obeys the scope, naming, and type rules of C++"


#define MAX(a,b)    a > b ? a : b

Works, because C/C++ macro is - typeless.

But a macro is processed not by the C++ compiler, therefore there are a number of "secondary effect":


MAX( x, y)*2  -->   x > y ? x : y*2

#define MAX(a,b)    ((a) > (b) ? (a) : (b))

MAX( ++x, y) -->    ++x > y ? ++x : y

void swap( int& x, int& y)
{
    int temp = x;   // !! how to detect type of x?
    x = y;
    y = temp;
}

Does not works with macro, because a macro is - typeless.

We need a facility to use type parameters. Template depends only on the properties that is actually uses from its parameter types and does not require different types used as arguments to be explicitly related. In particular, the argument types used as a template need not be from a single inheritance hierarchy.


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


template <class T>
T max( T a, T b)
{
    if ( a > b )
        return a;
    else
        return b;
}


A template is not a single function! It is rather a schema. The process of generating a concrete function or class declaration from a template and a template argument is often called template instantiation. A version of a template for a particular argument is called a specialization.

Instantiation

The instantiation is - in most cases - an automatic process.


    double x, y = 5.1, z = 3.14;

    x = max( y, z);

Templates can take type parameters or parameters of scalar types:


template <class T, T defval>
class C
{
    T   t[defval];
}

C<int,10>   c;

A template parameter can be

  • constant expression

  • address of an object or function with external linkage in form of &obj, or f

  • non-overloaded) pointer to member

But can not be a string literal: "hello"

Type equivalence


C<char,10>		c1;
C<int, 10>      c2;
C<int, 25-15>   c3;

Instantiation, template argument deduction


int     i = 3, j = 4, k;
double  x = 3.14, y = 4.14, z;
const int ci = 6;

k = max( i, j);     // -> max(int, int)
z = max( x, y);     // -> max(double, double)
k = max( i, ci);    // -> max(int, int), with trivial conversion

z = max( i, x);     // -> ambiguous, no standard conversion


template <class T, class S>
T max( T a, S b)
{
    if ( a > b )
        return a;
    else
        return b;
}


int     i = 3;
double  x = 3.14;

z = max( i, x);     // ok, but..

z == 3.0    // ??

There is no way to deduce type parameter in runtime.


template <class R, class T, class S>
R max( T a, S b)
{
    if ( a > b )
        return a;
    else
        return b;
}

z = max( i, x);     // error

Of course, the return type has no role in deduction. Template argument R is not deducable.


template <class R, class T, class S>
R max( T a, S b, R)
{
    if ( a > b )
        return a;
    else
        return b;
}

z = max( i, x, 0.0);    // ok, but ugly and misleading

Explicit specialization


template <class R, class T, class S>
R max( T a, S b)
{
    if ( a > b )
        return a;
    else
        return b;
}

z = max<double>( i, x);             // ok, returns 3.14
k = max<long, long, int>( i, x);    // converts to long and int
k = max<int, int, int>( i, j);      // unnecessary

Template overloading


template <class T>  T   max(T,T);
template <class R, class T, class S>    R   max(T,S);

User specializations



char *s1 = "Hello";
char *s2 = "world";

cout << max( s1, s2);       // ??

template <>
const char *max<const char *>( const char *s1, const char *s2)
{
    return  strcmp( s1, s2) < 0;
}

or in shorter form:


template <> const char *max( const char *s1, const char *s2) .

Template classes

Since class template parameters regularly cannot be deduced from constructor parameters, objects from template classes must be explicitly specialized:


#include <iostream>
#include "matrix.h"

using namespace std;

int main()
{
    matrix<int>  m(10,20);

    m.at(2,3) = 1;
    cout << m(2,3) << endl;

    return 0;
}

Consider all the member functions are template functions for a template class. Even those are templates, where there is no explicite use of parameter T.


int rows() const { return x; }

Of course, there is the unvisible this parameter, which implicitelly depends from the parameter T.

Parametric polymorphism

A template class provides an alternative way of code reuse: parametric polymorphism.

Template class specialization

Let familiar with this ugly notation: namespace is matrix<T>, type of class is matrix<T>, inside the namespace matrix is matrix<T> by default


matrix<T>& matrix<T>::operator+=( const matrix &other) ...

The reason is the template class specialization:


template <>
class matrix<bool>
{
    //
    // totally different code
    //
}

matrix<bool>& matrix<bool>::operator+=( const matrix &other) ...

Partial specialization

There is possible to partially specialize a class template.


template <class A, class B>
class C
{
    // ...
}

template <class B>
class C<concreateType,B>
{
    // ...
}

Default Parameter

You can define default template arguments. They may even refer to previous template parameters:


template <class T, class C = deque<T> > 
class std::stack {
	// ...
};