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.
Original link: eopXD