Saya mencoba untuk menerapkan C++14 alias template make_integer_sequence
, yang menyederhanakan penciptaan kelas 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.
Untuk melaksanakan make_integer_sequence
kita butuh penolong struktur make_helper
.
template< class T , class N >
using make_integer_sequence = typename make_helper<T,N>::type;
Menerapkan make_helper
isn't terlalu sulit.
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;
};
Untuk menguji make_integer_sequence
saya membuat ini fungsi utama:
int main()
{
#define GEN(z,n,temp) \
typedef make_integer_sequence< int, n > BOOST_PP_CAT(int_seq,n) ;
BOOST_PP_REPEAT(256, GEN, ~);
}
Aku menyusun program dengan GCC 4.8.0, quad-core i5 dengan sistem 8GBs RAM. Kompilasi sukses mengambil 4 detik.
Tapi, ketika saya mengubah GEN makro untuk:
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, ~ );
}
Kompilasi tidak berhasil dan ditampilkan pesan kesalahan:
virtual memori habis.
Bisakah seseorang menjelaskan kesalahan ini dan apa yang menyebabkannya?
EDIT:
Aku disederhanakan tes ke:
int main()
{
typedef make_integer_sequence< int, 4096 > int_seq4096;
}
Saya kemudian berhasil dikompilasi dengan GCC 4.8.0 -ftemplate-kedalaman=65536.
Namun yang kedua ini test:
int main()
{
typedef make_integer_sequence< int, 16384 > int_seq16384;
}
Tidak di compile dengan GCC 4.8.0 -ftemplate-kedalaman=65536, dan mengakibatkan kesalahan:
virtual memori habis.
Jadi, pertanyaan saya adalah, bagaimana cara menurunkan template dalam instansiasi?
Salam, Khurshid.
Berikut ini's log N
implementasi yang doesn't bahkan perlu peningkatan max mendalam untuk template instantiasi dan mengkompilasi cukup cepat:
// 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>{};
Ini pada dasarnya adalah saya hacking sekitar Xeo's solusi: Membuat komunitas wiki - jika apresiatif, mohon upvote Xeo.
...hanya dimodifikasi sampai aku merasa itu tidak't mendapatkan lebih sederhana, berganti nama dan menambahkan value_type
dan size()
per Standar (tapi hanya melakukan index_sequence
tidak integer_sequence
), dan kode bekerja dengan GCC 5.2 -std=c++14
bisa berjalan jika tidak berubah di bawah lebih tua/lain-lain penyusun I'm terjebak dengan. Mungkin menyelamatkan seseorang beberapa waktu / kebingungan.
// 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> { };
}
Catatan:
"sihir" dari Xeo's solusi dalam deklarasi _merge_and_renumber
(concat
di kode nya) dengan tepat dua parameter, sedangkan specilisation efektif menghadapkan mereka masing-masing parameter paket
the typename
...::tipe
di...
struct make_index_sequence : _merge_and_renumber<typename make_index_sequence<N/2>::jenis, typename make_index_sequence<N - N/2>::jenis>
menghindari kesalahan:
invalid use of incomplete type 'struct std::_merge_and_renumber<std::make_index_sequence<1ul>, std::index_sequence<0ul> >'
Saya menemukan sangat cepat dan tak jauh rekursi versi dari pelaksanaan make_index_sequence
. Di PC saya mengkompilasi dengan N = 1 048 576 , dengan 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(){}
Anda kehilangan -1
di sini:
typedef typename mpl::if_< T(0) == N,
mpl::identity< integer_sequence<T> >,
make_helper< T, N, N-1,I...>
>::type;
secara khusus:
typedef typename mpl::if_< T(0) == N,
mpl::identity< integer_sequence<T> >,
make_helper< T, N-1, N-1,I...>
>::type;
Selanjutnya, cabang pertama seharusnya't integer_sequence<T>
, melainkan integer_sequence<T, aku...>
.
typedef typename mpl::if_< T(0) == N,
mpl::identity< integer_sequence<T, I...> >,
make_helper< T, N-1, N-1,I...>
>::type;
yang harus cukup untuk mendapatkan anda asli kode untuk mengkompilasi.
Secara umum, ketika menulis serius template
metaprogramming, tujuan utama anda harus menjaga kedalaman template
instansiasi turun. Cara untuk berpikir tentang masalah ini adalah membayangkan anda memiliki pilihan yang tak terbatas-benang komputer: setiap perhitungan independen harus dikocok lepas ke thread sendiri, kemudian dikocok bersama-sama di akhir. Anda memiliki beberapa operasi yang mengambil O(1) kedalaman, seperti ...
ekspansi: mengeksploitasi mereka.
Biasanya, menarik logaritma kedalaman yang cukup, karena dengan 900
mendalam, yang memungkinkan 2^900
berukuran struktur, dan sesuatu yang lain istirahat pertama. (Untuk menjadi adil, apa yang lebih mungkin terjadi adalah 90 lapisan yang berbeda dari 2^10
berukuran struktur).
Berikut ini adalah sedikit lebih umum variasi Xeo's logaritma jawaban yang menyediakan make_integer_sequence
untuk sewenang-wenang jenis. Hal ini dilakukan dengan menggunakan std::integral_constant
dalam rangka untuk menghindari ditakuti "argumen template yang melibatkan parameter template" kesalahan.
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
Implementasi sederhana O(N). Mungkin bukan apa yang anda inginkan untuk besar N, tapi saya aplikasi ini hanya untuk memanggil fungsi dengan diindeks argumen, dan saya tidak't mengharapkan tual membaca, keakraban lebih dari sekitar 10. Aku ingin't diisi anggota integer_sequence. I'm looking forward untuk menggunakan library standar pelaksanaan dan nuking ini :)
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;