Template metaprogramming is not yet a well-defined programming startegy. To became a full-featured software paradigm, we need elementary building blocks, construction tools and libraries.
There is already a number of such libraries:
Andrei Alexandrescu's Loki library: www.moderncppdesign.com
The Boost library: www.boost.org
In the following sections we show some parts of Loki with usage examples. These templates provide some basic utility functionalities.
Many times we want to select on compile time constants. Templates however can be specialized only different types. Therefore we need a utility to map constants to types.
//
// Mapping Integral constants to types
//
template <int v>
struct Int2Type
{
enum { value = v };
};
Int2Type<0>::value and Int2Type<1>::value has different type, because they have different template parameters.
Usage example. The following code is illegal, if there is no Clone function in T type.
illegal code
template <typename T, bool isPolymorphic>
class MyContainer
{
public:
void DoSomething( T* p)
{
if ( isPolymorphic )
{
T *newPtr = p->Clone();
// ...
}
else
{
T *newptr = new T(*p);
// ...
}
}
// ...
}
The following is legal, because only one of the DoSomething will be instantiated.
template <typename T, bool isPolymorphic>
class MyContainer
{
private:
void DoSomething( T* p, Int2Type<true>)
{
T* newptr = p->Clone();
// ...
}
void DoSomething( T* p, Int2Type<false>)
{
T* newptr = new T(*p);
// ...
}
public:
void DoSomething( T* p)
{
DoSomething( p, Int2Type<isPolymorphic>());
}
};
Similar mapping could be important from types to types.
//
// Type-to-type mapping
//
template <class T, class U>
T *Create(const U& arg)
{
return new T(arg);
}
The following is illegal, because there is no partial specialization for functions.
// illegal code: no partial specialization for functions
template <class U>
Widget *Create<Widget, U>(const U& arg)
{
return new Widget(arg, -1);
}
One can use the old trick of dummy extra parameters, but that is always artifical:
template <class T, class U>
T *Create( const U& arg, T) // T is dummy
{
return new T(arg);
}
template <class U>
Widget *Create( const U& arg, Widget) // Widget is dummy
{
return new Widget(arg,-1);
}
The Type2Type template provides a much transparent solution:
template <typename T>
struct Type2Type
{
typedef T OriginalType;
};
template <class T, class U>
T *Create( const U& arg, TypeToType<T>)
{
return new T(arg);
}
template <class U>
Widget *Create( const U& arg, TypeToType<Widget>)
{
return new Widget(arg, -1);
}
//
// use Create:
//
String *pS = Create("Hello", Type2Type<String>()); // no need for Widget const...
Widget *pW = Create( 200, Type2Type<Widget>());
This is useful for compile-time selection of types.
template <typename T, bool isPolymorphic>
class MyContainer
{
// store pointers in polymorphic case: vector<T *>
// store values otherwise: vector<T>
};
template <typename T, bool isPolymorphic>
struct MyContainerValueTraits
{
typedef T* ValueType;
};
template <typename T>
struct MyContainerValueTraits< T, false>
{
typedef T ValueType;
};
template <typename T, bool isPolymorphic>
struct MyContainer
{
typedef MyContainerValueTraits<T,isPolymorphic> Traits;
typedef typename Traits::ValueType ValueType;
// ...
vector<ValueType> v;
};
The problem: it is clumsy and doesn't scale: for each type selection we must define a new traits class template.
template <bool Flag, typename T, typename U>
struct Select
{
typename T Result;
};
template <typename T, typename U>
struct Select<false, T, U>
{
typename U Result;
};
template <typename T, bool isPolymorphic>
struct MyContainer
{
typedef typename Select<isPolymorphic, T*, T>::Result ValueType;
// ...
vector<ValueType> v;
};
For more advanced utilities we need some kind of data structure , which can hold more complex compile-time information. Alexandrescu's Loki has Typelist to store types and a number of handy utilities.
Typelist is ended with a special sentinel type: NullType:
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;
Loki defines a number of elementary utilities for typelist. One of the most important features of a list is its length.
//
// 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 };
};
if TList non-zero and i is 0 then head
if TList non-zero and i non-zero then TypeAt(Tail,i-1)
else out of bound access then compile time error
template <class Head, class Tail>
struct TypeAt< TypeList<Head, Tail>, 0>
{
typedef Head Result;
};
template <class Head, class Tail, unsigned int i>
struct TypeAt< TypeList<Head, Tail, i>
{
typedef typename TypeAt<Tail,i-1>::Result Result;
};
If there is out of bound access, then no specialization for TypeAt<NullType,i>
The next template produces the position of a typename in a typelist:
if TList is NullType then -1
if the Head is T then 0
if IndexOf(Tail,T)==-1 then -1
else IndexOf(Tail,T)+1
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 };
};
There are also modifyind routines on Typelist:
//
// Append
//
template <class TList, class T> struct Append;
template <>
struct Append< NullType, NullType>
{
typedef NullType Result;
};
template <class T>
struct Append< NullType, T>
{
typedef TYPELIST_1(T) Result;
};
template <class Head, class Tail>
struct Append< NullType, Typelist<Head,Tail> >
{
tyepdef Typelist<Head,Tail> Result;
};
template <class Head, class Tail, class T>
struct Append< Typelist<Head,Tail>, T>
{
typedef Typelist<Head, typename Append<Tail,T>::Result> Result;
};
// usage
typedef Append<SignedIntegrals,
TYPELIST_3(float,double,long double)>::Result SignedTypes;
//
// Erase
//
template <class TList, class T> struct Erase;
template <class T>
struct Erase< NullType, T>
{
typedef NullType Result;
};
template <class T, clas Tail>
struct Erase< Typelist<T, Tail>, T>
{
typedef Tail Result;
};
template <class Head, class Tail, class T>
struct Erase< TypeList<Head, Tail>, T>
{
typedef TypeList<Head, typename Erase<Tail,T>::Result> Result;
};
Here is an example, to show the expressivity of Loki. In a previous example we introduced copy_trait to express the copy startegy or policy of the classes.
The problem with that solution is the separate specialization of the is_pod class template. With the help of Loki we can collect all the pod classes in one place
#ifndef MATRIX_H
#define MATRIX_H
#include <stdexcept>
#include <iostream>
#include <typeinfo>
#include "loki/Typelist.h"
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)
{
std::cerr << typeid(T).name() << " default copy with loop" << std::endl;
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)
{
std::cerr << typeid(T).name() << " bitwise copy" << std::endl;
memcpy( to, from, n*sizeof(T));
}
};
template <class T, class Cpy = copy_trait<T,is_pod<T>::value> >
class matrix
{
public:
matrix( int i, int j ) : x(i), y(j), v(new T[i*j]) { }
matrix( const matrix &other) { copy(other); }
~matrix() { delete [] v; }
matrix& operator=( const matrix &other)
{
matrix temp(other);
x = temp.x;
y = temp.y;
T *v2 = temp.v; temp.v = v; v = v2;
return *this;
}
int rows() const { return x; }
int cols() const { return y; }
T& at( int i, int j) { check(i,j); return operator()(i,j); }
const T& at( int i, int j) const { check(i,j); return operator()(i,j); }
T& operator()( int i, int j) { return v[i*y+j]; }
const T& operator()( int i, int j) const { return v[i*y+j]; }
private:
int x;
int y;
T *v;
void check( int i, int j) const
{
if ( 0 > i || i >= x || 0 > j || j >= y )
throw( std::out_of_range("Bad index"));
}
void copy( const matrix &other);
};
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);
}
#endif /* MATRIX_H */
The TYPELIST collect all the pod types into one code segment. The IndexOf algorithm tries to find the second parameter in the first typelist, and returns the index on success or -1 otherwise. Therefore is_pod<T>::value is set to true for these types. These types ensure a set of default pod types for clients. In the main.cpp we must specify just the exceptions:
#include "matrix2.h"
int main()
{
matrix<int> mi1(2,3), mi2(2,3);
matrix<long> ml1(4,4), ml2(4,4);
matrix<double> md1(5,5), md2(5,5);
matrix<double, copy_trait<double,true> > md3(5,5), md4(5,5);
mi1 = mi2;
ml1 = ml2;
md1 = md2;
md3 = md4;
return 0;
}
/* result:
i bitwise copy
l default copy with loop
d default copy with loop
d bitwise copy
*/
This way we can automatize (almost) any algoritm in compilation time.