compilador - Implementación C++ 14 make_integer_sequence

gcc c++

Question

Intenté implementar la plantilla de alias C++14 make_integer_sequence , que simplifica la creación de la plantilla de clase 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.

Para implementar make_integer_sequence , necesitamos una estructura auxiliar make_helper .

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

La implementación de make_helper no es muy difícil.

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

Para probar make_integer_sequence hice esta función principal:

int main()
{
    #define GEN(z,n,temp)   /
     typedef make_integer_sequence< int, n >  BOOST_PP_CAT(int_seq,n) ;

   BOOST_PP_REPEAT(256, GEN, ~);
}

Recopilé el programa con GCC 4.8.0, en un sistema quad-core i5 con 8 GB de RAM. La compilación exitosa tomó 4 segundos.

Pero, cuando cambié la macro GEN a:

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

La compilación no tuvo éxito y arrojó el mensaje de error:

memoria virtual agotada

¿Alguien podría explicar este error y qué lo causó?

EDITAR:

Simplifiqué la prueba para:

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

Luego compilé satisfactoriamente con GCC 4.8.0 -ftemplate-depth = 65536.

Sin embargo, esta segunda prueba:

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

No compiló con GCC 4.8.0 -ftemplate-depth = 65536, y dio como resultado el error:

memoria virtual agotada

Entonces, mi pregunta es, ¿cómo puedo disminuir la instanciación profunda de plantillas?

Saludos, Khurshid.

Answer 1

Aquí hay otra variación ligeramente más general de la respuesta logarítmica de Xeo que proporciona make_integer_sequence para tipos arbitrarios. Esto se hace usando std::integral_constant para evitar el temido error de "argumento de plantilla implica parámetro de plantilla".

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

Demostración: coliru

Answer 2

Aquí hay una implementación de log N que ni siquiera necesita una mayor profundidad máxima para las instancias de plantillas y se compila bastante rápido:

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

Encontré la versión de recursión profunda muy rápida e innecesaria de make_index_sequence . En mi PC compila con N = 1 048 576, con 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(){}

Answer 4

Esto es básicamente yo pirateando la solución de Xeo: haciendo una wiki comunitaria, si agradecido, vota por favor a Xeo .

... solo se modificó hasta que sentí que no podía obtener ningún value_type and size() más simple, renombrado y agregado por el estándar (pero solo haciendo index_sequence no integer_sequence ), y el código que funcionaba con GCC 5.2 -std=c++14 podría corre de otra manera inalterado bajo compiladores más antiguos / otros con los que estoy atascado. Podría salvar a alguien un poco de tiempo / confusión.

// based on http://.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> { };
}

Notas:

• la "magia" de la solución de Xeo está en la declaración de _merge_and_renumber ( concat en su código) con exactamente dos parámetros, mientras que la especificación expone efectivamente sus paquetes de parámetros individuales

• el typename ::type ... ::type en ...

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

evita el error:

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

Answer 5

Implementación simple O (N). Probablemente no sea lo que quiere para N grande, pero mi aplicación es solo para llamar funciones con argumentos indexados, y no esperaría una arity de más de 10. No he completado los miembros de integer_sequence. Tengo muchas ganas de usar una implementación de biblioteca estándar y nuking esto :)

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 6

Te estás perdiendo un -1 aquí:

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

en particular:

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

A continuación, la primera rama no debe ser integer_sequence<T> , sino más bien 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;

que debería ser suficiente para compilar el código original.

En general, cuando se escribe metaprogramación de template serias, su principal objetivo debe ser mantener baja la profundidad de template instanciación de template . Una manera de pensar acerca de este problema es imaginando que tiene una computadora de hilo infinito: cada cálculo independiente debe mezclarse en su propio hilo y luego mezclarse al final. Tiene algunas operaciones que tienen una profundidad de O (1), como ... expansión: explótelas.

Por lo general, es suficiente tirar de la profundidad logarítmica, porque con una profundidad de 900 , eso permite estructuras de tamaño 2^900 , y algo más se rompe primero. (Para ser justos, lo más probable es que surjan 90 capas diferentes de estructuras de tamaño 2^10 ).