52

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.

4

8 回答 8

117

这是一个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>{};
于 2013-07-02T13:13:54.620 回答
25

这基本上是我在破解 Xeo 的解决方案：制作社区 wiki - 如果欣赏，请支持 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在他的代码中）声明只有两个参数，而规范有效地公开了它们各自的参数包

  • 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> >'
于 2015-08-26T09:52:20.930 回答
10

我发现make_index_sequence. 在我的 PC 中，它使用 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(){}
于 2013-11-20T16:12:09.360 回答
4

您在-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大小的结构）。

于 2013-07-03T03:41:25.760 回答
4

这是Xeo的对数答案的另一个稍微更一般的变体，它提供make_integer_sequence了任意类型。这是通过使用来完成的std::integral_constant，以避免可怕的“模板参数涉及模板参数”错误。

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

演示：大肠杆菌

于 2018-04-24T11:32:55.223 回答
2

简单的实现 O(N)。对于大 N 可能不是您想要的，但我的应用程序仅用于调用具有索引参数的函数，并且我不希望 arity 超过大约 10。我没有填写 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;
于 2014-12-24T00:17:57.337 回答
0

这是一个非常简单的解决方案，使用基于标签调度的递归实现

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

但是，此解决方案无法扩展到 C++11。

于 2021-01-25T10:27:51.617 回答
0

这是另一种实现技术（对于T=size_t），它使用 C++17 折叠表达式和按位生成（即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;
于 2020-11-19T14:23:53.990 回答