Implementazione C ++ 14 make_integer_sequence

Ho cercato di implementare il modello di alias C ++ 14 make_integer_sequence , che semplifica la creazione del modello di class integer_sequence .

 template struct integer_sequence { typedef T value_type; static constexpr size_t size() noexcept { return sizeof...(I) ; } }; template using make_integer_sequence = integer_sequence; // only for illustration. 

Per implementare make_integer_sequence abbiamo bisogno di una struttura helper make_helper .

 template using make_integer_sequence = typename make_helper::type; 

L’implementazione di make_helper non è troppo difficile.

 template struct make_helper { typedef typename mpl::if_< T(0) == N, mpl::identity< integer_sequence >, make_helper >::type; }; 

Per testare make_integer_sequence ho creato questa funzione principale:

 int main() { #define GEN(z,n,temp) \ typedef make_integer_sequence BOOST_PP_CAT(int_seq,n) ; BOOST_PP_REPEAT(256, GEN, ~); } 

Ho compilato il programma con GCC 4.8.0, su un sistema i5 quad-core con 8 GB di RAM. La compilazione riuscita ha richiesto 4 secondi.

Ma, quando ho cambiato la macro GEN in:

 int main() { #define GEN(z,n,temp) \ typedef make_integer_sequence BOOST_PP_CAT(int_seq, n) ; BOOST_PP_REPEAT(256, GEN, ~ ); } 

La compilazione non è andata a buon fine e ha emesso il messaggio di errore:

memoria virtuale esaurita.

Qualcuno potrebbe spiegare questo errore e cosa lo ha causato?

MODIFICARE:

Ho semplificato il test per:

 int main() { typedef make_integer_sequence int_seq4096; } 

Ho quindi compilato con successo GCC 4.8.0 -ftemplate-depth = 65536.

Comunque questo secondo test:

 int main() { typedef make_integer_sequence int_seq16384; } 

Non è stato compilato con GCC 4.8.0 -ftemplate-depth = 65536 e ha generato l’errore:

memoria virtuale esaurita.

Quindi, la mia domanda è, come faccio a ridurre l’istanziazione profonda del template?

Saluti, Khurshid.

Ecco un’implementazione di log N che non richiede nemmeno un aumento della profondità massima per le istanze dei template e la compilazione abbastanza veloce:

 // using aliases for cleaner syntax template using Invoke = typename T::type; template struct seq{ using type = seq; }; template struct concat; template struct concat, seq> : seq{}; template using Concat = Invoke>; template struct gen_seq; template using GenSeq = Invoke>; template struct gen_seq : Concat, GenSeq>{}; template<> struct gen_seq<0> : seq<>{}; template<> struct gen_seq<1> : seq<0>{}; 

Questo è fondamentalmente il mio modo di hackerare la soluzione di Xeo: realizzare un wiki per la comunità: se si vuole apprezzare, si prega di aggiornare Xeo .

… appena modificato fino a quando ho sentito che non poteva ottenere alcun più semplice, rinominato e aggiunto value_type e size() per lo standard (ma facendo solo index_sequence non integer_sequence ), e il codice che funziona con GCC 5.2 -std=c++14 potrebbe sono altrimenti inalterato con vecchi / altri compilatori con cui sono bloccato. Potrebbe salvare qualcuno un po ‘di tempo / confusione.

 // 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> : index_sequence { }; // -------------------------------------------------------------- template  struct make_index_sequence : _merge_and_renumber::type, typename make_index_sequence::type> { }; template<> struct make_index_sequence<0> : index_sequence<> { }; template<> struct make_index_sequence<1> : index_sequence<0> { }; } 

Gli appunti:

  • la “magia” della soluzione di Xeo è nella dichiarazione di _merge_and_renumber ( concat nel suo codice) con esattamente due parametri, mentre la specilisation espone efficacemente i loro singoli pacchetti di parametri

  • il typename::type in …

     struct make_index_sequence : _merge_and_renumber::type, typename make_index_sequence::type> 

evita l’errore:

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

Ho trovato la versione molto veloce e inutile della ricorsione profonda dell’implementazione di make_index_sequence . Nel mio PC si 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  // 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. 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::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(){} 

Ti manca un -1 qui:

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

in particolare:

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

Successivamente, il primo ramo non dovrebbe essere integer_sequence , ma piuttosto integer_sequence .

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

che dovrebbe essere sufficiente per compilare il codice originale.

In generale, quando si scrive metaprogrammazione template seria, l’objective principale dovrebbe essere quello di mantenere bassa la profondità dell’istanza del template . Un modo per pensare a questo problema è immaginare di avere un computer a thread infinito: ogni calcolo indipendente dovrebbe essere mescolato con il suo thread, quindi mescolato insieme alla fine. Hai alcune operazioni che richiedono profondità O (1), come ... espansione: sfruttale.

Di solito, è sufficiente tirare la profondità logaritmica, perché con una profondità di 900 , ciò consente strutture di dimensioni 2^900 e qualcos’altro si rompe per primo. (Per essere onesti, è più probabile che succedano 90 livelli diversi di strutture di dimensioni 2^10 ).

Ecco un’altra variazione leggermente più generale della risposta logaritmica di Xeo che fornisce make_integer_sequence per tipi arbitrari. Questo viene fatto usando std::integral_constant per evitare il temuto “argomento template coinvolge parametri parametri”.

 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

Semplice implementazione O (N). Probabilmente non è quello che vuoi per N di grandi dimensioni, ma la mia applicazione è solo per chiamare funzioni con argomenti indicizzati, e non mi aspetterei un’arità di più di circa 10. Non ho compilato i membri di integer_sequence. Non vedo l’ora di utilizzare un’implementazione di libreria standard e nuking this 🙂

 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>::type; }; template  struct make_integer_sequence_impl::type> { using type = integer_sequence; }; template  using make_integer_sequence = typename make_integer_sequence_impl::type;