Implementierung C++14 make_integer_sequence

Lesezeit: 13 Minuten

Implementierung C14 make integer sequence
Khurshid

Ich habe versucht, die umzusetzen C++14 Alias-Vorlage make_integer_sequencewas die Erstellung der Klassenvorlage vereinfacht 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.

Implementieren make_integer_sequence Wir brauchen eine Hilfsstruktur make_helper.

template< class T , class N >
using make_integer_sequence = typename make_helper<T,N>::type;

Implementieren make_helper ist nicht allzu schwierig.

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

Zu testen make_integer_sequence Ich habe diese Hauptfunktion gemacht:

int main()
{
    #define GEN(z,n,temp)   \
     typedef make_integer_sequence< int, n >  BOOST_PP_CAT(int_seq,n) ;

   BOOST_PP_REPEAT(256, GEN, ~);
}

Ich habe das Programm mit GCC 4.8.0 auf einem Quad-Core-i5-System mit 8 GB RAM kompiliert. Die erfolgreiche Kompilierung dauerte 4 Sekunden.

Aber als ich das GEN-Makro geändert habe in:

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, ~ );
}

Die Kompilierung war nicht erfolgreich und es wurde die Fehlermeldung ausgegeben:

virtueller Speicher erschöpft.

Kann mir jemand diesen Fehler erklären und was ihn verursacht hat?

BEARBEITEN:

Ich habe den Test vereinfacht zu:

int main()
{
   typedef make_integer_sequence< int, 4096 > int_seq4096;
}

Ich habe dann erfolgreich mit GCC 4.8.0 -ftemplate-depth=65536 kompiliert.

Aber dieser zweite Test:

int main()
{
    typedef make_integer_sequence< int, 16384 > int_seq16384;
}

Konnte nicht mit GCC 4.8.0 -ftemplate-depth=65536 kompiliert werden und führte zu folgendem Fehler:

virtueller Speicher erschöpft.

Meine Frage ist also, wie kann ich die tiefe Instanziierung von Vorlagen verringern?

Grüße, Khurshid.

  • In einem Vortrag von STlavavej glaube ich gehört zu haben, dass der Microsoft-Compiler einen Hook generieren muss make_integer_sequence automatisch (im Grunde?) in O (1). Die Ironie ist, dass man viel daran arbeitet, dies für etwas zu implementieren, das ein Compiler möglicherweise selbst produziert.

    – alfC

    13. Mai 2017 um 5:57 Uhr

Hier ist ein log N Implementierung, die nicht einmal eine erhöhte maximale Tiefe für Vorlageninstanziierungen benötigt und ziemlich schnell kompiliert:

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

  • Sehr schön! Ich würde nur präzisieren, dass die Tiefe der Instanziierungen ist O(log N) (Die Anzahl der Operationen ist O(N)). In jedem Fall ist dies eine sehr schnelle Implementierung.

    – Cassio Neri

    2. Juli 2013 um 13:50 Uhr

  • @Xeo würde ich lesen Concat als “nimm zwei Listen und lege sie hintereinander”. Hinzufügen von “und addieren Sie die Länge der Liste ganz links zum Inhalt der Liste ganz rechts” zu what Concat würde mich überraschen. template<class S, unsigned I=1> struct inc; template<unsigned... Is, unsigned I> struct inc<seq<Is...>, I>:seq<(Is+I)...> {}; template<class S, unsigned I=1> using Inc=Invoke<inc<S,I>>; dann template<unsigned N>struct gen_seq:Concat<GenSeq<N/2>, Inc<GenSeq<N-N/2>,N/2>>{};wo Concat nichts zur zweiten Liste hinzufügt, würde diese Operation von der Verkettung entkoppeln.

    – Yakk – Adam Nevraumont

    4. Juli 2013 um 12:17 Uhr


  • Ich hatte Probleme mit diesem Code und erkannte dann, dass ich ihn verwenden sollte GenSeqnicht gen_seqzum make_index_sequence.

    – jcai

    7. Juli 2015 um 14:42 Uhr

  • Aus Experimenten mit einer ähnlichen Implementierung habe ich herausgefunden, dass die sizeof...(I1) in concat ist ziemlich ineffizient (zumindest für g++) und kann verbessert werden, indem diese Zahl in übergeben wird concat anstatt es neu zu berechnen.

    – Jonathan Wakely

    17. November 2015 um 20:41 Uhr


  • Darf ich um ein Beispiel bitten, wie man das benutzt?

    – Martin Bonner unterstützt Monika

    2. Juni 2017 um 11:58 Uhr

Im Grunde hacke ich hier um die Lösung von Xeo herum: Erstellen eines Community-Wikis – wenn Sie es wertschätzen, bitte stimme Xeo zu.

…nur modifiziert, bis ich das Gefühl hatte, es könnte nicht einfacher werden, umbenannt und hinzugefügt value_type und size() gemäß dem Standard (aber nur dabei index_sequence nicht integer_sequence) und Code, der mit GCC 5.2 funktioniert -std=c++14 ansonsten unverändert unter älteren/anderen Compilern laufen könnte, bei denen ich feststecke. Könnte jemandem etwas Zeit / Verwirrung ersparen.

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

Anmerkungen:

  • Die “Magie” der Lösung von Xeo liegt in der Deklaration von _merge_and_renumber (concat in seinem Code) mit genau zwei Parametern, während die Spezialisierung effektiv ihre individuellen Parameterpakete offenlegt

  • der typename::type in…

    struct make_index_sequence
      : _merge_and_renumber<typename make_index_sequence<N/2>::type,
                            typename make_index_sequence<N - N/2>::type>
    

vermeidet den Fehler:

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

  • Warum ist das index_sequence eher, als integer_sequence?

    – einpoklum

    8. Dezember 2016 um 15:23 Uhr


  • @einpoklum: weil integer_sequence muss der Datentyp ein Vorlagenparameter sein, während ich fest codiert habe size_twas mir damals ganz gut gepasst hat….

    – Toni Delroy

    19. Dezember 2016 um 23:10 Uhr

  • @einpoklum Um Tonys Antwort ein kleines Detail hinzuzufügen: Sie können sich nicht teilweise auf ein Vorlagenargument eines Vorlagentyps spezialisieren. Sie können integer_sequence auf diese Weise nicht implementieren. Das Beste, was Sie tun können, um integer_sequence zu erhalten, ist, sich vollständig auf jeden Integer-Typ zu spezialisieren. (diese Codelänge für jeden ganzzahligen Typ)

    – David

    30. Juni 2017 um 0:13 Uhr


Implementierung C14 make integer sequence
Khurshid

Ich fand eine sehr schnelle und unnötig tiefe Rekursionsversion der Implementierung von make_index_sequence. In meinem PC kompiliert es mit N = 1 048 576 , mit 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(){}

Ihnen fehlt ein -1 Hier:

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

bestimmtes:

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

Als nächstes sollte der erste Zweig nicht sein integer_sequence<T>sondern eher 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;

was ausreichen sollte, um Ihren ursprünglichen Code zum Kompilieren zu bringen.

Im Allgemeinen beim Schreiben ernst template Metaprogrammierung, Ihr Hauptziel sollte es sein, die Tiefe von zu behalten template Instanziierung herunter. Eine Möglichkeit, über dieses Problem nachzudenken, besteht darin, sich vorzustellen, Sie hätten einen Computer mit unendlichen Threads: Jede unabhängige Berechnung sollte in einen eigenen Thread verschoben und am Ende zusammengemischt werden. Sie haben ein paar Operationen, die O(1)-Tiefe benötigen, wie z ... Erweiterung: sie ausnutzen.

Üblicherweise reicht das Ziehen der logarithmischen Tiefe aus, denn mit a 900 Tiefe, das erlaubt 2^900 Größe Strukturen, und etwas anderes bricht zuerst. (Um fair zu sein, was wahrscheinlicher ist, sind 90 verschiedene Schichten von 2^10 große Strukturen).

Implementierung C14 make integer sequence
Spaß

Hier ist eine weitere etwas allgemeinere Variante der logarithmischen Antwort von Xeo, die liefert make_integer_sequence für beliebige Typen. Dies geschieht durch Verwendung std::integral_constant um den gefürchteten Fehler “Vorlagenargument beinhaltet Vorlagenparameter” zu vermeiden.

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

1647138613 875 Implementierung C14 make integer sequence
cdyson37

Einfache Implementierung O(N). Wahrscheinlich nicht das, was Sie für große N wollen, aber meine Anwendung dient nur zum Aufrufen von Funktionen mit indizierten Argumenten, und ich würde keine Arität von mehr als etwa 10 erwarten. Ich habe die Mitglieder von integer_sequence nicht ausgefüllt. Ich freue mich darauf, eine Standardbibliotheksimplementierung zu verwenden und dies zu vernichten 🙂

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;

Hier ist eine andere Implementierungstechnik (z T=size_t), verwendet es C++17-Fold-Ausdrücke und bitweise Generierung (d. h 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;

995700cookie-checkImplementierung C++14 make_integer_sequence

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy