Реализация C++14 make_integer_sequence
Я пытался реализовать шаблон псевдонима 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 не так уж сложно
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 с 8 ГБ ОЗУ. Успешная компиляция заняла 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, ~ );
}
Компиляция не удалась и вывел сообщение об ошибке:
виртуальная память исчерпана.
Может ли кто-нибудь объяснить эту ошибку и чем она вызвана?
РЕДАКТИРОВАТЬ:
Я упростил тест до:
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, и привел к ошибке:
виртуальная память исчерпана.
Итак, мой вопрос, как мне уменьшить глубину создания шаблона?
С уважением, Хуршид.
8 ответов
Вот 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>{};
По сути, это я взломал решение Xeo: создание вики для сообщества - если вы благодарны, пожалуйста, проголосуйте за Xeo.
... просто изменил, пока я не почувствовал, что это не может быть проще, переименован и добавлен value_type а также size() в соответствии со стандартом (но только делая index_sequence не integer_sequence) и код, работающий с GCC 5.2 -std=c++14 в противном случае может работать без изменений под старыми / другими компиляторами, с которыми я застрял. Может сэкономить кому-то время / путаницу.
// based on http://stackru.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> >'
Я нашел очень быструю и ненужную глубокую рекурсивную версию реализации make_index_sequence, В моем ПК он компилируется с N = 1 048 576, с 2 с.
(ПК: Centos 6.4 x86, i5, 8 Гб ОЗУ, 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(){}
Вот еще один более общий вариант логарифмического ответа 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>;
Демо: колиру
Вам не хватает -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 размерные структуры).
Простая реализация O(N). Вероятно, не то, что вы хотите для большого N, но мое приложение предназначено только для вызова функций с индексированными аргументами, и я не ожидал бы, что арность больше, чем около 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;
Вот еще одна техника реализации (для
T=size_t), он использует 17-кратные выражения C++ и побитовую генерацию (т.е.
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;
Вот очень простое решение, реализованное с рекурсией на основе диспетчеризации тегов.
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.