Exponential compilation times with simple typelist implementation. Why?
using type = typename std::conditional<
// Does the predicate hold on the head of the input list?
P<Head>::value,
// The head of the input list matches our predictate, copy it
typename filter_tl_impl<tl<Tail...>, tl<Ts2..., Head>, P>::type,
// The head of the input list does not match our predicate, skip
// it
typename filter_tl_impl<tl<Tail...>, tl<Ts2...>, P>::type>::type;
instantiates both sides because of ::type
.
You might delay intermediate instantiation by after the std::conditional
:
using type = typename std::conditional<
// Does the predicate hold on the head of the input list?
P<Head>::value,
// The head of the input list matches our predicate, copy it
filter_tl_impl<tl<Tail...>, tl<Ts2..., Head>, P>,
// The head of the input list does not match our predicate, skip
// it
filter_tl_impl<tl<Tail...>, tl<Ts2...>, P>>::type::type;
Which leads to linear number of instantiations instead of exponential.
If you want lists, the first thing you do is define the cons
function. The rest becomes natural and straightforward.
// first, define `cons`
template <class Head, class T> struct cons_impl;
template <class Head, class ... Tail>
struct cons_impl <Head, tl<Tail...>> {
using type = tl<Head, Tail...>;
};
template <class Head, class T>
using cons = typename cons_impl<Head, T>::type;
// next, define `filter`
template <template <typename> class P, class T>
struct filter_tl_impl;
template <template <typename> class P, class T>
using filter_tl = typename filter_tl_impl<P, T>::type;
// empty list case
template <template <typename> class P>
struct filter_tl_impl<P, tl<>> {
using type = tl<>;
};
// non-empty lust case
template <template <typename> class P, class Head, class ... Tail>
struct filter_tl_impl<P, tl<Head, Tail...>> {
using tailRes = filter_tl<P, tl<Tail...>>;
using type = std::conditional_t<P<Head>::value,
cons<Head, tailRes>,
tailRes>;
};
Note tailRes is defined for readability only, you can write directly
using type = std::conditional_t<P<Head>::value,
cons<Head, filter_tl<P, tl<Tail...>>>,
filter_tl<P, tl<Tail...>>>;
and compilation time remains negligible.