Most C++ programmers will do little Template Meta Programming. However we could all use Template Meta Programs (TMP) in our own code. Hence a basic understanding of TMP will make C++ programming much more enjoyable. My aim here is not so much to show how to write template meta programs but to show how how they are written. Let us start with something simple. Consider:
int Factorial(int n)
{
return n ==1 ? 1 : (n * Factorial(n - 1));
}
Here is a simple factorial function that can be turned into a Template Meta Program (TMP) as follows:
template <int N>
struct factorial
{
enum {value = N*factorial<N-1>::value };
};
template <>
struct<1> factorial
{
enum {value = 1 };
};
factorial<10> f;
To create the object f, the compiler has to make factorial<10>. It has the primary and the specialised template to choose from. The specialised template does not match. Hence it uses the primary template which “calls” factorial<9> which “calls” factorial<8> and so on. But when the value reaches one the compiler tries to use the most specialised version and this time it succeeds and the recursion stops. Thus factorial<10>::value will return the value of factorial 10. A few key points:
- Variables are immutable.
- Conditional statements are implemented through the use of partial specialistaion.
- There is no iteration. Recursive function call is simulated by generating classes recursively.
- Generated classes are not compiled unless an object of that type is required at run time. In the above case, factorial<10> is in the compiled code because an object of that type, namely f, is declared. But other classes like factorial<9> or factorial<8> are not available at run time.
Apart from class the only other template parameters that can be used to declare a template are integral types such as bool and int but not float. We have already used int. later we shall see the use of bool.
As another example consider a recursive version of GCD:
int GCD(int m, int n)
{
if (n = 0) return m;
else return GCD(n, m%n);
}
Converting to TMP is straightforward [Walter Brown] :
template <int M, int N>
struct gcd
{
enum { value = gcd<N, M%N>::value };
};
template <int M>
struct gcd<M, 0>
{
enum { value = M };
};
Here gcd<56,72>::value will return the value 8. These types of numerical algorithms can be done more easily now using C++14 ‘constexpr’ (not available in VS2013/Visual C++). Here is an exercise based on Pascal’s triangle:
int Combination(int const K, int const N)
{
if (K == 0) return 1;
else if (N == K) return 1;
else return Combination(K-1,N-1) + Combination(K, N-1);
}
Implementing that as a TMP should not be difficult.
Let’s move on to a different pattern:
template<class T>
struct rank
{
enum {value = 0 };
};
template<class U,size_t N>
struct rank<U[N]>
{
enum { value = 1 + rank<U>::value };
};
Here
using array_t = int[5][6][7];
rank<array_t>::value yields 3
As an aside array_t is a 5 element array of type int[6][7] and the latter is a 6 element array of type int[7]. Hence if you replace the above specilaisation with
template<class U,size_t N>
struct rank<U[N]>
{
enum { value = N + 10*rank<U>::value };
};
then rank<array_t>::value will return 765 (not 567). Notice that the specialisation is declared with two parameters but defined with only one. In general a specialisation can have fewer or more parameters in its declaration but must be defined with the same number of parameters as the primary for the specialised to be considered as a special case of the primary.
The more interesting aspect of TMP deals with type. Boost Spirit is a parser written entirely in TMP style. Let's start with something simple:
template<class T>
struct remove_const
{
using type = T;
};
template<class T>
struct remove_const<T const>
{
using type = T;
};
Thus remove_const<const int>::type will have type int because it matches the more specialised template. Modifying the above to remove volatile should be straightforward. 'remove_const' is part of the C++11 standard and so are a few others listed later.
Consider the following template:
conditional<bool,T,U>
where
conditional<b,T,U>::type
is T if b is true and U if false. Here is an implementation.
template <bool, class T, class U>
struct conditional { using type = T; };
template<class T, class U>
struct conditional<false, T, U> { using type = U; };
The above code says that
conditional<b,T,U>::type
is by default T unless b is false when the more specialised version is chosen and the type becomes U. Hence
conditional < 10 < 0, int, unsigned int > ::type
is of type unsigned int.
conditional<(q<0),F,G>::type{}(…)
will call of one the two function objects F or G depending on q and the selection is done at compile time.
class D: public conditional<(q<0),B1,B2>::type{…};
inherit from B1 or B2 depending on q.
"conditional" is also part of the standard library. The standard also defines the following templates
- add_const
- add_cv
- add_pointer
- add_reference
- add_volatile
- aligned_storage
- alignment_of
- conditional
- decay
- enable_if
- extent
- false_type
- has_nothrow_assign
- has_nothrow_constructor
- has_nothrow_copy
- has_trivial_assign
- has_trivial_constructor
- has_trivial_copy
- has_trivial_destructor
- has_virtual_destructor
- integral_constant
- is_abstract
- is_arithmetic
- is_array
- is_base_of
- is_class
- is_compound
- is_const
- is_convertible
- is_empty
- is_enum
- is_floating_point
- is_function
- is_fundamental
- is_integral
- is_member_function_pointer
- is_member_object_pointer
- is_member_pointer
- is_object
- is_pod
- is_pointer
- is_polymorphic
- is_reference
- is_same
- is_scalar
- is_signed
- is_union
- is_unsigned
- is_void
- is_volatile
- make_signed
- make_unsigned
- rank
- remove_all_extents
- remove_const
- remove_cv
- remove_extent
- remove_pointer
- remove_reference
- remove_volatile
- true_type
The semantics of these templates can be inferred from the name except in a few cases like ‘decay’. The definition of these templates are quite simple too.
The Sunday Programmer 