Templates

  Your quote here -- B. Stroustrup


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.


Overloading


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



Prepocessor macro:


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

A template parameter before C++11 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"

Since C++11 it is a bit relaxed



Instantiation, parameter deduction


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


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 ? s1 : s2;
}


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.


// even this is a template:
int rows() const { return x; }



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
{
    // ...
};


Template metaprogramming



// Erwin Unruh, untitled program, 
// ANSI X3J16-94-0075/ISO WG21-462, 1994.

template <int i>
struct D
{
    D(void *);
    operator int();
};

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

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

struct is_prime<0,0> { enum { prim = 1 }; };
struct is_prime<0,1> { enum { prim = 1 }; };
struct Prime_print<2>
{
    enum { prim = 1 };
    void f() { D<2> d = prim; }
};

void foo()
{
    Prime_print<10> a;
}

// output:
// unruh.cpp 30: conversion from enum to D<2> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<3> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<5> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<7> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<11> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<13> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<17> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<19> requested in Prime_print




Factorial function


Template metaprogramming can inprove efficiency:



int factorial( int n)
{
    return (n==0) ? 1 : n*factorial(n-1)l
}

int main()
{
    cout << factorial(5) << endl;
    return 0;
}



But we can compute the value of the factorial function in compile-time:



// factorial.cpp

#include <iostream>

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

template <>
struct Factorial<1>
{
    enum { value = 1 };
};

// example use
int main()
{
    const int fact5 = Factorial<5>::value;
    std::cout << fact5 << endl;
    return 0;
}


Template Recursion


Factorial<5> --> Factorial<4> --> ... -> Factorial<0>

intermediate classes are in pending state
recursive template instatiation nesting depth is limited

- ISO/ANSI recommend at least 17
- everyday compilers can do much more
- sometimes (g++) nesting depth is parameter



Meta Control Structures



In 1966 Bohm and Jacopini proved, that Turing machine implementation is
equivalent the exsistence of conditional and looping control structures.


// IF

template <bool condition, class Then, class Else>
struct IF
{
    typedef Then RET;
};

template <class Then, class Else>
struct IF<false, Then, Else>
{
    typedef Else RET;
};


This is a partial template specialization, we only specialize it on
condition==false, Then and Else remains parameter.

// if sizeof(int) < sizeof(long) then use long else use int
IF< sizeof(int)<sizeof(long), long, int>::RET  i;


template <typename T, typename S>
IF< sizeof(T)<sizeof(S), S, T>::RET max(T t, S s)
{
    if ( t < s)
        return s;
    else
        return t;
}



Metafunctions as Parameter

In dynamic C++ one can use pointer to function as parameter or return value


// accumulate(n,f) := f(0) + f(1) + ... + f(n)

template <int n, template<int> class F>
struct Accumulate
{
    enum { RET = Accumulate<n-1,F>::RET + F<n>::RET };
};

template <template<int> class F>
struct Accumulate<0,F>
{
    enum { RET = F<0>::RET };
};

template <int n>
struct Square
{
    enum { RET = n*n };
};

cout << Accumulate<3,Square>::RET << endl;



Motivation

This is a motivating example:


int main()
{
    const unsigned int di = 12;
    const unsigned int oi = 014;
    const unsigned int hi = 0xc;

    const unsigned int bi0 = binary_value("1101");
    const unsigned int bi1 = binary<1100>::value;
}


Why in compilation time

- Speed.
- Constantness (array size, enum value must be known in compilation time).
- Compiler control.


template <unsigned long N>
struct binary
{
    static unsigned const value
       = binary<N/10>::value * 2   // prepend higher bits
         + N%10;                   // to lowest bit
};

template <>                           // specialization
struct binary<0>                      // terminates recursion
{
    static unsigned const value = 0;
};



Expression templates


Object-orientation sometimes sacrifies efficiency for readibility and
ease of code maintenance:


Array a, b, c, d, e;

a = b + c + d + e;


This will generate the following pseudo-code:


// pseudocode for a = b + c + d + e

double* _t1 = new double[N];
for ( int i=0; i<N; ++i)
    _t1[i] = b[i] + c[i];

double* _t2 = new double[N];
for ( int i=0; i<N; ++i)
    _t2[i] = _t1[i] + d[i];

double* _t3 = new double[N];
for ( int i=0; i<N; ++i)
    _t3[i] = _t2[i] + e[i];

for ( int i=0; i<N; ++i)
    a[i] = _t3[i];

delete [] _t3;
delete [] _t2;
delete [] _t1;



Performace problems

- For small arrays new  andi delete result poor performance: 1/10 of C.
- For medium arrays, overhead of extra loops and memory access add +50%
- For large arrays, the cost of the temporaries are the limitations: by Veldhuizen


minimal expression template implementation


#include <iostream>

using namespace std;

// this class encapsulates the "+" operation.
struct plus
{
    static double apply( double a, double b)
    {
        return a+b;
    }
};


// the node in the parse tree.
template <typename Left, typename Op, typename Right>
struct X
{
    Left    left;
    Right   right;

    X( Left t1, Right t2) : left(t1), right(t2)  { }

    double operator[](int i)
    {
        return Op::apply( left[i], right[i] );
    }
};


struct Array
{
    // constructor
    Array( double *data, int N) : data_(data), N_(N) { }

    // assign an expression to the array
    template <typename Left, typename Op, typename Right>
    void operator=( X<Left,Op,Right> expr)
    {
        for ( int i = 0; i < N_; ++i)
            data_[i] = expr[i];
    }

    double operator[](int i)
    {
        return data_[i];
    }

    double *data_;
    int N_;
};

template <typename Left>
X<Left, plus, Array> operator+( Left a, Array b)
{
    return X<Left, plus, Array>(a,b);
}

int main()
{
    double a_data[] = { 2, 3, 5, 9 };
    double b_data[] = { 1, 0, 0, 1 };
    double c_data[] = { 3, 0, 2, 5 };
    double d_data[4];

    Array A(a_data,4);
    Array B(b_data,4);
    Array C(c_data,4);
    Array D(d_data,4);

    D = A + B + C;

    for ( int i = 0; i < 4; ++i )
        cout << D[i] << " ";
    cout << endl;
}




Traits and policy classes



template <class T>
class matrix
{
public:
    matrix( int i, int j );
    matrix( const matrix &other);
    ~matrix();
    matrix operator=( const matrix &other);

    int rows() const { return x; }
    int cols() const { return y; }

    T& at( int i, int j) throw(indexError);
    T  at( int i, int j) const throw(indexError);
    T& operator()( int i, int j);
    T  operator()( int i, int j) const;

    matrix operator+=( const matrix &other);
private:
    int  x;
    int  y;
    T   *v;
    void copy( const matrix &other);
    void check( int i, int j) const throw(indexError);
};


template <class T>
void matrix<T>::copy( const matrix &other)
{
    x = other.x;
    y = other.y;
    v = new T[x*y];
    for ( int i = 0; i < x*y; ++i )
        v[i] = other.v[i];
}



// Specializations for POD types

template <>
void matrix<long>::copy( const matrix &other)
{
    x = other.x;
    y = other.y;
    v = new long[x*y];
    memcpy( v, other.v, sizeof(long)*x*y);
}



Using traits



template <typename T>
struct copy_trait
{
    static void copy( T* to, const T* from, int n)
    {
        for( int i = 0; i < n; ++i )
            to[i] = from[i];
    }
};
template <>
struct copy_trait<long>
{
    static void copy( long* to, const long* from, int n)
    {
        memcpy( to, from, n*sizeof(long));
    }
};


template <class T, class Cpy = copy_trait<T> >
class matrix
{
    //...
};

template <class T, class Cpy>
void matrix<T,Cpy>::copy( const matrix &other)
{
    x = other.x;
    y = other.y;
    v = new T[x*y];

    Cpy::copy( v, other.v, x*y);
}



Policy classes



template <typename T>
struct is_pod
{
    enum { value = false };
};

template <>
struct is_pod<long>
{
    enum { value = true };
};

template <typename T, bool B>
struct copy_trait
{
    static void copy( T* to, const T* from, int n)
    {
        for( int i = 0; i < n; ++i )
            to[i] = from[i];
    }
};

template <typename T>
struct copy_trait<T, true>
{
    static void copy( T* to, const T* from, int n)
    {
        memcpy( to, from, n*sizeof(T));
    }
};

template <class T, class Cpy = copy_trait<T,is_pod<T>::value> >
class matrix
{
    // ...
};



Typelist



class NullType {};

struct EmptyType {};        // could be instantiated



We now can construct a null-terminated list of typenames:


typedef Typelist< char, Typelist<signed char,
        Typelist<unsigned char, NullType> > > Charlist;


For the easy maintenance, precompiler macros are defined to create Typelists:


#define TYPELIST_1(x)           Typelist< x, NullType>
#define TYPELIST_2(x, y)        Typelist< x, TYPELIST_1(y)>
#define TYPELIST_3(x, y, z)     Typelist< x, TYPELIST_2(y,z)>
#define TYPELIST_4(x, y, z, w)  Typelist< x, TYPELIST_3(y,z,w)>
// :

typedef TYPELIST_3(char, signed char, unsigned char)  Charlist;



//
//  Length
//
template <class TList> struct Length;

template <>
struct Length<NullType>
{
    enum { value = 0 };
};

template <class T, class U>
struct Length <Typelist<T,U> >
{
    enum { value = 1 + Length<U>::value };
};



template <class TList, class T> struct IndexOf;

template <class T>
struct IndexOf< NullType, T>
{
    enum { value = -1 };
};

template <class T, class Tail>
struct IndexOf< Typelist<Head, Tail>, T>
{
private:
    enum { temp = IndexOf<Tail, T>::value };
public:
    enum { value = (temp == -1) ? -1 : 1+temp };
};



Usage



typedef TYPELIST_4(char, signed char, unsigned char, int)  Pod_types;

template <typename T>
struct is_pod
{
    enum { value = ::Loki::TL::IndexOf<Pod_types,T>::value != -1 };
};

template <typename T, bool B>
struct copy_trait
{
    static void copy( T* to, const T* from, int n)
    {
        for( int i = 0; i < n; ++i )
            to[i] = from[i];
    }
};
template <typename T>
struct copy_trait<T, true>
{
    static void copy( T* to, const T* from, int n)
    {
        memcpy( to, from, n*sizeof(T));
    }
};

template <class T, class Cpy = copy_trait<T,is_pod<T>::value> >
class matrix
{
    // ...
};

template <class T, class Cpy>
void matrix<T,Cpy>::copy( const matrix &other)
{
    x = other.x;
    y = other.y;
    v = new T[x*y];

    Cpy::copy( v, other.v, x*y);
}





Practice
========




1. Write a C++ Macro to print the bigger value


#include <iostream>

#define MAX(a,b)  <solution here>


int main()
{
  int i = 3;
  double d = 3.14;

  std::cout << "MAX( i, d ) = "   << ( MAX( i, d) )   << std::endl;
  std::cout << "MAX( i, d )*2 = " << ( MAX( i, d)*2 ) << std::endl;
  std::cout << "MAX( ++i, d ) = " << ( MAX( ++i, d) ) << std::endl;

  return 0;
}



2. Write a template which returns the bigger value.
   The two parameter types belong to the same type.


#include <iostream>

<solution here>

int main()
{
  int i = 3, j = 4;
  double d = 3.14, e = 2.71;

  std::cout << "max( i, j ) = "  << max( i, j) << std::endl;
  std::cout << "max( d, e ) = "  << max( d, e) << std::endl;
//  std::cout << "max( i, d ) = "  << max( i, d) << std::endl;  // will not compile

  return 0;
}



3. Write a template which returns the bigger value.
   The two parameter types belong to different types.


#include <iostream>

<solution here>

int main()
{
  int i = 3;
  double d = 3.14;

  std::cout << "max( d, i ) = "  << max( d, i) << std::endl;
  std::cout << "max( i, d ) = "  << max( i, d) << std::endl;

  return 0;
}


4. The same as 3. but You specify the type of the return value
   with this tricky 3rd parameter


#include <iostream>

<solution here>

int main()
{
  int i = 3;
  double d = 3.14;

  std::cout << "max( d, i, 0.0 ) = "  << max( d, i, 0.0) << std::endl;
  std::cout << "max( i, d, 0.0 ) = "  << max( i, d, 0.0) << std::endl;

  return 0;
}


5. The same as 3. but You specify the type of the return value
   with user specialization a better solution


#include <iostream>

<solution here>

int main()
{
  int i = 3;
  double d = 3.14;

  std::cout << "max<double>( d, i ) = "  << max<double>( d, i) << std::endl;
  std::cout << "max<double>( i, d ) = "  << max<double>( i, d) << std::endl;

  return 0;
}



6. Write a template function which returns the bigger parameter.
   The return type is defined by a template metaprogram which computes
   the "better" return type.


#include <iostream>

<solution here>

int main()
{
  int i = 3;
  double d = 3.14;

  std::cout << "max( d, i ) = "  << max( d, i) << std::endl;
  std::cout << "max( i, d ) = "  << max( i, d) << std::endl;

  return 0;
}


7. The same as 6. but instead of template metaprogram use std::common_type.


#include <iostream>
#include <type_traits>

<solution here>

int main()
{
  int i = 3;
  double d = 3.14;

  std::cout << "max( d, i ) = "  << max( d, i) << std::endl;
  std::cout << "max( i, d ) = "  << max( i, d) << std::endl;

  return 0;
}



Solutions
=========



1. Write a C++ Macro to print the bigger value



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



2. Write a template which returns the bigger value.
   The two parameter types belong to the same type.



template <typename T>
T max( T x, T y)
{
  if ( x > y )
    return x;
  else
    return y;
}




3. Write a template which returns the bigger value.
   The two parameter types belong to different types.



template <typename T, typename S>
T max( T x, S y)
{
  if ( x > y )
    return x;
  else
    return y;
}



4. The same as 3. but You specify the type of the return value
   with this tricky 3rd parameter


template <typename R, typename T, typename S>
R max( T x, S y, R)
{
  if ( x > y )
    return x;
  else
    return y;
}



5. The same as 3. but You specify the type of the return value
   with user specialization a better solution


template <typename R, typename T, typename S>
R max( T x, S y)
{
  if ( x > y )
    return x;
  else
    return y;
}


6. Write a template function which returns the bigger parameter.
   The return type is defined by a template metaprogram which computes
   the "better" return type.



template <typename T, typename S>
IF< sizeof(T)<sizeof(S), S, T>::RET max(T t, S s)
{
    if ( t < s)
        return s;
    else
        return t;
}



7. The same as 6. but instead of template metaprogram use std::common_type.


template <typename T, typename S>
typename std::common_type<T, S>::type max( T x, S y)
{
  if ( x > y )
    return x;
  else
    return y;
}