Porkoláb Zoltán
C++ template Metaprogramming
Simonyi Károly Szakkollégium
2012.05.03.
Outline
Templates in C++
Template specialization
Template metaprogramming
Examples
Debugging Template metaprograms
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;
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 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"
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);
z = max( x, y);
k = max( i, ci);
z = max( i, x);
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);
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);
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);
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);
k = max<long, long, int>( i, x);
k = max<int, int, int>( i, j);
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.
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>
{
}
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
{
};
Variadic templates (From Stroustrup C++0x FAQ)
const string pi = "pi";
const char* m = "The value of %s is about %g (unless you live in %s).\n";
printf(m, pi, 3.14159, "Indiana");
void printf(const char* s)
{
while (s && *s)
{
if (*s=='%' && *++s!='%')
{
throw runtime_error("invalid format: missing arguments");
}
std::cout << *s++;
}
}
template<typename T, typename... Args>
void printf(const char* s, T value, Args... args)
{
while (s && *s)
{
if (*s=='%' && *++s!='%')
{
std::cout << value;
return printf(++s, args...);
}
std::cout << *s++;
}
throw std::runtime error("extra arguments provided to printf");
}
We can create variadic types
template<typename Head, typename... Tail>
class tuple<Head, Tail...> : private tuple<Tail...>
{
typedef tuple<Tail...> inherited;
public:
tuple() { }
tuple(typename add_const_reference<Head>::type v,
typename add_const_reference<Tail>::type... vtail)
: m_head(v), inherited(vtail...) { }
template<typename... VValues>
tuple(const tuple<VValues...>& other)
: m_head(other.head()), inherited(other.tail()) { }
template<typename... VValues>
tuple& operator=(const tuple<VValues...>& other)
{
m_head = other.head();
tail() = other.tail();
return *this;
}
typename add_reference<Head>::type head() { return m_head; }
typename add_reference<const Head>::type head() const { return m_head; }
inherited& tail() { return *this; }
const inherited& tail() const { return *this; }
protected:
Head m_head;
};
Template metaprogramming
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;
}
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:
#include <iostream>
template <int N>
struct Factorial
{
enum { value = N * Factorial<N-1>::value };
};
template <>
struct Factorial<1>
{
enum { value = 1 };
};
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.
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), 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
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: type-cheking.
template <unsigned long N>
struct binary
{
static unsigned const value
= binary<N/10>::value * 2
+ N%10;
};
template <>
struct binary<0>
{
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:
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 and 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 Veldhui
minimal expression template implementation
#include <iostream>
using namespace std;
struct plus
{
static double apply( double a, double b)
{
return a+b;
}
};
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
{
Array( double *data, int N) : data_(data), N_(N) { }
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];
}
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 {};
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;
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);
}
Static interface checking
template <class T>
class HasClone
{
public:
static void Constraints()
{
T* (T::*test)() const = &T::Clone;
test;
}
HasClone() { void (*p)() = Constraints; }
};
template <class T>
class C : HasClone<T>
{
};
Conversion Checking
Most fundamental check is whether a type could be converted to an other.
template <class T, class U>
class Conversion
{
public:
enum
{
exists = sizeof(Test(MakeT()))==sizeof(Small)
};
enum
{
sameType = false;
};
private:
typedef char Small;
class Big { char dummy[2]; };
static Small Test(U);
static Big Test(...);
static T MakeT();
};
typename <class T>
class Conversion<T,T>
{
public:
enum { exists = 1, sameType = 1 };
};
int main()
{
std::cout << Conversion<double, int>::exists <<
<< Conversion<char, char*>::exists <<
<< Conversion<std::vector<int>,std::list<int> >::exists
<< std::endl;
return 0;
}
Inheritance
The next step is to chech inheritance:
#define SUPERSUBCLASS(T,U) \
((Conversion<const U*, const T*>::exists && \
! (Conversion<const T*, const void*>::sameType))
Compile-Time Assertion
Based on compile-time decision we can decide to abort the program.
This is parallel to run-time assertions:
template <bool> class CompileTimeAssert;
template <> class CompileTimeAssert<true> {};
The trick is, that only specialization is exist: the general case has only
declaration. This declaration is neccessary, because otherwise the
specialization would be invalid.
CompileTimeAssert< SUPERSUBCLASS( X, Y) > MUST_BE_SUPERCLASS;
Debugging C++ Template metaprograms
#include <iostream>
static inline int f(char *s){ return 1;}
template <int N>
struct Fact
{
enum { begin = sizeof (f("")) };
enum { value = Fact<N-1>::value * N };
enum { end = sizeof (f("")) };
};
template <>
struct Fact<1>
{
enum { begin = sizeof (f("")) };
enum { value = 1 };
enum { end = sizeof (f("")) };
};
int main()
{
std::cout << Fact<6>::value << std::endl;
return 0;
}
~
$ g++ 31_fact.cpp
31_fact.cpp:18:30: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp:20:28: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<6>’:
31_fact.cpp:25:23: instantiated from here
31_fact.cpp:10:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<5>’:
31_fact.cpp:11:3: instantiated from ‘Fact<6>’
31_fact.cpp:25:23: instantiated from here
31_fact.cpp:10:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<4>’:
31_fact.cpp:11:3: instantiated from ‘Fact<5>’
31_fact.cpp:11:3: instantiated from ‘Fact<6>’
31_fact.cpp:25:23: instantiated from here
31_fact.cpp:10:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<3>’:
31_fact.cpp:11:3: instantiated from ‘Fact<4>’
31_fact.cpp:11:3: instantiated from ‘Fact<5>’
31_fact.cpp:11:3: instantiated from ‘Fact<6>’
31_fact.cpp:25:23: instantiated from here
31_fact.cpp:10:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<2>’:
31_fact.cpp:11:3: instantiated from ‘Fact<3>’
31_fact.cpp:11:3: instantiated from ‘Fact<4>’
31_fact.cpp:11:3: instantiated from ‘Fact<5>’
31_fact.cpp:11:3: instantiated from ‘Fact<6>’
31_fact.cpp:25:23: instantiated from here
31_fact.cpp:10:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp:12:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<3>’:
31_fact.cpp:11:3: instantiated from ‘Fact<4>’
31_fact.cpp:11:3: instantiated from ‘Fact<5>’
31_fact.cpp:11:3: instantiated from ‘Fact<6>’
31_fact.cpp:25:23: instantiated from here
31_fact.cpp:12:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<4>’:
31_fact.cpp:11:3: instantiated from ‘Fact<5>’
31_fact.cpp:11:3: instantiated from ‘Fact<6>’
31_fact.cpp:25:23: instantiated from here
31_fact.cpp:12:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<5>’:
31_fact.cpp:11:3: instantiated from ‘Fact<6>’
31_fact.cpp:25:23: instantiated from here
31_fact.cpp:12:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<6>’:
31_fact.cpp:25:23: instantiated from here
31_fact.cpp:12:3: warning: deprecated conversion from string constant to ‘char*’
Further reading:
Bjarne Stroustrup: The C++ Programming Language: Special Edition
Addison-Wesley. February 11, 2000
ISBN-10: 0201700735 | ISBN-13: 978-0201700732
David Vandevoorde and Nicolai M. Josuttis: C++ Templates: The Complete Guide
Addison-Wesley. November 22, 2002
ISBN-10: 0201734842 | ISBN-13: 978-0201734843
Andrei Alexandrescu: Modern C++ Design: Generic Programming
and Design Patterns Applied
Addison-Wesley. February 23, 2001
ISBN-10: 0201704315 | ISBN-13: 978-0201704310
David Abrahams and Aleksey Gurtovoy: C++ Template Metaprogramming:
Concepts, Tools, and Techniques from Boost and Beyond
Addison-Wesley. December 20, 2004
ISBN-10: 0321227255 | ISBN-13: 978-0321227256
Aleksey Gurtovoy and David Abrahams: Boost.MPL
http:
Eric Niebler: Boost.Proto
http:
Eric Niebler: Boost.Xpressive
http:
J. de Guzman and H. Kaiser: Boost.Spirit
http:
V. Karvonen and P. Mensonides: Boost.PP
http:
Ábel Sinkovics: Metaparse library
http:
C++now Conference. Aspen, Co, USA. May 13 – 18, 2012.
http:
Thank you!
http:
gsd@elte.hu | zoltan.porkolab@ericsson.com