Challenging exercises in Template Metaprogramming
Typelists and std::index_sequence
For type metaprogramming, the central data structures are the typelist and std::index_sequence. A TypeList is just a static list of types. A std::index_sequence is an integer sequence known at compile-time. TypeLists and std::index_sequences differ from run-time data structures, such as std::list, in that they don’t allow mutation. Adding an element to a TypeList, does not change the original TypeList: rather it creates a new typelist without modifying the original. If you are familar with functional programming languages like Haskell and F#, there’s a lot of parallel between working with typelists in C++ and lists in those languages.
Implementing a TypeList
A TypeList is implemented as a class template. A particular instance of a typelist is a template specialization that encodes the contents of the typelist as template arguments.
template<typename... Ts>
struct TypeList{
using type = TypeList<Ts...>;
static constexpr auto value = TypeList<Ts...>{};
};
using SignedIntegralTypes = TypeList<signed char, short,
int, long, long long>;make_index_sequence metafunction is used to create an integer sequence.
Manipulating TypeList and index_sequence
Manipulating the typelist and index_sequence typically requires breaking the typelist into parts, generally by separting the first element in the list (the head) from the remaining elements in the list (the tail).
// front implementation
template<typename List>
struct front;
template<typename Head, typename... Tail>
struct front<TypeList<Head,Tail...>>{
using type = Head;
static constexpr auto value = Head{};
};
template<typename List>
struct seq_front;
template<size_t First, size_t... Rest>
struct seq_front<std::index_sequence<First,Rest...>>{
static constexpr size_t value = First;
};
int main(){
static_assert(std::is_same_v<front<TypeList<int,float>>::type, int>);
constexpr auto seq_front_result = seq_front<std::index_sequence<1,5,8,12>>::value;
std::cout << std::format("\nseq_front result = {}", seq_front_result);
}The above implementation splits the typelist elements into the head and tail and then forms a new TypeList specialization from the elements in the tail.
Implementing pop_front
The pop_front metafunction removes the first element from the typelist. Its implementation splits the typelist elements into the head and tail and then forms a new typelist from the elements in the tail.
template<typename List>
struct pop_front;
template<typename Head, typename... Tail>
struct pop_front<TypeList<Head,Tail...>>{
using type = TypeList<Tail...>;
static constexpr auto value = TypeList<Tail...>{};
};
template<typename List>
struct seq_pop_front;
template<size_t First, size_t... Rest>
struct seq_pop_front<std::index_sequence<First,Rest...>>{
using type = std::index_sequence<Rest...>;
static constexpr auto value = std::index_sequence<Rest...>{};
};Implementing push_front
We can also insert elements onto the front of the typelist by capturing all of the existing elements into a template parameter pack, then creating a new TypeList specialization containing all of those elements:
template<typename Element, typename List>
struct push_front;
template<typename T, typename... Ts>
struct push_front<T, TypeList<Ts...>>{
using type = TypeList<T,Ts...>;
static constexpr auto value = TypeList<T,Ts...>{};
};
template<size_t I, typename IndexSequenceT>
struct seq_push_front;
template<size_t I, size_t... Is>
struct seq_push_front<I, std::index_sequence<Is...>>{
using type = std::index_sequence<I,Is...>;
static constexpr auto value = std::index_sequence<I,Is...>{};
};
template<size_t I, typename IndexSequence>
using seq_push_front_t = seq_push_front<I,IndexSequence>::type;Implementing push_back
// push_back implementation
template<typename Element, typename List>
struct push_back;
template<typename Element>
struct push_back<Element, TypeList<>>{
using type = TypeList<Element>;
};
template<typename Element, typename... Ts>
struct push_back<Element, TypeList<Ts...>>{
using type = TypeList<Ts...,Element>;
};
// push_back implementation for index_sequence
template<size_t I, typename IndexSequence>
struct seq_push_back;
template<size_t I, size_t... Is>
struct seq_push_back<I, std::index_sequence<Is...>>{
using type = std::index_sequence<Is...,I>;
static constexpr auto value = std::index_sequence<Is...,I>{};
};
template<size_t I, typename IndexSequence>
using seq_push_back_t = seq_push_back<I,IndexSequence>::type;Typelist algorithms
The fundamental typelist operations front, push_front, back and push_back can be composed to create more interesting typelist manipulations. For example, we can replace the first element in a typelist by applying push_front to the result of pop_front.
Going further, we can implement algorithms - searches, transformations, reversals as metafunctions operating on typelists.
Indexing
One of the most fundamental operations on a typelist is to extract a specific element of the list. Let us code up a metafunction to extract the \(N\)th element.
template<size_t I, typename List>
struct nth_element;
template<typename First, typename... Rest>
struct nth_element<1,TypeList<First, Rest...>>{
using type = First;
};
template<size_t N, typename First, typename... Rest>
struct nth_element<N, TypeList<First, Rest...>> : nth_element<N-1, TypeList<Rest...>>{};
template<size_t N, typename List, size_t... Is>
struct seq_nth_element;
template<size_t I, size_t... Is>
struct seq_nth_element<1,std::index_sequence<I,Is...>>{
static constexpr auto value = I;
};
template<size_t N, size_t I, size_t... Is>
struct seq_nth_element<N, std::index_sequence<I,Is...>> : seq_nth_element<N-1,std::index_sequence<Is...>>{};Implementing find_if
Many typelist algorithms search for data within the typelist. This too can be easily achieved with a recursive template metaprogram.
#include <utility>
#include <memory>
#include <format>
#include <iostream>
template<typename List, template<size_t I> typename Predicate, size_t... Is>
struct seq_find_if;
template<template<size_t > typename Predicate>
struct seq_find_if<std::index_sequence<>,Predicate> {
using type = std::false_type;
};
template<size_t First, template<size_t > typename Predicate, size_t... Is>
struct seq_find_if<std::index_sequence<First, Is...>,Predicate> {
static constexpr bool is_true = Predicate<First>::value;
static constexpr bool more_elements_to_check = (sizeof...(Is) > 0);
using type = std::conditional<
is_true,
std::integral_constant<size_t,First>,
typename std::conditional<more_elements_to_check, typename seq_find_if<std::index_sequence<Is...>,Predicate>::type, std::false_type>::type
>::type;
};
template<size_t N>
struct my_predicate{
using type = std::conditional<(N % 2 == 0),std::true_type, std::false_type>::type;
static constexpr bool value = (N % 2 == 0);
};
int main(){
static_assert(std::is_same_v<
seq_find_if<std::index_sequence<1,2,3,4>,my_predicate>::type,
std::integral_constant<size_t,2>
>);
}Reversing a TypeList and index_sequence
When typelists have some ordering among their elements, it is convenient to be able to reverse the ordering of the elements in the typelist when applying some algorithms. The reverse algorithm implements this metafunction:
template<typename List>
struct reverse;
// basis case
template<typename Head>
struct reverse<TypeList<Head>>{
using type = TypeList<Head>;
};
template<typename... Ts>
struct reverse<TypeList<Ts...>>{
using front_el = front<TypeList<Ts...>>::type;
using tail = pop_front<TypeList<Ts...>>::type;
using type = push_back<front_el, typename reverse<tail>::type>::type;
};template<typename IndexSequence>
struct seq_reverse;
template<size_t Head>
struct seq_reverse<std::index_sequence<Head>>{
using type = std::index_sequence<Head>;
static constexpr auto value = std::index_sequence<Head>{};
};
template<size_t Head, size_t... Tail>
struct seq_reverse<std::index_sequence<Head,Tail...>>{
using type = seq_push_back<Head,typename seq_reverse<std::index_sequence<Tail...>>::type>::type;
};Implementing transform
template<template <size_t I> typename Func, typename IndexSequence>
struct seq_transform;
template<template <size_t I> typename Func, size_t First>
struct seq_transform<Func, std::index_sequence<First>>{
using type=std::index_sequence<Func<First>::value>;
};
template<template <size_t I> typename Func, size_t... Is>
struct seq_transform<Func, std::index_sequence<Is...>>{
static constexpr size_t front_el = seq_front<std::index_sequence<Is...>>::value;
using tail = seq_pop_front<std::index_sequence<Is...>>::type;
using type = seq_push_front<Func<front_el>::value, typename seq_transform<Func,tail>::type>::type;
};Remove duplicates
Assume that we a sorted integer sequence such as \(1, 2, 2, 2, 4, 4, 5, \ldots\). We are interested to write a function seq_uniq that will remove duplicates from the sequence.
template<typename List>
struct seq_uniq;
template<size_t I>
struct seq_uniq<std::index_sequence<I>>{
using type = std::index_sequence<I>;
};
template<size_t I1, size_t I2>
struct seq_uniq<std::index_sequence<I1, I2>>{
using type = std::conditional<
(I1 == I2),
std::index_sequence<I1>,
std::index_sequence<I1, I2>
>::type;
};
template<size_t First, size_t... Rest>
struct seq_uniq<std::index_sequence<First,Rest...>>{
static constexpr size_t first = First;
static constexpr size_t next = seq_front<std::index_sequence<Rest...>>::value;
using tail = std::index_sequence<Rest...>;
using tail_next = seq_pop_front<std::index_sequence<Rest...>>::type;
using type = std::conditional<
(first == next),
typename seq_uniq<typename seq_push_front<First, tail_next>::type>::type,
typename seq_push_front<First, typename seq_uniq<tail>::type>::type
>::type;
};Implementing Merge Sort
We can write a cool metafunction to implement merge sort. I’d encourage you to try this as a challenge. Let’s see what you’ve got!
template<typename V>
struct MergeSort{
using type = typename MergeVecs<
typename MergeSort<typename SplitVec<V>::left>::type,
typename MergeSort<typename SplitVec<V>::right>::type
>::type;
};
int main(){
static_assert(
std::is_same_v<
MergeSort<Vec<2, 4, 1, 5, 7, 9, 4, 5>>::type,
Vec<1, 2, 4, 4, 5, 5, 7, 9>
>
);
}Here’s my implementation of merge-sort:
template<size_t... Is>
using Vec = std::index_sequence<Is...>;
template<typename List, typename Indexer>
struct SelectVec;
template<size_t... Is, size_t... Js>
struct SelectVec<std::index_sequence<Is...>, std::index_sequence<Js...>>{
using type = std::index_sequence<seq_nth_element<Is,typename std::index_sequence<Js...>>::value...>;
};
template<size_t Start,typename List, typename Indexer>
struct VecSliceHelper;
template<size_t Start, size_t... Is, size_t... Js>
struct VecSliceHelper<Start, std::index_sequence<Is...>, std::index_sequence<Js...>>{
using type = std::index_sequence<seq_nth_element<Start + Js,typename std::index_sequence<Is...>>::value...>;
};
template<size_t Start, size_t End, typename V>
struct VecSlice;
template<size_t Start, size_t End, size_t... Is>
struct VecSlice<Start, End, Vec<Is...>>{
static constexpr size_t num_elements = End - Start + 1;
using s = std::make_index_sequence<num_elements>;
using type = VecSliceHelper<Start, Vec<Is...>, s>::type;
};
template<typename V>
struct SplitVec;
template<size_t I1, size_t I2>
struct SplitVec<Vec<I1, I2>>{
using left = Vec<I1>;
using right = Vec<I2>;
};
template<size_t... Is>
struct SplitVec<Vec<Is...>>{
static constexpr size_t N = sizeof...(Is);
static constexpr size_t mid = N / 2;
using left = VecSlice<1,mid,Vec<Is...>>::type;
using right = VecSlice<mid+1,N,Vec<Is...>>::type;
};
template<typename Vec1, typename Vec2, typename Result >
struct MergeHelper;
// Base cases
template<size_t... I>
struct MergeHelper<Vec<>, Vec<>, Vec<I...>>{
using type = Vec<I...>;
};
// When no elements remain in right subarray
template<size_t... I1, size_t... I>
struct MergeHelper<Vec<I1...>, Vec<>, Vec<I...>>{
static constexpr size_t element = seq_front<Vec<I1...>>::value;
using tail = seq_pop_front<Vec<I1...>>::type;
using result = seq_push_back<element, Vec<I...>>::type;
using type = MergeHelper<tail, Vec<>, result>::type;
};
// When no elements remain in left subarray
template<size_t... I2, size_t... I>
struct MergeHelper<Vec<>, Vec<I2...>, Vec<I...>>{
static constexpr size_t element = seq_front<Vec<I2...>>::value;
using tail = seq_pop_front<Vec<I2...>>::type;
using result = seq_push_back<element, Vec<I...>>::type;
using type = MergeHelper<tail, Vec<>, result>::type;
};
// compare the head elements of both vectors,
// pop off the smaller of the two and insert it into the results array
template<size_t... I1, size_t... I2, size_t... I>
struct MergeHelper<Vec<I1...>, Vec<I2...>, Vec<I...>>{
using left = Vec<I1...>; using right = Vec<I2...>;
using left_tail = seq_pop_front<left>::type;
using right_tail = seq_pop_front<right>::type;
using result = Vec<I...>;
static constexpr size_t p = seq_front<Vec<I1...>>::value;
static constexpr size_t q = seq_front<Vec<I2...>>::value;
using type = std::conditional<
p < q,
typename MergeHelper<left_tail, right, typename seq_push_back<p, result>::type>::type,
typename MergeHelper<left, right_tail, typename seq_push_back<q, result>::type>::type
>::type;
};
template<typename Vec1, typename Vec2>
struct Merge;
template<size_t... Is, size_t... Js>
struct Merge<Vec<Is...>,Vec<Js...>>
{
using type = MergeHelper<Vec<Is...>,Vec<Js...>,Vec<>>::type;
};
template<typename V>
struct MergeSort;
template<>
struct MergeSort<Vec<>>{
using type = Vec<>;
};
template<size_t I>
struct MergeSort<Vec<I>>{
using type = Vec<I>;
};
template<size_t... Is>
struct MergeSort<Vec<Is...>>{
using type = Merge<
typename MergeSort<typename SplitVec<Vec<Is...>>::left>::type,
typename MergeSort<typename SplitVec<Vec<Is...>>::right>::type
>::type;
};Implementing zip
Let’s say you have a bunch of compile-time vectors. We’d want to write a metafunction that takes multiple vectors and zips them with *. For example, given the input:
produce:
That is:
You can try writing your implementation using the below as a starting point:
#include <type_traits>
#include <iostream>
#include <utility>
// DEFINITION: Compile-time integer vector defined as:
template<int... I>
struct Vector;
// The code below will assume a 'zip' metafunction is used, but feel free to use a different approach.
// If you do, please adjust the static assert accordingly.
int main(){
static_assert(std::is_same<
zip<Vector<1, 2, 3>, Vector<4, 5, 6>, Vector<7, 8, 9>>::type,
Vector<1*4*7,2*5*8,3*6*9>>::value, "");
}Put on your thinking cap and happy coding! When you’re done with your attempt, you can take a look below at my solution:
#include <type_traits>
#include <iostream>
#include <utility>
// DEFINITION: Compile-time integer vector defined as:
template<int... I>
struct Vector;
// The code below will assume a 'zip' metafunction is used, but feel free to use a different approach.
// If you do, please adjust the static assert accordingly.
// A getter for the nth-element of the compile-time sequence
// of integers
template<size_t N, typename List>
struct get;
// Base case
template<int Head, int... Tail>
struct get<0, Vector<Head,Tail...>>{
static constexpr auto value = Head;
};
// get<N,Vector<I1,I2,...>> inherits from get<N-1,Vector<I2,...>>
template<size_t N, int Head, int... Tail>
struct get<N, Vector<Head,Tail...>> : get<N-1,Vector<Tail...>>{};
template<int... I>
struct front{
static constexpr auto value = get<0, Vector<I...>>::value;
};
template<typename List>
struct pop_front;
template<int I, int... Is>
struct pop_front<Vector<I,Is...>>{
using type = Vector<Is...>;
};
// Let's design a metafunction zip that accepts a variadic pack
// of Vector's.
// Template declaration
template<typename... Vectors>
struct zip;
// Partial specialization
template<int... Is>
struct zip<Vector<Is...>>{
using type = Vector<Is...>;
};
template<typename Indexes, typename V, typename... List>
struct zip_impl;
template<size_t... Is, int... Elements>
struct zip_impl<std::index_sequence<Is...>, Vector<Elements...>>{
using type = Vector<Elements...>;
};
template<size_t... Is, int... Elements, typename... Vectors>
struct zip_impl<std::index_sequence<Is...>,Vector<Elements...>, Vectors...>{
using first = Vector<Elements...>;
using rest = typename zip_impl<std::index_sequence<Is...>, Vectors...>::type;
using type = Vector<(get<Is, first>::value * get<Is, rest>::value)...>;
};
template<int... Is, typename... Vectors>
struct zip<Vector<Is...>, Vectors...>{
static constexpr size_t N = sizeof...(Is);
using seq = std::make_index_sequence<N>;
using type = zip_impl<seq,Vector<Is...>,Vectors...>::type;
};
// TEST
int main() {
// Test case #1
static_assert(get<0,Vector<1,2,3>>::value == 1);
static_assert(std::is_same<
zip<Vector<1, 2, 3>, Vector<4, 5, 6>, Vector<7, 8, 9>>::type,
Vector<1*4*7,2*5*8,3*6*9>>::value, "");
// TASK: Add more test cases here
// TASK: Ensure it compiles before submission
return 0;
}Basic std::tuple design
A tuple is an arbitrary collection of heterogenous data. It is a recursive data-structure. A tuple has a static component and a run-time component. The list of types are baked into the tuple definition at compile-time. The actual values/objects held by the tuple can be objects known at run-time.
We will design a tuple class template. Implementing your own version tuple type is a good exercise to flex your metaprogramming muscles.
#include <utility>
#include <memory>
#include <format>
#include <iostream>
#include <cassert>
namespace dev
{
// TypeList definition
template<typename... Ts>
struct TypeList{
using type = TypeList<Ts...>;
static constexpr auto value = TypeList<Ts...>{};
};
// TypeList Indexing
template<size_t I, typename List>
struct nth_element;
template<typename First, typename... Rest>
struct nth_element<1,TypeList<First, Rest...>>{
using type = First;
};
template<size_t N, typename First, typename... Rest>
struct nth_element<N, TypeList<First, Rest...>> : nth_element<N-1, TypeList<Rest...>>{};
// Implement tuple. This is a forward declaration.
template <typename... Types>
class tuple;
// Base case
template <>
class tuple<> { };
template<typename Head, typename... Tail>
requires std::is_trivially_default_constructible_v<Head>
class tuple<Head, Tail...>{
using type = TypeList<Head, Tail...>;
private:
Head m_head;
tuple<Tail...> m_tail;
public:
tuple()
: m_head{}
, m_tail{}
{}
tuple(Head head, Tail... tail)
: m_head{head}
, m_tail{tail...}
{}
Head head() const{
return m_head;
}
tuple<Tail...> tail() const{
return m_tail;
}
constexpr auto empty(){
return std::tuple<>();
}
constexpr auto initialize(Head head, Tail... tail){
m_head = head;
if constexpr(sizeof...(Tail))
m_tail.initialize(tail...);
}
};
// Implement get
template <unsigned N, typename... Types>
auto get(const tuple<Types...>& tuple) {
if constexpr(N == 0)
return tuple.head();
else
return get<N-1>(tuple.tail());
}
}
int main(){
dev::tuple<int> tup;
assert(get<0>(tup) == 0);
}Tuple Algorithms
Implementing transform for a std::tuple{t1,t2,...,tn}
template<typename TupleT, typename Func, size_t... Is>
constexpr auto transform_impl(TupleT tup, Func func, std::index_sequence<Is...> indexes){
return std::make_tuple(func(std::get<Is>(tup))...);
}
// transform
template<typename TupleT, typename Fn>
constexpr auto transform(Fn func, TupleT tup)
{
constexpr auto index_seq = std::make_index_sequence<std::tuple_size_v<TupleT>>{};
return transform_impl(tup, func, index_seq);
}Implementing select_tuple for a std::tuple{t1,...,tn}
Reversing a tuple
template<typename TupleT, size_t... Is>
constexpr auto reverse_tuple_impl(TupleT tuple, std::index_sequence<Is...> idx_seq){
constexpr auto rev_idx_seq = seq_reverse<std::index_sequence<Is...>>::value;
return select_tuple(tuple, rev_idx_seq);
}
template<typename TupleT>
constexpr auto reverse_tuple(TupleT tuple){
constexpr std::index_sequence idx_sequence = std::make_index_sequence<std::tuple_size_v<TupleT>>{};
return reverse_tuple_impl(tuple, idx_sequence);
}Implementing tuple concatenation
template<typename TupleT1, typename TupleT2, size_t... I1s, size_t... I2s>
constexpr auto cat_tuple_impl(TupleT1 tuple1, TupleT2 tuple2, std::index_sequence<I1s...> seq1, std::index_sequence<I2s...> seq2){
return std::make_tuple(std::get<I1s>(tuple1)...,std::get<I2s>(tuple2)...);
}
template<typename TupleT1, typename TupleT2>
constexpr auto cat_tuple(TupleT1 t1, TupleT2 t2)
{
constexpr std::index_sequence seq1 = std::make_index_sequence<std::tuple_size_v<TupleT1>>{};
constexpr std::index_sequence seq2 = std::make_index_sequence<std::tuple_size_v<TupleT2>>{};
return cat_tuple_impl(t1, t2, seq1, seq2);
}Implementing zip for a pair of tuples
template<typename TupleT1, typename TupleT2, size_t... I1s, size_t... I2s>
constexpr auto zip_tuple_impl(TupleT1 tuple1, TupleT2 tuple2, std::index_sequence<I1s...> seq1, std::index_sequence<I2s...> seq2){
return std::make_tuple(std::make_tuple(std::get<I1s>(tuple1), std::get<I2s>(tuple2))...);
}
template<typename TupleT1, typename TupleT2>
constexpr auto zip_tuple(TupleT1 t1, TupleT2 t2){
constexpr std::index_sequence seq1 = std::make_index_sequence<std::tuple_size_v<TupleT1>>{};
constexpr std::index_sequence seq2 = std::make_index_sequence<std::tuple_size_v<TupleT2>>{};
return zip_tuple_impl(t1, t2, seq1, seq2);
}