Recursive 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.

constexpr std::index_seq seq = std::make_index_sequence<1,2,3,4,5>{};

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);
}

Compiler Explorer

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...>{};
};

Compiler Explorer

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...>>{};

Compiler Explorer

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>
    >);
}

Compiler Explorer

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;
};

Compiler Explorer

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;
};

Compiler Explorer

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;
};

Compiler Explorer

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;
};

Compiler Explorer

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;
};

Compiler Explorer

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:

Vector<1,2,3>, Vector<4,5,6>, Vector<7,8,9>

produce:

Vector<28,80,162>

That is:

Vector<1*4*7, 2*5*8, 3*6*9>

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;
}

Compiler Explorer

Recursive Template Metaprogramming

Typelists and std::index_sequence

Implementing a TypeList

Manipulating TypeList and index_sequence

Implementing pop_front

Implementing push_front

Implementing push_back

Typelist algorithms

Indexing

Implementing find_if

Reversing a TypeList and index_sequence

Implementing transform

Remove duplicates

Implementing Merge Sort

Implementing zip

Typelists and `std::index_sequence`

Implementing a `TypeList`

Manipulating `TypeList` and `index_sequence`

Implementing `pop_front`

Implementing `push_front`

Implementing `push_back`

Implementing `find_if`

Reversing a `TypeList` and `index_sequence`

Implementing `transform`

Implementing `zip`