实现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我做了这个主要功能:

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 RAM的四核i5系统上.成功编译花了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, ~ );
}

编译失败并输出错误消息:

虚拟内存耗尽.

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

编辑:

我将测试简化为:

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编译,导致错误:

虚拟内存耗尽.

所以,我的问题是,如何减少模板深度实例化？

此致,Khurshid.

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>{};

Answer 2

这基本上是我围绕Xeo的解决方案:制作社区维基 - 如果感激,请upvote 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解决方案的"神奇之处"在于_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> >'

Answer 3

我发现了非常快速且不必要的深度递归版本的实现make_index_sequence.在我的电脑中,它编译为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(){}