I am trying my hand at C++ type lists. Below is a trivial implementation of a type list filter function. It seems to work except that compilation times in both gcc and clang are horrific beyond say 18 elements. I was wondering what improvements I could make to make this practical.
#include <type_traits>
// a type list
template <class... T> struct tl ;
// helper filter for type list
template <class IN_TL, class OUT_TL, template <typename> class P>
struct filter_tl_impl;
// Base case
template <class... Ts, template <typename> class P>
// If the input list is empty we are done
struct filter_tl_impl<tl<>, tl<Ts...>, P> {
using type = tl<Ts...>;
};
// Normal case
template <class Head, class... Tail, class... Ts2, template <typename> class P>
struct filter_tl_impl<tl<Head, Tail...>, tl<Ts2...>, P> {
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;
};
template <class TL, template <typename> class P> struct filter_tl {
using type = typename filter_tl_impl<TL, tl<>, P>::type;
};
// Test code
using MyTypes = tl<
char*, bool, char, int, long, void,
char*, bool, char, int, long, void,
char*, bool, char, int, long, void
>;
using MyNumericTypes = filter_tl<MyTypes, std::is_arithmetic>::type;
static_assert(std::is_same < MyNumericTypes,
tl<
bool,char,int,long,
bool,char,int,long,
bool,char,int,long
>> :: value);
int main(int, char **) {}
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.