Expanding with pack of templates

Question

Define template_pack as in the following example. Given

template <typename> struct A;
template <typename, typename, typename> struct B;
template <typename, typename> struct C;

then

template_pack<std::tuple<char, bool, double>, A, B, C>::type

is to be

std::tuple<A<char>, B<char, bool, double>, C<char, bool>>

i.e. always reading from left to right in the tuple, so as to get enough types to fit each template.

Here's my solution so far. But it only works for templates that take up to 3 types, and I don't see how I can generalize to templates of any number of types:

#include <type_traits>
#include <tuple>

template <template <typename...> class Template, typename... Ts> struct use_template;

template <template <typename> class Template, typename A, typename... Rest>
struct use_template<Template, A, Rest...> {
    using type = Template<A>;
};

template <template <typename, typename> class Template, typename A, typename B, typename... Rest>
struct use_template<Template, A, B, Rest...> {
    using type = Template<A,B>;
};

template <template <typename, typename, typename> class Template, typename A, typename B, typename C, typename... Rest>
struct use_template<Template, A, B, C, Rest...> {
    using type = Template<A,B,C>;
};

template <typename Pack, template <typename...> class... Templates> struct template_pack;

template <template <typename...> class P, typename... Ts, template <typename...> class... Templates>
struct template_pack<P<Ts...>, Templates...> {
    using type = P<typename use_template<Templates, Ts...>::type...>;
};

// Testing
template <typename> struct A;
template <typename, typename, typename> struct B;
template <typename, typename> struct C;

int main() {
    static_assert (std::is_same<
        template_pack<std::tuple<char, bool, double>, A, B, C>::type,
        std::tuple<A<char>, B<char, bool, double>, C<char, bool>>
    >::value, "");
}

How to generalize the above? Is it even possible?

score 2 · Answer 1 · edited May 23 '17 at 12:16

I won't write it all, but I'll do a walkthrough.

template<template<class...>class Z>
struct z_template{
  template<class...Ts>using result=Z<Ts...>;
};

this lets you manipulate templates like types.

template<template<class...>class Z, class...Ts>
using can_apply = /* ... */;

this asks the question "is Z<Ts...> valid? If so, return true_type".

template<class...>struct types{using type=types;};

this is a light-weight template pack.

template<template<class...>class Z, class types>
using apply = /* ... */;

this takes a template Z, and a types<Ts...>, and returns Z<Ts...>.

template<class Z, class types>
using z_apply = apply<typename Z::template result, types>;

this does it with a z_template argument instead of a template one.

Working on types as often as possible makes many kinds of metaprogramming easier.

Next we write

template<class types>using pop_front = // ...
template<class types>using reverse = // ...
template<class types>using pop_back = reverse<pop_front<reverse<types>>>;

which remove elements from the front and back of types.

template<class Result>
struct z_constant {
  template<class...Ts>using result=Result;
};

This finds the longest prefix of types that can be passed to Z::template result<???> validly. Some work to avoid passing too-short sequences is done, in case they fail "late":

template<class Z, class types>
struct z_find_longest_prefix :
  std::conditional_t<
    can_apply< z_apply, Z, types >{},
    z_constant<types>,
    z_template<longest_prefix>
  >::template result<Z, pop_back<types>>
{};
template<class Z, class types>
using z_find_longest_prefix_t = typename z_find_longest_prefix<Z,types>::type;

struct empty_t {};
template<class Z>
struct z_find_longest_prefix<Z,types<>>:
  std::conditional_t<
    can_apply< Z::template result >,
    types<>,
    empty_t
  >
{};

find_longest_prefix will fail to compile if there is no valid prefix.

template<class Z, class types>
using z_apply_longest_prefix_t =
  z_apply< Z, z_find_longest_prefix_t<Z, types> >;

template<class src, template<class...>class... Zs>
struct use_template;
template<class src, template<class...>class... Zs>
using use_template_t = typename use_template<src, Zs...>::type;

template<template<class...>class Z0, class...Ts, template<class...>class... Zs>
struct use_template< Z0<Ts...>, Zs... > {
  using type=Z0<
    z_apply_longest_prefix_t<
      z_template<Zs>, types<Ts...>
    >...
  >;
};

and up to typos and similar problems, done.

Can be cleaned up lots. Probably the entire z_ subsystem isn't needed. I just tend to run towards it whenever doing serious metaprogramming, because suddenly any metafunction I write that applies to types now can be used on templates.

reverse takes a bit of work to do efficiently.

can_apply is available in many of my posts.

pop_front is trivial.

apply should be easy.

score 2 · Accepted Answer · answered May 14 '16 at 01:37

This is "find shortest prefix".

Utilities:

// pack that is easy to append to
template<class... Ts> 
struct pack{
    template<class... T1s>
    using append = pack<Ts..., T1s...>;
};

template<class...> using void_t = void;

The meat:

// find the shortest proper prefix Ts... of [T, Rest...]
// such that A<Ts...> is well-formed, and return it.
template<template<class...> class A, // template we are going to look at
         class AlwaysVoid,           // for void_t
         class Current,              // pack containing the types we are testing next
         class T,                    // next type to add to pack if test fails
         class... Rest>              // remaining types
struct find_viable
    : find_viable<A, AlwaysVoid, typename Current::template append<T>, Rest...> {};

// picked if A<Ts...> is well-formed
template<template<class...> class A, class... Ts, class T, class...Rest>
struct find_viable<A, void_t<A<Ts...>>, pack<Ts...>, T, Rest...> {
    using type = A<Ts...>;
};

// Finds the shortest prefix of Ts... such that A<prefix...> is well formed.
// the extra void at the end is slightly hackish - find_viable only checks
// proper prefixes, so we add an extra dummy type at the end.
template<template<class...> class A, class... Ts>
using find_viable_t = typename find_viable<A, void, pack<>, Ts..., void>::type;

Then use it:

template <typename Pack, template <typename...> class... Templates> struct template_pack;

template <template <typename...> class P, typename... Ts,
          template <typename...> class... Templates>
struct template_pack<P<Ts...>, Templates...> {
    using type = P<find_viable_t<Templates, Ts...>...>;
};

ildjarn · Answer 3 · 2016-05-14T09:45:53.943

This looked fun so I tried my hand at it; I'm not claiming this is in any way better than the existing answers, but maybe some people will find it clearer:

namespace detail {

template<typename...>
using void_t = void;

template<template<typename...> class, typename, typename, typename EnableT = void>
struct fill_template;

template<template<typename...> class TemplateT, typename TupleT, std::size_t... Is>
struct fill_template<
    TemplateT, TupleT, std::index_sequence<Is...>,
    void_t<TemplateT<std::tuple_element_t<Is, TupleT>...>>
>
{
    using type = TemplateT<std::tuple_element_t<Is, TupleT>...>;
};

template<
    template<typename...> class TemplateT, typename TupleT,
    std::size_t I, std::size_t N
>
struct fill_template_dispatcher
{
    template<typename T, typename = typename T::type>
    static constexpr std::true_type test(int) { return {}; }
    template<typename T>
    static constexpr std::false_type test(long) { return {}; }

    using candidate_t = fill_template<TemplateT, TupleT, std::make_index_sequence<I>>;

    using type = typename std::conditional_t<
        test<candidate_t>(0),
        candidate_t,
        fill_template_dispatcher<TemplateT, TupleT, I + 1, I != N ? N : 0>
    >::type;
};

template<template<typename...> class TemplateT, typename TupleT, std::size_t I>
struct fill_template_dispatcher<TemplateT, TupleT, I, 0>
{
    static_assert(I != I, "tuple contains insufficient types to satisfy all templates");
};

} // namespace detail

template<typename TupleT, template<typename...> class... TemplateTs>
struct template_pack
{
    static_assert(std::tuple_size<TupleT>::value, "tuple must not be empty");

    using type = std::tuple<typename detail::fill_template_dispatcher<
        TemplateTs, TupleT, 0, std::tuple_size<TupleT>::value
    >::type...>;
};

template<typename TupleT, template<typename...> class... TemplateTs>
using template_pack_t = typename template_pack<TupleT, TemplateTs...>::type;

Online Demo

Note that for variadic class templates this will pass as few types as possible (see D in the test); for an implementation that passes as many types as possible instead, see that variation of the code here (only two lines are changed in the implementation).

Expanding with pack of templates

3 Answers3