使用简单的类型列表实现的指数编译时间。为什么？

Question

我正在尝试 C++ 类型列表。下面是类型列表过滤器函数的简单实现。它似乎有效，只是 gcc 和 clang 的编译时间都超过了 18 个元素。我想知道我可以做些什么改进来使这个实用。

#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 **) {}

Answer 1

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;

实例化双方因为::type.

您可能会在 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;

这导致实例化的数量是线性的，而不是指数的。

Answer 2

一个可能的替代方法是在 filter_tl_impl 中插入 std::conditional。

我是说

// Normal case
template <typename Head, typename... Tail, typename... Ts2,
          template <typename> class P>
struct filter_tl_impl<tl<Head, Tail...>, tl<Ts2...>, P>
 {
   using type = typename filter_tl_impl<tl<Tail...>,
                                        std::conditional_t<
                                           P<Head>::value,
                                           tl<Ts2..., Head>,
                                           tl<Ts2...>>,
                                        P>::type;
};

Answer 3

而现在，为了一些完全不同的东西...

我建议将你的“正常情况”（递归情况）分成两种不同的情况：“真”情况和“假”情况。

不幸的是，这需要额外的自定义类型特征 check_first

template <typename, template <typename> class>
struct check_first : public std::false_type
 { };

template <typename H, typename ... T, template <typename> class P>
struct check_first<tl<H, T...>, P>
   : public std::integral_constant<bool, P<H>::value>
 { };

现在可以这样写filter_tl_impl

// declaration and ground case
template <typename I, typename O, template <typename> class P,
          bool = check_first<I, P>::value>
struct filter_tl_impl
 { using type = O; };

// recursive-positive case
template <typename H, typename... T, typename... Ts,
          template <typename> class P>
struct filter_tl_impl<tl<H, T...>, tl<Ts...>, P, true>
   : public filter_tl_impl<tl<T...>, tl<Ts..., H>, P>
 { };

// recursive-negative case
template <typename H, typename... T, typename... Ts,
          template <typename> class P>
struct filter_tl_impl<tl<H, T...>, tl<Ts...>, P, false>
   : public filter_tl_impl<tl<T...>, tl<Ts...>, P>
 { };

我也将 filter_tl 重写为更简单的 using

template <typename TL, template <typename> class P>
using filter_tl = typename filter_tl_impl<TL, tl<>, P>::type;

所以你的原始代码变成了

#include <type_traits>

// a type list
template <typename...>
struct tl;

template <typename, template <typename> class>
struct check_first : public std::false_type
 { };

template <typename H, typename ... T, template <typename> class P>
struct check_first<tl<H, T...>, P>
   : public std::integral_constant<bool, P<H>::value>
 { };   

// declaration and ground case
template <typename I, typename O, template <typename> class P,
          bool = check_first<I, P>::value>
struct filter_tl_impl
 { using type = O; };

// recursive-positive case
template <typename H, typename... T, typename... Ts,
          template <typename> class P>
struct filter_tl_impl<tl<H, T...>, tl<Ts...>, P, true>
   : public filter_tl_impl<tl<T...>, tl<Ts..., H>, P>
 { };

// recursive-negative case
template <typename H, typename... T, typename... Ts,
          template <typename> class P>
struct filter_tl_impl<tl<H, T...>, tl<Ts...>, P, false>
   : public filter_tl_impl<tl<T...>, tl<Ts...>, P>
 { };

template <typename TL, template <typename> class P>
using filter_tl = 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>;

static_assert(std::is_same_v<MyNumericTypes,
                             tl<bool, char, int, long,
                                bool, char, int, long,
                                bool, char, int, long>>);

int main ()
 { }

Answer 4

如果你想要列表，你要做的第一件事就是定义 cons 函数。剩下的就自然而然了。

// 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>;
  };

注意tailRes只是为了可读性而定义的，你可以直接写

    using type = std::conditional_t<P<Head>::value,
                                    cons<Head, filter_tl<P, tl<Tail...>>>,
                                    filter_tl<P, tl<Tail...>>>;

并且编译时间可以忽略不计。

使用简单的类型列表实现的指数编译时间。为什么？

Exponential compilation times with simple typelist implementation. Why?

c++

template-meta-programming

variadic-templates