使用简单的typelist实现的指数级编译时间。为什么？
使用简单的typelist实现的指数级编译时间。为什么？
提问于 2020-07-13 01:29:15
我正在尝试使用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 **) {}回答 4
Stack Overflow用户
回答已采纳
发布于 2020-07-13 01:50:40
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;这导致了实例化的线性数量，而不是指数。
Stack Overflow用户
发布于 2020-07-13 02:59:39
如果需要列表，第一件事就是定义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...>>>;并且编译时间仍然可以忽略不计。
Stack Overflow用户
发布于 2020-07-13 02:09:54
一种可能的替代方法是在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;
};页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62864301
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号