Реализация на C++14 make_integer_sequence

Я попытался реализовать с++14 make_integer_sequence шаблон псевдоним, которое упрощает создание шаблона класса [integer_sequence`]2.

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, на четырехъядерной системе i5 с 8GBs оперативной памяти. Успешная компиляция заняла 4 секунды.

Но, когда я сменила ген макрос:

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

Затем я скомпилировал с 4.8.0 -ftemplate-глубина ССЗ=65536.

Однако этот второй тест:

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

Не удалось скомпилировать с 4.8.0 -ftemplate-глубина ССЗ=65536, и вылилось в ошибки:

виртуальная память исчерпана.

Итак, мой вопрос, Как уменьшить глубокие шаблона, инстанцирования?

С уважением, Хуршид.

JulianAustralia
Редактировал вопрос 2-го июля 2015 в 11:44
Программирование
gcc c++ c++11 c++14
2-го июля 2013 в 11:31
30 просмотров
Комментарии к вопросу (1)
Решение

Здесь'ы реализация отчет N что не'т даже увеличенная максимальная глубина для шаблона, инстанцирования и составляет довольно быстро:

// using aliases for cleaner syntax
template using Invoke = typename T::type;

template struct seq{ using type = seq; };

template struct concat;

template
struct concat
  : seq{};

template
using Concat = Invoke;

template struct gen_seq;
template using GenSeq = Invoke;

template
struct gen_seq : Concat{};

template struct gen_seq : seq{};
template struct gen_seq : seq{};
Комментарии (13)

Это в основном меня взлом вокруг Хео'ы решение: создание сообщества Вики - если ценит, пожалуйста, голосуйте Хео.

...просто изменен, пока я не чувствовал, что это не'т получить любой проще, переименовал и добавил, что с value_type и размер () в стандарт (но только делаешьindex_sequenceнеinteger_sequence), и код работает с GCC 5.2-с std=с++14` может работать, в противном случае без изменений под старые/другие компиляторы я'м застрял с. Может спасти кого-то какое-то время / путаница.

// based on http://stackoverflow.com/a/17426611/410767 by Xeo
namespace std  // WARNING: at own risk, otherwise use own namespace
{
    template 
    struct index_sequence
    {
        using type = index_sequence;
        using value_type = size_t;
        static constexpr std::size_t size() noexcept { return sizeof...(Ints); }
    };

    // --------------------------------------------------------------

    template 
    struct _merge_and_renumber;

    template 
    struct _merge_and_renumber
      : index_sequence
    { };

    // --------------------------------------------------------------

    template 
    struct make_index_sequence
      : _merge_and_renumber
    { };

    template struct make_index_sequence : index_sequence { };
    template struct make_index_sequence : index_sequence { };
}

Примечания:

  • в "Магия" из приемо-передатчика'ный раствор в декларации _merge_and_renumber (функция concat в его код) с точностью до двух параметров, а specilisation эффективно подвергает их отдельных параметров пакетов

  • в имя_типа...`::тип в...

структура make_index_sequence : _merge_and_renumber<make_index_sequence&ЛТ имя_типа;Н/2>::тип, make_index_sequence&ЛТ имя_типа;Н - П/2>::тип>

&ампер;усилитель; nbsp;&ампер;усилитель; nbsp;&ампер;усилитель; nbsp;&ампер;усилитель; nbsp;во избежание ошибок:

invalid use of incomplete type 'struct std::_merge_and_renumber'
magras
Редактировал ответ 17-го июня 2016 в 2:33
Комментарии (3)

Я нашел очень быстро и излишне глубокая рекурсия варианте осуществления make_index_sequence. В моем компьютере он компилирует с N = 1 048 576 , с 2 сек. (ПК : ОС CentOS 6.4 с архитектурой x86, i5 процессор, 8 Гб ОЗУ, на GCC-4.4.7 -с std=с++0х -О2 -стена).

#include  // for std::size_t

template< std::size_t ... i >
struct index_sequence
{
    typedef std::size_t value_type;

    typedef index_sequence 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 >
{
    typedef index_sequence 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{ typedef IS type; };

template< std::size_t ... i >
struct inc_index_sequence< true, index_sequence >
{
    typedef index_sequence 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.
templatestruct make_index_sequence_impl{ 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::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(){}
Casey
Редактировал ответ 22-го октября 2014 в 2:48
Комментарии (0)

Вам не хватает -1 здесь:

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

в частности:

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

Далее, первое отделение должно'т быть integer_sequence в<Т&GT;, а integer_sequence<Т, Я...>.

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

которых должно быть достаточно, чтобы получить исходный код для компиляции.

В общем, при написании серьезных "шаблон" метапрограммирование, ваша главная цель должна держать глубину "шаблон" инстанцирование вниз. Способ думать об этой проблеме не мерещится, у вас есть бесконечное-нить компьютер: каждый независимый расчет должен быть заковыляла на своем собственном потоке, затем перемешиваются вместе в конце. У вас есть несколько операций, что займет O(1) глубина, как ... расширение: использовать.

Обычно, вытягивать логарифмической глубины достаточно, потому что с 900 глубина, что позволяет 2^900 большие структуры, и еще что-то сломается первым. (Чтобы быть справедливым, что это более вероятно, произойдет на 90 разных слоев 2^10 размер структуры).

Комментарии (0)

Вот еще немного более общий вариация Хео's в логарифмических ответ, который обеспечивает make_integer_sequence для произвольных типов. Это делается с помощью функции std::integral_constant, чтобы избежать страшной "и шаблон аргумент шаблон включает параметр" и ошибка.

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

template
using index_sequence = integer_sequence;

namespace
{
    // Merge two integer sequences, adding an offset to the right-hand side.
    template
    struct merge;

    template
    struct merge<
        std::integral_constant,
        integer_sequence,
        integer_sequence
    >
    {
        using type = integer_sequence;
    };

    template
    struct log_make_sequence
    {
        using L = std::integral_constant;
        using R = std::integral_constant;
        using type = typename merge<
            L,
            typename log_make_sequence::type,
            typename log_make_sequence::type
        >::type;
    };

    // An empty sequence.
    template
    struct log_make_sequence
    {
        using type = integer_sequence;
    };

    // A single-element sequence.
    template
    struct log_make_sequence
    {
        using type = integer_sequence;
    };
}

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

template
using make_index_sequence = make_integer_sequence;

Демо: coliru

joki
Редактировал ответ 25-го апреля 2018 в 10:46
Комментарии (0)

Простая реализация за o(n) времени. Наверное, не то, что вы хотите для больших n, но мое приложение является только для вызова функций с проиндексированных Аргументы, и я бы'т ожидать арности больше, чем примерно 10. Я не'т заполнить в члены integer_sequence. Я'м глядя вперед, чтобы с помощью реализации стандартной библиотеки и уничтожить этого :)

template 
struct integer_sequence
{ };

template 
struct make_integer_sequence_impl
{
    template 
    struct tmp;

    template 
    struct tmp
    {
        using type = integer_sequence;
    };

    using type = typename tmp::type;
};

template 
struct make_integer_sequence_impl
{ using type = integer_sequence; };

template 
using make_integer_sequence = typename make_integer_sequence_impl::type;
Комментарии (0)