In Part1 I presented a few metafunctions that although useful to a certain extent, do not exhaust the many worthy ways of manipulating parameter packs and type lists. I’m going to cover a few of those in the following sections, along with a couple of common implementation techniques, with the help of which you can significantly simplify otherwise cumbersome tasks, while potentially reducing their compile-time overhead. Note, however, that these tricks are not silver bullets; you should always benchmark your solutions so that you can see how they compare to each other. ¹

---

push_front<>, push_back<>

Among the simplest metafunctions are push_front<> and push_back<>, since they can be easily implemented by leveraging C++11’s parameter pack expansion. Let’s just deal with push_front<> for now: for example, we’d like push_front<list<char>, int> to give us list<int, char>, which immediately implies that we’ll need a primary template with a template parameter list consisting of exactly two type parameters:

template <typename, typename>
struct push_front_impl;

As always, it’s a good idea to have an alias template forwarding to the implementation in the class template, so why not introduce it right away:

template <typename L, typename T>
using push_front = typename push_front_impl<L, T>::type;

From here we just have to fill in the gaps, that is, implement push_front_impl<>’s partial specialization for type lists (and the type to be added):

template <template <typename...> typename L, typename... Ts, typename T>
struct push_front_impl<L<Ts...>, T> {
    using type = L<T, Ts...>;
};

Adding T as the first element in L<> requires us to echo L<>’s template arguments and prepend T at the beginning.

That’s as easy as it gets, isn’t it? It’s just that you want to be able to prepend an arbitrary number of elements, right? I know, say no more!

template <typename, typename...>
struct push_front_impl;

template <template <typename...> typename L, typename... T1s, typename... T2s>
struct push_front_impl<L<T1s...>, T2s...> {
    using type = L<T2s..., T1s...>;
};

template <typename L, typename... Ts>
using push_front = typename push_front_impl<L, Ts...>::type;

This version of push_front<> is almost identical to the one prepending only one element at a time, so there is really no reason not to use parameter packs instead.

Although I’m quite sure you now have an idea of how it’s done, for the sake of completeness, here is how push_back<> could be implemented based on the solution of push_front<>:

template <typename, typename...>
struct push_back_impl;

template <template <typename...> typename L, typename... T1s, typename... T2s>
struct push_back_impl<L<T1s...>, T2s...> {
    using type = L<T1s..., T2s...>;
};

template <typename L, typename... Ts>
using push_back = typename push_back_impl<L, Ts...>::type;

Finally, you would use them like so:

static_assert(std::is_same_v<push_front<list<>, int>, list<int>>);
static_assert(std::is_same_v<push_front<std::tuple<char>, int>, std::tuple<int, char>>);
static_assert(std::is_same_v<push_front<std::variant<double>, int, char>, std::variant<int, char, double>>);

static_assert(std::is_same_v<push_back<list<>, int>, list<int>>);
static_assert(std::is_same_v<push_back<std::tuple<int>, char>, std::tuple<int, char>>);
static_assert(std::is_same_v<push_back<std::variant<int>, char, double>, std::variant<int, char, double>>);

It’s not rocket science, is it? Let’s move on to something more exciting!

---

pop_front<> and the void* trick

Next, I’m going to show you how you can make use of the void* trick, but right off the bat, I’d like to point out that using such a trick when implementing the pop_front<> metafunction is absolutely uncalled-for, since you can get its functionality in just a few lines of code by employing less cryptic methods. In fact, there are several ways to get the job done.

If you’d like to reduce pop_front<> to an alias template doing the actual work, you might go with something along these lines:

template <typename>
class pop_front_impl;

template <template <typename...> typename L, typename... T1s>
class pop_front_impl<L<T1s...>> {
    template <typename, typename... T2s>
    using tail = L<T2s...>;

public:
    using type = typename defer<tail, T1s...>::type;
};

template <typename L>
using pop_front = typename pop_front_impl<L>::type;

If you’re not familiar with the above concept, or you don’t understand why we need to use defer<> in the first place, you may want to check out the relevant parts of Part1. Anyway, the essence of this solution is tail<>, which just expands its parameter pack (T2s) into L<>, while leaving its first template parameter untouched (which, therefore, I didn’t even name).

You can actually get rid of tail<> and do exactly the same thing, right in pop_front_impl<>:

template <typename>
struct pop_front_impl;

template <template <typename...> typename L, typename T, typename... Ts>
struct pop_front_impl<L<T, Ts...>> {
    using type = L<Ts...>;
};

template <typename L>
using pop_front = typename pop_front_impl<L>::type;

The key point here is the template parameter list of pop_front_impl<>’s partial specialization having L<>’s first template argument (T) separated from the others in the parameter pack (Ts). Specifying L<T, Ts...> as pop_front_impl<>’s template argument gives us the opportunity to refer to the passed-in type list without its first element (L<Ts...>).

You could even make the alias template forward to a function template instead (see below for more information on this particular usage of decltype):

template <template <typename...> typename L, typename T, typename... Ts>
L<Ts...> pop_front_impl(L<T, Ts...>);

template <typename L>
using pop_front = decltype(pop_front_impl(L{}));

Because of L{} and pop_front_impl<>() taking its parameter by value, the above would require you to not only declare, but also to define the type list that you’re about to call pop_front<> with. Though you can get around this problem by using std::declval<>() and changing pop_front_impl<>()’s signature:

template <template <typename...> typename L, typename T, typename... Ts>
L<Ts...> pop_front_impl(L<T, Ts...> const&);

template <typename L>
using pop_front = decltype(pop_front_impl(std::declval<L>()));

std::declval<L>() converts L to L&& (reference collapse rules apply), making it possible to use it in decltype without the need to go through its constructor and, therefore, (in our case) the need to define it.

I guess you get the idea: there are plenty of pop_front<>’s possible implementations, I’m pretty sure you could come up with your own, too.

Anyhow, here’s the one that does the trick:

template <typename>
class pop_front_impl;

template <template <typename...> typename L, typename... T1s>
class pop_front_impl<L<T1s...>> {
    template <typename... T2s>
    static L<typename T2s::type...> types(void*, T2s*...);

public:
    using type = decltype(types(static_cast<identity<T1s>*>(nullptr)...));
};

template <typename L>
using pop_front = typename pop_front_impl<L>::type;

The usual approach — exploiting pack expansion in an unusual way. Basically, we declare a variadic function template (types<>()) with a void* parameter and a function parameter pack and call it with pointer arguments. We want the first argument to get eaten by the void* parameter, so that we can build the desired type list out of the rest.

I don’t know whether you’ve come across anything like that before, but the above call to types<>() is not a traditional function call. Let’s get to the nuts and bolts:

8 Expressions
[expr]
“⁸ In some contexts, unevaluated operands appear (8.2.8, 8.3.3, 8.3.7, 10.1.7.2). An unevaluated operand is not evaluated. [Note: In an unevaluated operand, a non-static class member may be named (8.1) and naming of objects or functions does not, by itself, require that a definition be provided (6.2). An unevaluated operand is considered a full-expression (4.6). — end note]” ISO/IEC 14882:2017 (draft)

10.1.7.2 Simple type specifiers
[dcl.type.simple]
“^(4.5) The operand of the decltype specifier is an unevaluated operand (Clause 8).”
ISO/IEC 14882:2017 (draft)

In light of this, we cannot expect the call to types<>() to get evaluated (not even if its definition was provided), but that’s alright, since we’re only interested in its return type anyway, which is exactly what we get with:

using type = decltype(types(static_cast<identity<T1s>*>(nullptr)...));

And there it is… What’s the deal with identity<> again? Should we let go of it, we’d be left with:

using type = decltype(types(static_cast<T1s*>(nullptr)...));

Now, would pop_front<> work with arbitrary types passed to it? Of course not, and that’s because with this we would impose a requirement on the types in T1s, namely, they must be types that can be pointed-to, and as we know, e.g. references are not of this kind.

The only thing left to do is to fetch the types from the identity<>s that didn’t get eaten by the void* parameter, which is what typename T2s::type... stands for.

I can hear you complaining that you cannot pop more than one element at a time. If you were to go with one of the alternative solutions above, then that would actually be something you wouldn’t be able to achieve that easily (at least not on a general basis). Accomplishing it with the void* trick, however, is fairly straightfoward:

template <typename, typename>
class pop_front_impl;

template <template <typename...> typename L, typename... T1s, std::size_t... indices>
class pop_front_impl<L<T1s...>, std::index_sequence<indices...>> {
    template <typename... T2s>
    static L<typename T2s::type...> types(decltype(reinterpret_cast<void*>(indices))..., T2s*...);

public:
    using type = decltype(types(static_cast<identity<T1s>*>(nullptr)...));
};

template <typename L, std::size_t how_many = 1>
using pop_front = typename pop_front_impl<L, std::make_index_sequence<how_many>>::type;

That is, we:

• introduce an extra non-type (std::size_t) template parameter (how_many) in pop_front<>’s template parameter list (defaulting it to 1 for convenience)

• adjust the template parameter list of pop_front_impl<>’s primary template (adding a second type parameter)

• adjust the template parameter list and the template argument list of pop_front_impl<>’s partial specialization accordingly (non-type (std::size_t) parameter pack as a second template parameter, std::index_sequence<> ² as a second template argument)

• generate the variadic function template signature for types<>() with as many void*s as were specified in the call to pop_front<> (for the record: we don’t need the value of any of the indices created by std::make_index_sequence<>; we just need to know exactly how_many times we should “repeat” void* in the declaration)

As a result, you can use pop_front<> like this:

static_assert(std::is_same_v<pop_front<list<int, char, double>, 0>, list<int, char, double>>);
static_assert(std::is_same_v<pop_front<std::tuple<int, char, double>/*, 1*/>, std::tuple<char, double>>);
static_assert(std::is_same_v<pop_front<std::variant<int, char, double>, 2>, std::variant<double>>);

Now that was a lot more fun, wasn’t it?

---

pop_back<> and the multiple inheritance trick

In this section I’m going to demonstrate a technique for utilizing multiple inheritance in implementing the pop_back<> metafunction. Again, I’d like to stress that using a trick like that without benchmarking is not by any means recommended. As per alternative solutions, the same applies as to pop_front<>. Let’s take a look at a few recursive approaches, shall we?

We can make use of push_front<> from the first section:

template <typename>
struct pop_back_impl;

template <template <typename...> typename L, typename T>
struct pop_back_impl<L<T>> {
    using type = L<>;
};	

template <typename L>
using pop_back = typename pop_back_impl<L>::type;

template <template <typename...> typename L, typename T, typename... Ts>
struct pop_back_impl<L<T, Ts...>> {
    using type = push_front<pop_back<L<Ts...>>, T>;
};

How this works can be best conveyed by unwrapping the recursion for a simple example:

pop_back<list<int, char, double>>

push_front<
    pop_back<list<char, double>>,
    int
>

push_front<
    push_front<
        pop_back<list<double>>,
        char
    >,
    int
>

push_front<
    push_front<
        list<>,
        char
    >,
    int
>

push_front<
    list<char>,
    int
>

list<int, char>

That is, we recurse to the second partial specialization until there’s only one element in the type list, the case of which triggers the instantiation of the first partial specialization, which evaluates to an empty type list. The recursion then unwinds and unwraps until all push_front<>s are performed.

If you look carefully enough, you may realize that pop_back<>’s recursive implementation is pretty close to what a metafunction reversing a type list should look like. Actually, using push_back<> in lieu of push_front<>, along with terminating the recursion at the empty type list, yields the metafunction reverse<>:

template <typename>
struct reverse_impl;

template <template <typename...> typename L>
struct reverse_impl<L<>> {
    using type = L<>;
};	

template <typename L>
using reverse = typename reverse_impl<L>::type;

template <template <typename...> typename L, typename T, typename... Ts>
struct reverse_impl<L<T, Ts...>> {
    using type = push_back<reverse<L<Ts...>>, T>;
};

Use it like this:

static_assert(std::is_same_v<reverse<list<int>>, list<int>>);
static_assert(std::is_same_v<reverse<std::tuple<int, char>>, std::tuple<char, int>>);
static_assert(std::is_same_v<reverse<std::variant<int, char, double>>, std::variant<double, char, int>>);

Now that we have reverse<>, we could use it to reduce pop_back<> to pop_front<> (or just the other way around, depending on which one we’d like to have reduced to the other), turning it into a one-liner:

template <typename L> using pop_back = reverse<pop_front<reverse<L>>>;

Although it looks nice and gets the job done, it’s somewhat inefficient, since it performs two reverse<>s.

Anyhow, without further ado, here is the solution of pop_back<> featuring multiple inheritance:

template <std::size_t, typename T>
struct indexed_type {
    using type = T;
};

template <typename, typename...>
struct index_types;

template <std::size_t... indices, typename... Ts>
struct index_types<std::index_sequence<indices...>, Ts...>
    : indexed_type<indices, Ts>...
{};

template <typename>
class pop_back_impl;

template <template <typename...> typename L, typename... Ts>
class pop_back_impl<L<Ts...>> {
    struct indexed_types
        : index_types<std::index_sequence_for<Ts...>, Ts...>
    {};

    template <std::size_t index, typename T>
    static T type_at(indexed_type<index, T>);

    template <std::size_t... indices>
    static L<
        decltype(type_at<indices>(indexed_types{}))...
    > types(
        std::index_sequence<indices...>
    );

    static_assert(sizeof...(Ts) >= 1);
	
public:
    using type = decltype(types(std::make_index_sequence<sizeof...(Ts) - 1>{}));
};

template <typename L>
using pop_back = typename pop_back_impl<L>::type;

Seem like overkill? Absolutely. But let’s just focus on the trick itself for now!

The pop_back<> alias template forwarding to the pop_back_impl<> class template is no longer a surprise, I suppose, but what about the extra structs and function templates? The basic idea behind them is the utilization of multiple inheritance and a related template argument deduction rule:

17.8.2.1 Deducing template arguments from a function call
[temp.deduct.call]
“^(4.3) — If P is a class and P has the form simple-template-id, then the transformed A can be a derived class of the deduced A. Likewise, if P is a pointer to a class of the form simple-template-id, the transformed A can be a pointer to a derived class pointed to by the deduced A.” ISO/IEC 14882:2017 (draft)

In other words, this works as you’d expect:

template <typename>
struct Base {};

struct Derived
    : Base<int>
{};

template <typename T>
void f(Base<T>) {}

f(Derived{});

since P = Base<T> (a simple-template-id), transformed A = Derived, deduced A = Base<int> and Derived is indeed a derived class of Base<int>. You’ve probably heard of (object) slicing, but in this case it’s not something we should be worried about, as not only do these classes not have virtual functions, but they even lack a (real) layout, in general.

Likewise, this works, too:

template <std::size_t, typename>
struct Base {};

struct Derived
    : Base<0, int>
    , Base<1, char>
    , Base<2, double>
{};

template <std::size_t index, typename T>
void f(Base<index, T>) {}

f<0>(Derived{}); // P = Base<index, T>, transformed A = Derived, deduced A = Base<0, int>,    std::is_base_of_v<Base<0, int>, Derived>    == true
f<1>(Derived{}); // P = Base<index, T>, transformed A = Derived, deduced A = Base<1, char>,   std::is_base_of_v<Base<1, char>, Derived>   == true
f<2>(Derived{}); // P = Base<index, T>, transformed A = Derived, deduced A = Base<2, double>, std::is_base_of_v<Base<2, double>, Derived> == true

Since we’re calling f<>() with a fixed index, we’re not leaving too many candidates for the compiler to consider; it’s going to deduce Base<0, int>, Base<1, char> and Base<2, double>, respectively, as there are no other matches.

As you can see, things match up with the example above: indexed_type plays the role of Base and indexed_types plays the role of Derived, whereas index_types pretty much does the obvious: it indexes the types by inheriting from them via indexed_type (from indexed_type<0, T1> up to indexed_type<N - 1, TN>).

Thus, the trick lies within calling type_at<>() with a fixed index, while passing indexed_types{} as argument:

// let N be sizeof...(Ts)
decltype(type_at<0>(indexed_types{})), ..., decltype(type_at<N - 2>(indexed_types{}))

Now, since in

decltype(types(std::make_index_sequence<sizeof...(Ts) - 1>{}))

std::make_index_sequence<sizeof...(Ts) - 1> generates one less index than L<> has template arguments, we end up fetching the types at the indices from 0 to N - 2 (which is exactly what we wanted).

Two things worth mentioning here:

1. The above solution of pop_back<> is not going to compile under MSVC, at least not with the current latest version (Version 16.5.1). ³ A fix for the issue is being prepared for release, but for the time being, you’ll need to get around it:

template <std::size_t index, typename T>
static indexed_type<index, T> type_at(indexed_type<index, T>);

template <std::size_t... indices>
static L<
    typename decltype(type_at<indices>(indexed_types{}))::type...
> types(
    std::index_sequence<indices...>
);

2. Though we’re performing compile-time assertion checking for Ts, still in the unfortunate event of calling pop_back<> with an empty type list, strange things are about to happen: MSVC although issues a compile-time error, yet it gets busy generating the indices up to static_cast<std::size_t>(-1) (and runs out of heap space eventually). ⁴ Fortunately, there’s a platform-independent workaround for that, too (although not at all fancy). We modify pop_back_impl<>’s partial specialization in such a way that it no longer remains a candidate when calling pop_back<> with an empty type list:

template <template <typename...> typename L, typename T1, typename... Ts>
class pop_back_impl<L<T1, Ts...>> { // at least one template argument is required for L<>
    struct indexed_types
        : index_types<std::index_sequence_for<T1, Ts...>, T1, Ts...>
    {};

    template <std::size_t index, typename T>
    static indexed_type<index, T> type_at(indexed_type<index, T>);

    template <std::size_t... indices>
    static L<
        typename decltype(type_at<indices>(indexed_types{}))::type...
    > types(
        std::index_sequence<indices...>
    );

public:
    using type = decltype(types(std::index_sequence_for<Ts...>{}));
};

One final twist: none of the versions of pop_back<> using multiple inheritance are suitable for popping multiple elements at a time, but we sure can come up with an approach similar to what we used in pop_front<>:

template <typename, std::size_t>
class pop_back_impl;

template <template <typename...> typename L, typename... Ts, std::size_t how_many>
class pop_back_impl<L<Ts...>, how_many> {
    struct indexed_types
        : index_types<std::index_sequence_for<Ts...>, Ts...>
    {};

    template <std::size_t index, typename T>
    static indexed_type<index, T> type_at(indexed_type<index, T>);

    template <std::size_t... indices>
    static L<
        typename decltype(type_at<indices>(indexed_types{}))::type...
    > types(
        std::index_sequence<indices...>
    );

    static_assert(sizeof...(Ts) >= how_many);

public:
    using type = decltype(types(std::make_index_sequence<sizeof...(Ts) - how_many>{}));
};

template <typename L, std::size_t how_many = 1>
using pop_back = typename pop_back_impl<L, how_many>::type;

You can use it like so:

static_assert(std::is_same_v<pop_back<list<int, char, double>, 0>, list<int, char, double>>);
static_assert(std::is_same_v<pop_back<std::tuple<int, char, double>/*, 1*/>, std::tuple<int, char>>);
static_assert(std::is_same_v<pop_back<std::variant<int, char, double>, 2>, std::variant<int>>);

That’s it in a nutshell!

---

---

Conclusion

Although using the void* trick or the multiple inheritance trick is a little elaborate when implementing otherwise straightforward metafunctions, they have their real-world use-cases as well. For example, take a look at how in Louis’ article ¹ they compare to each other when used in implementing the at<> metafunction (or how he calls it, nth_element<>).

In this post I:

• presented simple implementations of push_front<> and push_back<>,
• introduced several alternatives on how to implement pop_front<>,
• outlined the void* trick and elaborated on how to use it in implementing pop_front<>,
• presented recursive approaches (including reverse<>) to implementing pop_back<>,
• outlined the multiple inheritance trick and showed how it can be utilized when implementing pop_back<>.

Hope you now have a better grasp of what can really be accomplished with template metaprogramming!

---

Download source

1. You might also want to check out the author of Boost.Hana elaborating on these techniques from the perspective of indexing parameter packs: Louis Dionne – Efficient parameter pack indexing ↩ ↩²

2. std::index_sequence<> and std::integer_sequence<> in general are beyond the scope of this article, but I’ll get to them, eventually. ↩

3. Bug report: decltype and “no parameter packs available to expand” ↩

4. Bug report: Although the compilation fails with error C2338, the build still hangs. ↩