Implementasi C++14 make_integer_sequence

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.

JulianAustralia
Pertanyaan edit 2 Juli 2015 в 11:44
Pemrograman
gcc c++ c++11 c++14
2 Juli 2013 в 11:31
13 tayangan
Mengomentari pertanyaan (1)
Larutan

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

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

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'
magras
Jawaban edit 17 Juni 2016 в 2:33
Komentar (3)

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  // 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
Jawaban edit 22 Oktober 2014 в 2:48
Komentar (0)

Anda kehilangan -1 di sini:

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

secara khusus:

typedef typename mpl::if_< T(0) == N,  
              mpl::identity< integer_sequence >,
              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 >,
              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).

Komentar (0)

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

Demo: coliru

joki
Jawaban edit 25 April 2018 в 10:46
Komentar (0)

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 
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;
Komentar (0)