C ++ d’implémentation 14 make_integer_sequence

J’ai essayé d’implémenter le modèle d’alias C ++ 14 make_integer_sequence , qui simplifie la création du modèle de classe 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. 

Pour implémenter make_integer_sequence nous avons besoin d’une structure d’assistance make_helper .

 template using make_integer_sequence = typename make_helper::type; 

Implémenter make_helper n’est pas trop difficile.

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

Pour tester make_integer_sequence j’ai fait cette fonction principale:

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

J’ai compilé le programme avec GCC 4.8.0, sur un système i5 quad-core avec 8 Go de RAM. Une compilation réussie a pris 4 secondes.

Mais quand j’ai changé la macro GEN pour:

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

La compilation a échoué et le message d’erreur est sorti:

mémoire virtuelle épuisée.

Quelqu’un pourrait-il expliquer cette erreur et quelle en est la cause?

MODIFIER:

J’ai simplifié le test pour:

 int main() { typedef make_integer_sequence int_seq4096; } 

J’ai ensuite compilé avec succès avec GCC 4.8.0 -ftemplate-depth = 65536.

Cependant ce second test:

 int main() { typedef make_integer_sequence int_seq16384; } 

N’a pas compilé avec GCC 4.8.0 -ftemplate-depth = 65536 et a entraîné l’erreur:

mémoire virtuelle épuisée.

Alors, ma question est la suivante: comment puis-je diminuer l’instanciation profonde d’un modèle?

Cordialement, Khurshid.

Voici une implémentation log N qui n’a même pas besoin d’une profondeur maximale accrue pour les instanciations de modèles et qui comstack assez rapidement:

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

Il s’agit essentiellement de pirater la solution de Xeo: Créer un wiki de communauté – si vous appréciez, révélez Xeo .

… juste modifié jusqu’à ce que je pense qu’il ne pourrait pas être plus simple, renommé et ajouté value_type et size() selon le standard (mais seulement faire index_sequence pas index_sequence ), et le code fonctionnant avec GCC 5.2 -std=c++14 pourrait exécuter autrement inchangé sous les anciens / autres compilateurs avec lesquels je suis coincé. Sauver quelqu’un de temps / confusion.

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

Remarques:

  • la “magie” de la solution de Xeo se trouve dans la déclaration de _merge_and_renumber ( concat dans son code) avec exactement deux parameters, alors que la spécification expose efficacement leurs paquets de parameters individuels

  • le typename::type dans …

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

évite l’erreur:

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

J’ai trouvé une version de récursivité profonde et rapide de l’implémentation de make_index_sequence . Dans mon PC, il comstack avec N = 1 048 576, avec 2 s. (PC: Centos 6.4 x86, i5, 8 Go de 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(){} 

Il vous manque un -1 ici:

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

en particulier:

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

Ensuite, la première twig ne doit pas être integer_sequence , mais plutôt integer_sequence .

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

ce qui devrait être suffisant pour obtenir votre code original à comstackr.

En général, lors de l’écriture d’une métaprogrammation de template sérieuse, votre objective principal devrait être de garder la profondeur de l’instanciation du template . Une façon de penser à ce problème est d’imaginer que vous avez un ordinateur à thread infini: chaque calcul indépendant doit être mélangé sur son propre thread, puis mélangé à la fin. Vous avez quelques opérations qui prennent la profondeur O (1), comme ... expansion: exploitez-les.

En général, il suffit de tirer une profondeur logarithmique, car avec une profondeur de 900 , cela permet des structures de 2^900 unités, et autre chose en premier. (Pour être juste, ce qui est plus susceptible de se produire, c’est 90 couches différentes de structures de taille 2^10 ).

Voici une autre variante légèrement plus générale de la réponse logarithmique de Xeo qui fournit make_integer_sequence pour les types arbitraires. Ceci est fait en utilisant std::integral_constant afin d’éviter l’erreur redoutée de “l’argument de modèle implique le paramètre de modèle”.

 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; 

Démo: coliru

Implémentation simple O (N). Probablement pas ce que vous voulez pour un grand N, mais mon application ne sert qu’à appeler des fonctions avec des arguments indexés, et je ne m’attendrais pas à une arité supérieure à environ 10. Je n’ai pas renseigné les membres de integer_sequence. Je suis impatient d’utiliser une implémentation de bibliothèque standard et de 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;