Implementation C++14 make_integer_sequence

C++ Problem Overview

I tried to implement the C++14 alias template make_integer_sequence, which simplifies the creation of the class template 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.

To implement make_integer_sequence we need a helper structure make_helper.

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

Implementing make_helper isn't too difficult.

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

To test make_integer_sequence I made this main 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, ~);
}

I compiled the program with GCC 4.8.0, on a quad-core i5 system with 8GBs of RAM. Successful compilation took 4 seconds.

But, when I changed the GEN macro to:

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, ~ );
}

The compilation was unsuccessful and outputted the error message: > virtual memory exhausted.

Could somebody explain this error and what caused it?

EDIT:

I simplified the test to:

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

I then successfully compiled with GCC 4.8.0 -ftemplate-depth=65536.

However this second test:

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

Did not compile with GCC 4.8.0 -ftemplate-depth=65536, and resulted in the error: >virtual memory exhausted.

So, my question is, how do I decrease template deep instantiation?

Regards, Khurshid.

C++ Solutions

Solution 1 - C++

Here's a log N implementation that doesn't even need an increased max-depth for template instantiations and compiles pretty fast:

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

Solution 2 - C++

This is basically me hacking around Xeo's solution: Making community wiki - if appreciative, please upvote Xeo.

...just modified until I felt it couldn't get any simpler, renamed and added value_type and size() per the Standard (but only doing index_sequence not integer_sequence), and code working with GCC 5.2 -std=c++14 could run otherwise unaltered under older/other compilers I'm stuck with. Might save someone some time / confusion.

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

Notes:

the "magic" of Xeo's solution is in the declaration of _merge_and_renumber (concat in his code) with exactly two parameters, while the specilisation effectively exposes their individual parameter packs

the typename...::type in...

  struct make_index_sequence
    : _merge_and_renumber<typename make_index_sequence<N/2>::type,
                          typename make_index_sequence<N - N/2>::type>

avoids the error:

invalid use of incomplete type 'struct std::_merge_and_renumber<std::make_index_sequence<1ul>, std::index_sequence<0ul> >'

Solution 3 - C++

I found very fast and needless deep recursion version of implementation of make_index_sequence. In my PC it compiles with N = 1 048 576 , with 2 s. (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(){}

Solution 4 - C++

You are missing a -1 here:

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

in particular:

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

Next, the first branch shouldn't be integer_sequence<T>, but rather 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;

which should be enough to get your original code to compile.

In general, when writing serious template metaprogramming, your main goal should be to keep the depth of template instantiation down. A way to think about this problem is imagining you have an infinite-thread computer: each independent calculation should be shuffled off onto its own thread, then shuffled together at the end. You have a few operations that take O(1) depth, like ... expansion: exploit them.

Usually, pulling of logarithmic depth is enough, because with a 900 depth, that allows 2^900 sized structures, and something else breaks first. (To be fair, what is more likely to happen is 90 different layers of 2^10 sized structures).

Solution 5 - C++

Here is another slightly more general variation of Xeo's logarithmic answer which provides make_integer_sequence for arbitrary types. This is done by using std::integral_constant in order to avoid the dreaded "template argument involves template parameter" error.

template<typename Int, Int... Ints>
struct integer_sequence
{
    using value_type = Int;
    static constexpr std::size_t size() noexcept
    {
        return sizeof...(Ints);
    }
};

template<std::size_t... Indices>
using index_sequence = integer_sequence<std::size_t, Indices...>;

namespace
{
    // Merge two integer sequences, adding an offset to the right-hand side.
    template<typename Offset, typename Lhs, typename Rhs>
    struct merge;

    template<typename Int, Int Offset, Int... Lhs, Int... Rhs>
    struct merge<
        std::integral_constant<Int, Offset>,
        integer_sequence<Int, Lhs...>,
        integer_sequence<Int, Rhs...>
    >
    {
        using type = integer_sequence<Int, Lhs..., (Offset + Rhs)...>;
    };

    template<typename Int, typename N>
    struct log_make_sequence
    {
        using L = std::integral_constant<Int, N::value / 2>;
        using R = std::integral_constant<Int, N::value - L::value>;
        using type = typename merge<
            L,
            typename log_make_sequence<Int, L>::type,
            typename log_make_sequence<Int, R>::type
        >::type;
    };

    // An empty sequence.
    template<typename Int>
    struct log_make_sequence<Int, std::integral_constant<Int, 0>>
    {
        using type = integer_sequence<Int>;
    };

    // A single-element sequence.
    template<typename Int>
    struct log_make_sequence<Int, std::integral_constant<Int, 1>>
    {
        using type = integer_sequence<Int, 0>;
    };
}

template<typename Int, Int N>
using make_integer_sequence =
    typename log_make_sequence<
        Int, std::integral_constant<Int, N>
    >::type;

template<std::size_t N>
using make_index_sequence = make_integer_sequence<std::size_t, N>;

Demo: coliru

Solution 6 - C++

Simple implementation O(N). Probably not what you want for large N, but my application is only for calling functions with indexed arguments, and I wouldn't expect an arity of more than about 10. I haven't filled in the members of integer_sequence. I'm looking forward to using a standard library implementation and nuking this :)

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;

Solution 7 - C++

Here is another implementation technique (for T=size_t), it uses C++17 fold expressions and bitwise generation (i.e. O(log(N)):

template <size_t... Is>
struct idx_seq {
  template <size_t N, size_t Offset>
  struct pow2_impl {
    using type = typename idx_seq<Is..., (Offset + Is)...>::template pow2_impl<N - 1, Offset + sizeof...(Is)>::type;
  };
  template <size_t _> struct pow2_impl<0, _> { using type = idx_seq; };
  template <size_t _> struct pow2_impl<(size_t)-1, _> { using type = idx_seq<>; };

  template <size_t Offset>
  using offset = idx_seq<(Offset + Is)...>;
};

template <size_t N>
using idx_seq_pow2 = typename idx_seq<0>::template pow2_impl<N, 1>::type;

template <size_t... Is, size_t... Js>
constexpr static auto operator,(idx_seq<Is...>, idx_seq<Js...>)
  -> idx_seq<Is..., Js...>
{ return {}; }

template <size_t N, size_t Mask, size_t... Bits>
struct make_idx_seq_impl {
  using type = typename make_idx_seq_impl<N, (N >= Mask ? Mask << 1 : 0), Bits..., (N & Mask)>::type;
};

template <size_t N, size_t... Bits>
struct make_idx_seq_impl<N, 0, Bits...> {
  using type = decltype((idx_seq<>{}, ..., typename idx_seq_pow2<Bits>::template offset<(N & (Bits - 1))>{}));
};

template <size_t N>
using make_idx_seq = typename make_idx_seq_impl<N, 1>::type;

Solution 8 - C++

Here is a very simple solution implemented with recursion based on tag dispatching

template <typename T, T M, T ... Indx>
constexpr std::integer_sequence<T, Indx...> make_index_sequence_(std::false_type)
{
    return {};
}

template <typename T, T M, T ... Indx>
constexpr auto make_index_sequence_(std::true_type)
{
    return make_index_sequence_<T, M, Indx..., sizeof...(Indx)>(
            std::integral_constant<bool, sizeof...(Indx) + 1 < M>());
}

template <size_t M>
constexpr auto make_index_sequence()
{
    return make_index_sequence_<size_t, M>(std::integral_constant<bool, (0 < M)>());
}

However, this solution can not be extended to C++11.

Content Type	Original Author	Original Content on Stackoverflow
Question	Khurshid	View Question on Stackoverflow
Solution 1 - C++	Xeo	View Answer on Stackoverflow
Solution 2 - C++	Tony Delroy	View Answer on Stackoverflow
Solution 3 - C++	Khurshid	View Answer on Stackoverflow
Solution 4 - C++	Yakk - Adam Nevraumont	View Answer on Stackoverflow
Solution 5 - C++	joki	View Answer on Stackoverflow
Solution 6 - C++	cdyson37	View Answer on Stackoverflow
Solution 7 - C++	smilingthax	View Answer on Stackoverflow
Solution 8 - C++	Sergey Kolesnik	View Answer on Stackoverflow