c++ - 实现 C++14 make_integer_sequence

Question

我尝试实现 C++14别名模板make_integer_sequence，简化了类模板的创建integer_sequence .

template< class T, T... I> struct integer_sequence
{
    typedef T value_type;
    static constexpr size_t size() noexcept { return sizeof...(I) ; }

};

template< class T, T N>
using make_integer_sequence = integer_sequence< T, 0,1,2, ... ,N-1 >; // only for illustration.

要实现make_integer_sequence，我们需要一个辅助结构make_helper。

template< class T , class N >
using make_integer_sequence = typename make_helper<T,N>::type;

实现 make_helper 并不太难。

template< class T, T N, T... I >
struct make_helper
{
   typedef typename mpl::if_< T(0) == N,  
                  mpl::identity< integer_sequence<T,I...> >,
                  make_helper< T, N-1, N-1,I...> 
               >::type;
};

为了测试 make_integer_sequence 我做了这个 main 函数:

int main()
{
    #define GEN(z,n,temp)   \
     typedef make_integer_sequence< int, n >  BOOST_PP_CAT(int_seq,n) ;

   BOOST_PP_REPEAT(256, GEN, ~);
}

我在具有 8GB 内存的四核 i5 系统上使用 GCC 4.8.0 编译了该程序。成功编译耗时 4 秒。

但是，当我将 GEN 宏更改为:

int main() {

#define GEN(z,n,temp) \
typedef make_integer_sequence< int, n * 4 > BOOST_PP_CAT(int_seq, n) ;

BOOST_PP_REPEAT(256, GEN, ~ );
}

编译不成功，输出错误信息:

virtual memory exhausted.

有人能解释一下这个错误吗？是什么原因造成的？

编辑:

我将测试简化为:

int main()
{
   typedef make_integer_sequence< int, 4096 > int_seq4096;
}

然后我使用 GCC 4.8.0 -ftemplate-depth=65536 成功编译。

但是第二次测试:

int main()
{
    typedef make_integer_sequence< int, 16384 > int_seq16384;
}

没有使用 GCC 4.8.0 -ftemplate-depth=65536 编译，导致错误:

virtual memory exhausted.

那么，我的问题是，如何减少模板深度实例化？

问候，胡尔希德。

Answer 1

这是一个 log N 实现，它甚至不需要增加模板实例化的最大深度并且编译速度非常快:

// using aliases for cleaner syntax
template<class T> using Invoke = typename T::type;

template<unsigned...> struct seq{ using type = seq; };

template<class S1, class S2> struct concat;

template<unsigned... I1, unsigned... I2>
struct concat<seq<I1...>, seq<I2...>>
  : seq<I1..., (sizeof...(I1)+I2)...>{};

template<class S1, class S2>
using Concat = Invoke<concat<S1, S2>>;

template<unsigned N> struct gen_seq;
template<unsigned N> using GenSeq = Invoke<gen_seq<N>>;

template<unsigned N>
struct gen_seq : Concat<GenSeq<N/2>, GenSeq<N - N/2>>{};

template<> struct gen_seq<0> : seq<>{};
template<> struct gen_seq<1> : seq<0>{};