執行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不是太困難。與RAM 8GBs

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編譯的程序，四核i5系統上：

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我做了這個主要功能。 成功編譯花費了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深入= 65536編譯。

不過本次測試：

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

沒有與GCC 4.8.0 -ftemplate深度= 65536編譯，並導致錯誤：

virtual memory exhausted.

所以，我的問題是，我如何減少模板深度實例化？

Regards， Khurshid。

Answer 1

這裏有一個​​實現，甚至不需要增加的最大深度爲模板實例和編譯非常快：

// 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

你缺少一個-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; 

這應該足以讓您的原始代碼編譯。

通常，在編寫嚴重的元編程時，您的主要目標應該是保持實例化的深度。想想這個問題的一種方法是想象你有一臺無限線程的計算機：每一次獨立的計算都應該在自己的線程上進行洗牌，然後在最後一起洗牌。你有一些需要O（1）深度的操作，比如...擴展：利用它們。

通常，拉動對數深度就足夠了，因爲深度爲900，這允許尺寸爲2^900的結構，並且其他東西首先被破壞。 （公平地說，更可能發生的是90個不同層次的2^10大小的結構）。

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(){} 

Answer 4

簡單實現O（N）。可能不是你想要的大N，但我的應用程序僅用於調用具有索引參數的函數，並且我不希望有大於10左右的arity。我沒有填充integer_sequence的成員。我很期待使用標準庫的實現和的摧毀這個:)

template <typename T, T... ints> 
struct integer_sequence 
{ }; 

template <typename T, T N, 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; 

Answer 5

這基本上是我周圍的黑客XEO的解決方案：讓社區維基 - 如果激賞，請給予好評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> >'