Recursive template metaprogramming (Part I)

This article is a writeup to practice on recursive template metaprogramming. It is that may come in handy for compile time operations. I want to thank yoco for giving me a tutorial and introduction to the topic.


Since I’m here to share my write-up and walkthroughs for practice on template metaprogramming, there are some prerequisites that you may want to get familiar first, or even just take a look at the examples inside it to get a feel about it.

  • Cppref – Explicit (full) template specialization
  • Cppref – Partial template specialization
  • Wiki – Template metaprogramming

Recursive template metaprogramming

Writing recursive templates is just like how you write them in normal functions. the extra effort is to distinguish template declaration / partial specialization / full specialization besides writing out clear definitions.

Basic Utility

We would need list-like structure that represents determined values at compile time.

template<int ... Ints>
struct IntList;

template<typename ... Types>
struct TypeList;

By the way, C++11 does not provide constant expression (constexpr) std::min and std::max , an implementation just like the following is later added in C++14.

template<typename T>
constexpr const T& min(const T& a, const T& b) {
  return a < b ? a : b;
}
template<typename T>
constexpr const T& max(T const& a, T const& b) {
  return a < b ? b : a;
}

List Summation

Simply construct a static assertion that takes a IntList.

int main ()
{
  using values = IntList<1, 1, 2, 3, 5, 8>;
  static_assert(Sum<v>::value == 20);
}

When the body of a template is not found, the compiler will look for its specialization in the source. To take the integers inside a list into specialization, we will put them in the template parameters.

Line 6 lets the compiler to generate codes that provides IntList<Ints ...> into Sum <>.

// declaration
template<typename T>
struct Sum;
// specialization
template<int ... Ints>
struct Sum <IntList<Ints ...>> {
  using value = SumImpl<Ints ...>;
};

Sum<> is the interface the users of template takes access to. We implement the actual summation in SumImpl. Just like a recursive function, a recursive template needs to specify recursion and the base case. In template we would need to specify a declaration to the template to signal the compiler to deduct the variadic template (line 2) with the recursion template specified (line 4~8).

// declaration
template<int ... Ints>
struct SumImpl;
// recursion
template<int head, int tail ...>
struct SumImpl<head, tail ...> {
  using value = head + SumImpl<tail ...>;
};
// base case
template<int single>
struct SumImpl<single> {
  using value = single;
};
template<> 
struct SumImpl<> {
  using value = 0;
};

Min / Max / Any

With the same logic, it is easy to implement Min / Max / isAny as a practice.

///////////////////////////////////////////////////////////
////// Min
// declaration
template<typename T>
struct Min;
template<int ... Ints>
struct MinImpl;
// recursion
template<int head, int ... tail>
struct MinImpl <head, tail ...> {
  static constexpr int value = 
    detail::min(head, MinImpl<tail ...>::value);
};
// base
template<int single>
struct MinImpl<single> {
  static constexpr int value = single;
};
// specialization
template<int ... Ints>
struct Min <IntList<Ints ...>> {
  static constexpr int value = MinImpl<Ints ...>::value;
};
///////////////////////////////////////////////////////////
////// Max
// declaration
template<typename T>
struct Max;
template<int ... Ints>
struct MaxImpl;
// recursion
template<int head, int ... tail>
struct MaxImpl<head, tail ...> {
  static constexpr int value = 
    detail::max(head, MaxImpl<tail ...>::value);
};
// specialization
template<int single>
struct MaxImpl<single> {
  static constexpr int value = single;
};
template<int ... Ints>
struct Max<IntList<Ints...>> {
  static constexpr int value = MaxImpl<Ints ...>::value;
};
//////////////////////////////////////////////////////////
////// Any
template<typename toMatch, typename T>
struct Any;
template<typename toMatch, typename ... Types>
struct AnyImpl;

template<typename toMatch, typename head, typename ... tail>
struct AnyImpl <toMatch, head, tail ...> {
  static constexpr bool value = 
    std::is_same<toMatch, head>::value | 
    AnyImpl<toMatch, tail ...>::value;
};
template <typename toMatch, typename single>
struct AnyImpl <toMatch, single> {
  static constexpr bool value = std::is_same<toMatch, single>::value;
};
template<typename toMatch, typename ... Types>
struct Any <toMatch, TypeList<Types ...>> {
  static constexpr bool value = AnyImpl<toMatch, Types ...>::value;
};

In the next part I would implement utilities like Find, Remove, PopFront, and PopBack. Lastly I would implement MergeSort using recursive template metaprogramming as a milestone to this practice.

Author: eopXD

Hi 我是 eop ,希望人生過得有趣有挑戰XD

Leave a Reply