Template Meta Programming in C++: A Gentle Introduction – Part I : Template Specialisation

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

  1. add_const
  2. add_cv
  3. add_pointer
  4. add_reference
  5. add_volatile
  6. aligned_storage
  7. alignment_of
  8. conditional
  9. decay
  10. enable_if
  11. extent
  12. false_type
  13. has_nothrow_assign
  14. has_nothrow_constructor
  15. has_nothrow_copy
  16. has_trivial_assign
  17. has_trivial_constructor
  18. has_trivial_copy
  19. has_trivial_destructor
  20. has_virtual_destructor
  21. integral_constant
  22. is_abstract
  23. is_arithmetic
  24. is_array
  25. is_base_of
  26. is_class
  27. is_compound
  28. is_const
  29. is_convertible
  30. is_empty
  31. is_enum
  32. is_floating_point
  33. is_function
  34. is_fundamental
  35. is_integral
  36. is_member_function_pointer
  37. is_member_object_pointer
  38. is_member_pointer
  39. is_object
  40. is_pod
  41. is_pointer
  42. is_polymorphic
  43. is_reference
  44. is_same
  45. is_scalar
  46. is_signed
  47. is_union
  48. is_unsigned
  49. is_void
  50. is_volatile
  51. make_signed
  52. make_unsigned
  53. rank
  54. remove_all_extents
  55. remove_const
  56. remove_cv
  57. remove_extent
  58. remove_pointer
  59. remove_reference
  60. remove_volatile
  61. 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.

Advertisements

About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in C++, Software Engineering and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s