Concatenating lists using template metaprogramming in C++11

user_8808491 0
Viewed 160

I've created a new type called IntList, which represents a list of integers. This was made by using templates:

template<int...>
struct IntList;

template<int h, int... t>
struct IntList<h, t...>{
    constexpr static int head = h;
    typedef IntList<t...> next;
    constexpr static int size = sizeof...(t) + 1;
    constexpr static bool empty = false;
};

template<>
struct IntList<>{
    constexpr static int size = 0;
    constexpr static bool empty = true;
};

For example, IntList<1,2,3,4> is a list of 4 elements - 1,2,3,4.

IntList<1,2,3,4>::head; //Should be 1
IntList<1,2,3,4>::size; //Should be 4
IntList<1,2,3,4>::next; //Should be IntList<2,3,4>

Now, I want to use templates to create a new type which concatenates these type of lists. It will be called ConcatedIntLists. If I need to concatenate only two lists, then it is pretty simple:

template<typename...>
struct ConcatedIntLists;

template<int...T1, int...T2>
struct ConcatedIntLists<IntList<T1...>, IntList<T2...>>{
    typedef IntList<T1..., T2...> list;
};

But what if I want to concatenate unknown number of lists? For example:

ConcatedIntLists<IntList<1,2,3>, IntList<>, IntList<4,5>>::list; //Should be IntList<1,2,3,4,5>
ConcatedIntLists<IntList<1>, IntList<2>, IntList<3>, IntList<4>>::list; //Should be IntList<1,2,3,4>

This is the part I got stuck in.

template-meta-programming c++11 templates c++
3 Answers

This solution was an improvement to my original solution, suggested by Jarod42 in the comments.

You can write this template recursively:

template<typename ...T>
struct ConcatedIntLists;  // just to allow specializations
                          // for base case, and general case 

template<typename T>
struct ConcatedIntLists<T> 
{
    using list = T;             // base case: just a list
};

// for 2 or more lists
template<int...T1, int...T2, typename ...CRest>
struct ConcatedIntLists<IntList<T1...>, IntList<T2...>, CRest...>    
{
    using list = typename ConcatedIntLists<IntList<T1..., T2...> , CRest...>::list;
                                       //  ^concatenate first two, ^and the rest      
}

Here's a demo

Note that this solution uses using syntax instead of typedef syntax, because it's much cleaner to read.

user_83728530

You might add this extra specialization:

template<int...T1, typename...Ts>
struct ConcatedIntLists<IntList<T1...>, Ts...> {
    typedef typename ConcatedIntLists<IntList<T1...>,
                                      typename ConcatedIntLists<Ts...>::list>::list list;
};

Demo.

user_84917260

These kind of things can be solved using a left fold over a list of types. As we can't iterate over a variadic template parameter pack, we need to resort to recursion. The code might be a bit overwhelming if you are not used to template metaprogramming, so I've put a couple of explanatory comments into the code example.

// This is the functor we want to fold the elements over.
// It simply concatenates two IntLists.
template<typename L1, typename L2>
struct ConcateIntListsFunctor;

// The actual functor is a so called meta function, it's arguments
// are the template parameters in the primary template. 
template<int...T1, int...T2>...
struct ConcateIntListsFunctor<IntList<T1...>, IntList<T2...>>{
    // ... and we "call" it by retrieving it's "type" typedef.
    typedef IntList<T1..., T2...> type;
};


template<template<typename, typename> class, typename...>
struct LeftFold;

// The LeftFold is a meta-function that takes a binary meta-function as first parameter, a State and a list of types we want to fold over.
template<template<typename, typename> class Func,  typename State, typename T, typename... Ts>
struct LeftFold<Func, State, T, Ts...> {
    typedef typename Func<State, T>::type NewState; 
    // Here is where the recursion happens.
    typedef typename LeftFold<Func, NewState, Ts...>::type type;  
};

template<template<typename, typename> class Func, typename State, typename T>
struct LeftFold<Func, State, T> {
    typedef typename Func<State, T>::type type;
};

template<typename L0, typename... Ls>
struct ConcatenateIntLists {
    typedef typename LeftFold<ConcateIntListsFunctor, L0, Ls...>::type type;
};

Live example here.

user_84945880
Related