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

Question

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

sam*_*ise 6 c++ template-meta-programming variadic-templates

我正在尝试使用 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 **) {}

Run Code Online (Sandbox Code Playgroud)

Answer 1

Jar*_*d42 6

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;

Run Code Online (Sandbox Code Playgroud)

实例化双方，因为::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;

Run Code Online (Sandbox Code Playgroud)

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

不，至少，我们必须检查两个分支都没有错误，这需要完全简化它们。还有一个共同化专业化的问题：“std::conditional<true, std::type_identity<int>, float>”必须与“std::conditional<true, int, float>”*完全相同的类型* ，最简单的方法是在专门化“std::conditional”之前将“std::type_identity<int>”简化为“int”。请记住，“std::conditional”只是一个普通的类模板。它不像 `if`/`else` 或 `? ：`。它是一个函数“Type conditional(bool b, Type, Type)”，仅接受评估的参数。 (2认同)

归档时间：	5 年，4 月前
查看次数：	124 次
最近记录：	5 年，4 月前