实现C ++ 14 make_integer_sequence
我试图实现C ++ 14别名模板make_integer_sequence ，这简化了类模板integer_sequence的创build。
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, TN, 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; };
testingmake_integer_sequence我做了这个主要function：
int main() { #define GEN(z,n,temp) \ typedef make_integer_sequence< int, n > BOOST_PP_CAT(int_seq,n) ; BOOST_PP_REPEAT(256, GEN, ~); }
我使用GCC 4.8.0编译了一个带有8GB内存的四核i5系统。 成功的编译花了4秒钟。
但是，当我将GENmacros更改为：
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, ~ ); }
编译失败并输出错误信息：
虚拟内存耗尽。
有人可以解释这个错误，是什么造成的？
编辑：
我简化了testing：
int main() { typedef make_integer_sequence< int, 4096 > int_seq4096; }
然后我成功编译了GCC 4.8.0 -template-depth = 65536。
然而，第二个testing：
int main() { typedef make_integer_sequence< int, 16384 > int_seq16384; }
没有用GCC 4.8.0 -template-depth = 65536编译，导致错误：
虚拟内存耗尽。
所以，我的问题是，如何减less模板深度实例？
问候，Khurshid。
这是一个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>{};
这基本上是我对Xeo的解决scheme的攻击：制作社区维基 – 如果感激， 请注意Xeo 。
…只是修改，直到我觉得它不能得到任何更简单，重新命名和增加value_type和size()每标准（但只做index_sequence不integer_sequence ）和代码工作与GCC 5.2 -std=c++14可以在旧的/其他编译器下运行，否则我坚持。 可以节省一些时间/困惑。
// based on http://stackoverflow.com/a/17426611/410767 by Xeo namespace std // WARNING: at own risk, otherwise use own namespace { template <size_t... Ints> struct index_sequence { using type = index_sequence; using value_type = size_t; static constexpr std::size_t size() noexcept { return sizeof...(Ints); } }; // -------------------------------------------------------------- template <class Sequence1, class Sequence2> struct _merge_and_renumber; template <size_t... I1, size_t... I2> struct _merge_and_renumber<index_sequence<I1...>, index_sequence<I2...>> : index_sequence<I1..., (sizeof...(I1)+I2)...> { }; // -------------------------------------------------------------- template <size_t N> struct make_index_sequence : _merge_and_renumber<typename make_index_sequence<N/2>::type, typename make_index_sequence<N - N/2>::type> { }; template<> struct make_index_sequence<0> : index_sequence<> { }; template<> struct make_index_sequence<1> : index_sequence<0> { }; }
笔记：
-
Xeo解决scheme的“魔力”在于具有两个参数的
_merge_and_renumber（concat在他的代码中），而specilisation则有效地暴露了它们各自的参数包 -
typename…::type…struct make_index_sequence : _merge_and_renumber<typename make_index_sequence<N/2>::type, typename make_index_sequence<N - N/2>::type>
避免错误：
invalid use of incomplete type 'struct std::_merge_and_renumber<std::make_index_sequence<1ul>, std::index_sequence<0ul> >'
我发现make_index_sequence的执行速度非常快，不需要深度recursion版本。 在我的电脑中，编译N = 1 048 576，时间为2秒。 （PC：Centos 6.4 x86，i5,8 Gb RAM，gcc-4.4.7 -std = c ++ 0x -O2 -Wall）。
#include <cstddef> // for std::size_t template< std::size_t ... i > struct index_sequence { typedef std::size_t value_type; typedef index_sequence<i...> type; // gcc-4.4.7 doesn't support `constexpr` and `noexcept`. static /*constexpr*/ std::size_t size() /*noexcept*/ { return sizeof ... (i); } }; // this structure doubles index_sequence elements. // s- is number of template arguments in IS. template< std::size_t s, typename IS > struct doubled_index_sequence; template< std::size_t s, std::size_t ... i > struct doubled_index_sequence< s, index_sequence<i... > > { typedef index_sequence<i..., (s + i)... > type; }; // this structure incremented by one index_sequence, iff NEED-is true, // otherwise returns IS template< bool NEED, typename IS > struct inc_index_sequence; template< typename IS > struct inc_index_sequence<false,IS>{ typedef IS type; }; template< std::size_t ... i > struct inc_index_sequence< true, index_sequence<i...> > { typedef index_sequence<i..., sizeof...(i)> type; }; // helper structure for make_index_sequence. template< std::size_t N > struct make_index_sequence_impl : inc_index_sequence< (N % 2 != 0), typename doubled_index_sequence< N / 2, typename make_index_sequence_impl< N / 2> ::type >::type > {}; // helper structure needs specialization only with 0 element. template<>struct make_index_sequence_impl<0>{ typedef index_sequence<> type; }; // OUR make_index_sequence, gcc-4.4.7 doesn't support `using`, // so we use struct instead of it. template< std::size_t N > struct make_index_sequence : make_index_sequence_impl<N>::type {}; //index_sequence_for any variadic templates template< typename ... T > struct index_sequence_for : make_index_sequence< sizeof...(T) >{}; // test typedef make_index_sequence< 1024 * 1024 >::type a_big_index_sequence; int main(){}
你在这里错过了-1 ：
typedef typename mpl::if_< T(0) == N, mpl::identity< integer_sequence<T> >, make_helper< T, N, N-1,I...> >::type;
尤其是：
typedef typename mpl::if_< T(0) == N, mpl::identity< integer_sequence<T> >, make_helper< T, N-1, N-1,I...> >::type;
接下来，第一个分支不应该是integer_sequence<T> ，而应该是integer_sequence<T, I...> 。
typedef typename mpl::if_< T(0) == N, mpl::identity< integer_sequence<T, I...> >, make_helper< T, N-1, N-1,I...> >::type;
这应该足以让你的原代码编译。
一般来说，在编写严肃的template元编程时，您的主要目标应该是保持template实例化的深度。 想想这个问题的一种方法是想象你有一台无限线程的计算机：每一个独立的计算应该在自己的线程上被洗牌，然后在最后洗牌。 你有一些采取O（1）深度的操作，比如...扩展：利用它们。
通常，对数深度的拉伸是足够的，因为900深度允许2^900大小的结构，而其他东西首先被打破。 （公平地说，更可能发生的是90个不同层次的2^10大小的结构）。
简单的实现O（N）。 可能不是你想要的大N，但我的应用程序只是用索引参数调用函数，我不会期望一个约10以上的arity。我还没有填充integer_sequence的成员。 我期待使用标准的库实现和nuking这:)
template <typename T, T... ints> struct integer_sequence { }; template <typename T, TN, typename = void> struct make_integer_sequence_impl { template <typename> struct tmp; template <T... Prev> struct tmp<integer_sequence<T, Prev...>> { using type = integer_sequence<T, Prev..., N-1>; }; using type = typename tmp<typename make_integer_sequence_impl<T, N-1>::type>::type; }; template <typename T, T N> struct make_integer_sequence_impl<T, N, typename std::enable_if<N==0>::type> { using type = integer_sequence<T>; }; template <typename T, T N> using make_integer_sequence = typename make_integer_sequence_impl<T, N>::type;
