Fundamental operations on type lists (Part1)

A couple of thoughts are borrowed from Peter Dimov’s “Simple C++11 metaprogramming” articles. Make sure to check them out! ¹

Type lists and metafunctions

One of the fundamental building blocks of template metaprogramming is type lists. Dealing with them used to be a hassle, but since C++11 they are pretty much built into the language through type template parameter packs. Hence, it’s quite easy to define one:

template <typename...>
struct list; // actually, you don't even have to define it unless you're about to ODR-use it

Another building block is metafunctions. A metafunction used to be defined as a class template that represents a function, invocable at compile-time, the result of which can be accessed via a nested typedef called type, e.g.:

template <typename T>
struct add_const {
    typedef T const type;
};

Alias templates

Since the introduction of C++11’s alias template, a metafunction invocation can have a more terse, yet clean form. Namely, if you introduce an alias template for forwarding to your class template:

template <typename T>
using add_const_t = typename add_const<T>::type;

then you can declare a type alias simply like this:

using int_const = add_const_t<int>;
using T_const = add_const_t<T>; // T is a template parameter

You may now get rid of typedefs along with typedef’s somewhat unnatural syntax:

typedef add_const<int>::type int_const;
typedef typename add_const<T>::type T_const; // T is a template parameter

In fact, you might well want to save a template instantiation, remove the class template and use an alias template on its own:

template <typename T>
using add_const = T const;

using int_const = add_const<int>;
using T_const = add_const<T>; // T is a template parameter

As you can see, alias templates save you from having to deal with the typename disambiguator as well.

I don’t know about you, but to me alias templates fit so much better as metafunctions than their class template metafunction counterparts, although there’s a catch (or two)…

Alias template limitations (`first<>`, `front<>`)

Suppose we’d like to write a metafunction that returns the first element from a template parameter pack. Using an alias template to get the job done seems reasonable:

template <typename T, typename...>
using first = T;

Looks good, right? It even works:

static_assert(std::is_same_v<first<int, char, double>, int>);

Now, what if we’d like to use it, say, in a metafunction that returns the first element from a type list? Let’s call it front<>:

1
2
3
4
5
6
7
8
9
10
11
12
13
// primary template
template <typename>
struct front_impl;

// partial specialization
template <template <typename...> typename L, typename... Ts>
struct front_impl<L<Ts...>> {
    using type = first<Ts...>;
};

// alias template
template <typename L>
using front = typename front_impl<L>::type;

Here we utilize the fact that we don’t necessarily have to (partially) specialize front_impl<> for a specific type list. In this way it can take any variadic class template from std::tuple<> right through to the one that we’ve just defined. Anyhow, I bet you would expect the above to compile; it won’t, however. Not that it ought not to work, it’s just that an ongoing C++ core language issue kicks in:

C++ Standard Core Language Active Issues, Revision 100
“Originally, a pack expansion could not expand into a fixed-length template parameter list, but this was changed in N2555. This works fine for most templates, but causes issues with alias templates.” CWG 1430

If we could invoke first<> in a way we don’t have to write out first<Ts...>, then front<>’s implementation would be fine. Actually, we can achieve this with a class template that takes a metafunction and a template parameter pack to call that metafunction with. I’m going to call it defer<>:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <template <typename...> typename F, typename... Ps>
struct defer {
    using type = F<Ps...>;
};

template <typename>
struct front_impl;

template <template <typename...> typename L, typename... Ts>
struct front_impl<L<Ts...>> {
    using type = typename defer<first, Ts...>::type;
};

template <typename L>
using front = typename front_impl<L>::type;

Although deferring the invocation of first<> with defer<> works, it doesn’t mean we should be satisfied. On the one hand, front<>’s implementation is clearly redundant. On the other hand, using first<> would get unwieldy in no time since we would need to use defer<> everywhere we’d like a pack expansion to expand into its template parameter list.

Did you just see that in line 11 by the way? We’ve just passed an alias template (first<>) to a template template parameter (F<>). How cool is that?!

17.3.3 Template template arguments
[temp.arg.template]
¹ “A template-argument for a template template-parameter shall be the name of a class template or an alias template, expressed as id-expression.” ISO/IEC 14882:2017 (draft)

Alright, back to front<>… Let’s try approaching this the other way around: we implement front<> first, then reduce first<> to front<>. We could try implementing it as an alias template, which would look something like this:

template <typename>
using front;

template <template <typename...> typename L, typename T, typename... Ts>
using front<L<T, Ts...>> = T; // or whatever syntax alias template partial specialization would have, provided it existed

Although the above code snippet might look like C++, it’s certainly not. Alias templates cannot be specialized (as opposed to class templates):

17.5 Template declarations
[temp.decls]
³ “Because an alias-declaration cannot declare a template-id, it is not possible to partially or explicitly specialize an alias template.” ISO/IEC 14882:2017 (draft)

On to front<>’s final implementation with a class template:

1
2
3
4
5
6
7
8
9
10
template <typename>
struct front_impl;

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

template <typename L>
using front = typename front_impl<L>::type;

The structure above is quite common, by the way: you implement your metafunction as a class template (mostly in its partial specialization) and invoke it from an alias template.

Now you can use front<> like this:

static_assert(std::is_same_v<front<list<int, char, double>>, int>);

Implementing first<> in terms of front<> is fairly simple; we just need to wrap a type list around the parameter pack and pass it to front<>:

template <typename... Ts>
using first = front<list<Ts...>>;

If we were to write a self-contained implementation of first<>, it would involve expanding a pack expansion into first_impl<>’s template parameter list, which would indeed have a non-variadic template parameter:

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

template <typename... Ts>
using first = typename first_impl<Ts...>::type;

This time, however, CWG 1430 would not get in the way as it doesn’t apply to class templates.

That’s that! Undoubtedly, not the most useful metafunctions one can come across, but they’re suitable for getting some basic stuff straight.

Let’s move on to the next metafunction pair, shall we?

`last<>`, `back<>`

Generally, compile-time complexity is measured in terms of the number of template instantiations required. Both first<> and front<> have constant complexity; therefore it’d be nice if we could come up with a solution to last<> and back<> with a complexity similar to theirs.

We could try writing an alias template, but then we’d be facing alias template’s specialization limitation again. Skipping to the class template solution:

1
2
3
4
5
6
7
8
9
10
template <typename...>
struct last_impl;

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

template <typename... Ts>
using last = typename last_impl<Ts...>::type;

Again, looks right, feels right, does not compile. That’s because a couple of restrictions apply to class template partial specializations, unfortunately:

17.5.5 Class template partial specializations
[temp.class.spec]
^8.4 “If an argument is a pack expansion (17.5.3), it shall be the last argument in the template argument list.” ISO/IEC 14882:2017 (draft)

Maybe it’s time to relax our complexity requirement to linear? Well, not necessarily (provided your compiler supports C++17 properly), but we sure could give a linear-complexity solution as well, should we want to:

1
2
3
4
5
6
7
8
9
10
11
12
template <typename, typename... Ts>
struct last_impl {
    using type = typename last_impl<Ts...>::type;
};

template <typename T>
struct last_impl<T> {
    using type = T;
};

template <typename... Ts>
using last = typename last_impl<Ts...>::type;

This is a pretty straightforward recursive implementation. The primary template recursively pops off the first element of the parameter pack until there’s only one, the case of which is taken care of by the partial specialization.

Until C++17 (without fold expressions, in particular) there hadn’t been any solutions that were guaranteed to have \(O(1)\) complexity (at least not that I know of). With a fold expression however, one that reduces its parameter pack over the comma operator, we can do much better:

template <typename T>
struct identity {
    using type = T;
};

template <typename... Ts>
using last = typename decltype((..., identity<Ts>{}))::type;

The comma operator is no surprise, I suppose, but why on earth do we have to use identity<>? Let’s stick with the version not using identity<> for now:

template <typename... Ts>
using last = decltype((..., Ts{}));

The problem is that with this we would impose a requirement on the types we’d like to use last<> with, namely for any type T the expression T{} must be valid. From here it’s quite self-explanatory: “lvalue-reference-to-non-consts” or abstract classes are out, as well as those types with a private default constructor or with no default constructor at all.

An interesting, but not particularly delightful fact: suppose we have a class, A with a user-provided private constructor (mind the underlined part as it’s going to make a big difference):

class A {
    A() {}
};

11.4.2 Explicitly-defaulted functions
[dcl.fct.def.default]
⁵ “A function is user-provided if it is user-declared and not explicitly defaulted or deleted on its first declaration.” ISO/IEC 14882:2017 (draft)

Now this, for example:

template <typename T>
using self = decltype(T{});

static_assert(std::is_same_v<self<A>, A>);

is not going to compile because A’s constructor is inaccessible; thus neither would e.g. last<A> compile and that’s perfectly understandable. ² What’s awkward about this whole thing is that if you explicitly default A’s constructor as in

class A {
    A() = default;
};

then unexpectedly both self<> and last<> start to work, just as if A’s constructor was not declared private. Surprise! You’ve just turned A into an aggregate (since A’s constructor is now explicitly defaulted):

11.6.1 Aggregates
[dcl.init.aggr]
¹ “An aggregate is an array or a class (Clause 12) with
^(1.1) — no user-provided, explicit, or inherited constructors (15.1), …” ISO/IEC 14882:2017 (draft)

The above is not the only reason to use identity<>, by the way (which you’ll be able to replace with std::type_identity<> in C++20). I’ll get into other use-cases in future posts.

Finally, the reduction of back<> to last<> (the one that uses identity<>) is a cake-walk:

1
2
3
4
5
6
7
8
9
10
template <typename>
struct back_impl;

template <template <typename...> typename L, typename... Ts>
struct back_impl<L<Ts...>> {
    using type = last<Ts...>;
};

template <typename L>
using back = typename back_impl<L>::type;

Note that again, we didn’t have to deal with CWG 1430, this time because of last<>’s template parameter list not having non-variadic template parameters.

`apply<>`

Couldn’t we come up with a less verbose method for reducing back<> to last<>? It turns out that we very much could. Metaprogramming libraries generally have a primitive called apply<> that is worth introducing as it proves to be very handy in many situations, including this one. Here’s how it goes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <template <typename...> typename, typename>
struct apply_impl;

template <
    template <typename...> typename F,
    template <typename...> typename L,
    typename... Ts
>
struct apply_impl<F, L<Ts...>> {
    using type = F<Ts...>;
};

template <template <typename...> typename F, typename L>
using apply = typename apply_impl<F, L>::type;

Provided you pass an alias template to F<>, apply<> is equivalent to calling it with L<>’s parameter pack, and it does so by actually renaming the template-name around L<>’s parameter pack to F. With the help of apply<>, back<> can even be turned into a one-liner:

1
template <typename L> using back = apply<last, L>;

Pretty cool, isn’t it?

Conclusion

This post is intended to:

lay down basic concepts of C++ template metaprogramming, such as type lists and metafunctions,
elaborate on alias templates and their limitations,
present different approaches to implementing four fundamental metafunctions: first<>, front<>, last<> and back<>,
introduce a common metaprogramming primitive: apply<>.

Download source

Peter Dimov – Simple C++11 metaprogramming: Part1, Part2 ↩
At the time of this writing, MSVC (Version 16.4.5) does compile the aforementioned, but I don’t think this will remain for too long, as I’ve just filed a bug report on this issue and they work pretty fast. ↩

Type lists and metafunctions

Alias templates

Alias template limitations (first<>, front<>)

last<>, back<>

apply<>

Conclusion

Alias template limitations (`first<>`, `front<>`)

`last<>`, `back<>`

`apply<>`