Экспоненциальное время компиляции с простой реализацией списка типов. Зачем? - PullRequest
Новая
       70

Экспоненциальное время компиляции с простой реализацией списка типов. Зачем?

6 голосов
/ 12 июля 2020

Пробую свои силы в списках типов C ++. Ниже представлена ​​простая реализация функции фильтрации списка типов. Кажется, что это работает, за исключением того, что время компиляции как в g cc, так и в clang ужасно c сверх, скажем, 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 ]

6 голосов
/ 12 июля 2020 
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;

, что вместо этого приводит к линейному количеству экземпляров экспоненты.

2 голосов
/ 12 июля 2020

Если вам нужны списки, первое, что вам нужно сделать, это определить функцию 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...>>>;

, и время компиляции остается незначительным.

0 голосов
/ 12 июля 2020

А теперь для чего-то совершенно другого ...

Я предлагаю разделить ваш «нормальный случай» (рекурсивный случай) на два разных случая: случай «истина» и случай «ложь».

К сожалению, для этого требуются дополнительные черты пользовательского типа 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 ()
 { }
0 голосов
/ 12 июля 2020

Возможной альтернативой может быть вставка std::conditional внутри filter_tl_impl.

Я имею в виду 

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