3. campers TMP-Aufgabe(n): 7

campers TMP-Aufgabe(n): 7

  • S

    Hi,

    mir war langweilig, also habe ich mich an die Aufgaben von camper gemacht. Die letzte war die pfiffigste.

    Von http://www.c-plusplus.net/forum/291117-full

    camper schrieb:

    7. Erstelle eine Templatemetafunktion, die eine Liste erzeugt, in der die Elemente der ersten Liste sooft wiederholt werden, wie das korrespondierende Element der zweiten Liste vorgibt
    F<<0,1,2>,<3,1,2>> -> <0,0,0,1,2,2>

    template<int ... args>
struct index_list
{
    typedef index_list identity;
    static constexpr int arr[]{args...};
};
template<int ... args>
constexpr int index_list<args...>::arr[];

template<typename, typename> struct concat;
template<int ... args1, int ... args2>
struct concat<index_list<args1...>, index_list<args2...>> : index_list<args1..., args2...> {};

template<typename list1, typename ... lists>
struct concat_variadic : concat<typename list1::identity, typename concat_variadic<lists...>::identity> {};
template<typename list1>
struct concat_variadic<list1> : list1 {};

template<int val, int N>
struct repeat : concat<index_list<val>, typename repeat<val, N-1>::identity> {};
template<int val>
struct repeat<val, 0> : index_list<> {};

template<typename, typename> struct multiply;
template<int ... values, int ... repeats>
struct multiply<index_list<values...>, index_list<repeats...>> : concat_variadic<typename repeat<values, repeats>::identity ...> {};

#include <iostream>
#include <iterator>

int main()
{
    typedef multiply<index_list<48, 5>, index_list<3, 2>> mul;
    std::copy(std::begin(mul::arr), std::end(mul::arr), std::ostream_iterator<int>(std::cout, ", "));
}

    Dass man eine Identity für index_list braucht, ist witzig. Ich bin da drauf gekommen und hab dann bemerkt, dass camper schon ein identity -Template für genau das hatte.

    camper: Haste mehr? Sind tolle Aufgaben zum Zeitvertreib 👍

    0
  • O

    wie wäre s damit, sinnvolle Projekte zu starten? 🙂 Schreib doch ein kleines Computerspiel, dann wirst du zumindest ein besserer Programmierer 🙂

    0
  • S

    otze schrieb:

    wie wäre s damit, sinnvolle Projekte zu starten? 🙂 Schreib doch ein kleines Computerspiel, dann wirst du zumindest ein besserer Programmierer 🙂

    Hab ich doch letztens.
    http://sourceforge.net/projects/linacsim/
    (Code ist nicht ganz aktuell. Muss ich mal wieder updaten)

    0
  • C
    Mod

    Sone schrieb:

    camper: Haste mehr? Sind tolle Aufgaben zum Zeitvertreib 👍

    Kleine Abwandlung:
    gegeben seien bereits drei templates
    tag<N> - leer, erbt direkt von tag<N-1>; tag<0> hat keine Basisklasse
    make_indexes<N> erzeugt index_list 0,1,...,N-1
    und
    partial_sum<index_list> erzeugt partial_summen <1,4,3,2> -> <1,5,8,10>
    Formuliere jetzt multiply ohne (explizite) Rekursion.
    Bonus: formuliere partial_sum ohne explizite Rekursion (schwer: habe selbst keinen Lösungsweg parat, ist also ggf. nicht möglich habe eine Lösung, funktioniert aber nur mit clang)

    0
  • S

    camper schrieb:

    Bonus: formuliere partial_sum ohne explizite Rekursion (schwer: habe selbst keinen Lösungsweg parat, ist also ggf. nicht möglich habe eine Lösung, funktioniert aber nur mit clang)

    Mit Boost-PP, dem Trick mit den expliziten Spezialisierungen? Oder tatsächlich rein durch Templates, und ohne sichtliche Rekursion?
    (Edit: Ja, ich sitze hier und denke.)

    0
  • C
    Mod

    Sone schrieb:

    camper schrieb:

    Bonus: formuliere partial_sum ohne explizite Rekursion (schwer: habe selbst keinen Lösungsweg parat, ist also ggf. nicht möglich habe eine Lösung, funktioniert aber nur mit clang)

    Mit Boost-PP, dem Trick mit den expliziten Spezialisierungen? Oder tatsächlich rein durch Templates, und ohne sichtliche Rekursion?
    (Edit: Ja, ich sitze hier und denke.)

    An den Präprozessor habe ich nicht gedacht, aber wenn du damit etwas anstellen kannst, wäre das trotzdem interessant.

    0
  • S

    camper schrieb:

    Sone schrieb:

    camper schrieb:

    Bonus: formuliere partial_sum ohne explizite Rekursion (schwer: habe selbst keinen Lösungsweg parat, ist also ggf. nicht möglich habe eine Lösung, funktioniert aber nur mit clang)

    Mit Boost-PP, dem Trick mit den expliziten Spezialisierungen? Oder tatsächlich rein durch Templates, und ohne sichtliche Rekursion?
    (Edit: Ja, ich sitze hier und denke.)

    An den Präprozessor habe ich nicht gedacht, aber wenn du damit etwas anstellen kannst, wäre das trotzdem interessant.

    Noch eine Frage. Was verstehst du unter "expliziter" Rekursion? Darf es überhaupt keine Rekursion geben?

    Naja, BOOST_PP_LIMIT_REPEAT ist 256, nicht 1024 - daher wäre das technisch gesehen keine Standard-konforme und natürlich auch keine schöne Lösung.

    0
  • C
    Mod

    Sone schrieb:

    Was verstehst du unter "expliziter" Rekursion? Darf es überhaupt keine Rekursion geben?

    An irgendeinem Punkt des Algorithmus ist Rekursion unvermeidbar. Gemeint ist die Aufgabe so, dass diese Rekursion ausschließlich in den gegebenen Templates stattfindet.

    Das hat einen praktischen Grund: Ein rekursives Template mit einem Parameterpack hat typischerweise O(N^2)-Komplexität in Bezug auf den Speicherverbrauch beim Compilieren (ab einem gewissen Punkt wird der Speichverbrauch durch das bloße Aufzählen der Argumente dominiert). Das ist also etwas, was man u.U. vermeiden möchte, weshalb es sinnvoll sein kann, nach Alternativen zu suchen.

    0
  • ?

    camper schrieb:

    Das hat einen praktischen Grund: Ein rekursives Template mit einem Parameterpack hat typischerweise O(N^2)-Komplexität in Bezug auf den Speicherverbrauch beim Compilieren (ab einem gewissen Punkt wird der Speichverbrauch durch das bloße Aufzählen der Argumente dominiert). Das ist also etwas, was man u.U. vermeiden möchte, weshalb es sinnvoll sein kann, nach Alternativen zu suchen.

    Ob es jetzt so viel besser ist, von einer Typliste mit O(N) Typen abzuleiten, die selber jeweils von O(N) Klassen abzuleiten und insgesamt O(N) Memberfunktionen haben die sich der Reihe nach aufrufen, was O(N^2*index_list(N)) ergibt, oder einfach eine explizite Rekursion aufzuschreiben -- es hilft jedenfalls dabei, in langen Sätzen zu denken und selbst bei langen Templateketten nicht den Faden zu verlieren, war wirklich eine nette Übung.

    0
  • T

    Hmm ich hätte auch gerne C++ Aufgaben zum Zeitvertreib, aber etwas weniger anspruchsvoll aber doch anspruchsvoller als die ganzen C++ Anfängeraufgaben im Netz. Weiß da jemand etwas?

    0
  • S

    camper schrieb:

    Sone schrieb:

    Was verstehst du unter "expliziter" Rekursion? Darf es überhaupt keine Rekursion geben?

    An irgendeinem Punkt des Algorithmus ist Rekursion unvermeidbar.

    Ja, genau das wollte ich gerade schreiben. Jede Iteration braucht Rekursion, das ist bei TMP anders nicht möglich; Wenn ein bestimmter Wert durch Iteration berechnet werden soll, muss Rekursion auftreten.

    Das heißt, es darf genau eine rekursive Funktion geben,.... hmm.
    Ich wollte zuerst

    template<int counter, int first, int ... args>
struct accumulate : std::integral_constant<int, first + (counter > 0 ?  accumulate<counter-1, args...>::value : 0 )> {};
template<int counter, int first>
struct accumulate<counter, first> : std::integral_constant<int, first> {};

template<typename,
         typename>
struct partial_sum_impl;

template<int ... values,
         int ... indices>
struct partial_sum_impl<index_list<values...>, index_list<indices...>> : index_list< accumulate<sizeof...(indices) - indices - 1, values...>::value...> {};

template<int ... args>
struct partial_sum : partial_sum_impl<index_list<args...>, typename make_indices<sizeof...(args) - 1>::identity> {};

    Bringen, aber da ist make_indices und accumulate rekursiv. Stopp: make_indices zählt nicht, da, wenn ich es so implementiere:

    template<int N>
struct make_indices : concat<index_list<N>, typename make_indices<N-1>::identity> {};
template<>
struct make_indices<0> : index_list<0> {};

    Natürlich nichts mit variadic templates zu statten geht. Daher ist das eigentlich entsprechend der Aufgabe.
    (Edit: Nein, du willst ja ableiten mit parameter packs vollständig vermeiden. Hmm. Ich denke)

    Und hier würde auch deine Grammatik mit den Operatoren sehr gut passen.
    args + ...
    :träum:

    0
  • S

    TNA schrieb:

    Hmm ich hätte auch gerne C++ Aufgaben zum Zeitvertreib, aber etwas weniger anspruchsvoll aber doch anspruchsvoller als die ganzen C++ Anfängeraufgaben im Netz. Weiß da jemand etwas?

    http://trainyourprogrammer.de/?

    0
  • S

    Bzw. wenn bei der rekursiven Addition nicht diese eine letzte Basisklasse unnötig instantiiert werden soll, geht auch eine weitere partielle Spezialisierung mit SFINAE:

    template<int counter, int first, int ... args>
struct accumulate : std::integral_constant<int, first + accumulate<counter-1, args...>::value> {};
template<int counter, typename std::enable_if<counter != 0, int>::type first>
struct accumulate<counter, first> : std::integral_constant<int, first> {};
template<int first, int ... args>
struct accumulate<0, first, args...> : std::integral_constant<int, first> {};

    Man kann make_indices mit Boost-PP natürlich auch ein wenig effizienter schreiben, ob aber dadurch die Kompilierung schneller läuft ist fraglich, da der Compiler dann jedes mal durch alle Spezialisierungen gehen muss (256):

    template<int N>
struct make_indices : concat<index_list<N>, typename make_indices<N-1>::identity> {};

#include <boost/preprocessor.hpp>

#define specialize(z,N,t) \
    template<> \
    struct make_indices<N> : index_list<BOOST_PP_ENUM_PARAMS(N,)> {};
BOOST_PP_REPEAT(BOOST_PP_LIMIT_REPEAT, specialize,)

#undef number_text
#undef specialize

    Wenn man das hier nutzt muss man noch partial_sum :

    template<int ... args>
struct partial_sum :
    partial_sum_impl<index_list<args...>, typename make_indices<sizeof...(args)>::identity> {};

    Jetzt zum accumulate mit Boost-PP - etwas kniffliger:

    template<int counter, int ... args> struct accumulate{};

#define acc_expr(a, N, text) text##N
#define specialize(z,N,text) \
    template< BOOST_PP_ENUM_PARAMS(N, int param) BOOST_PP_COMMA_IF(N) int ... args> \
    struct accumulate<N, BOOST_PP_ENUM_PARAMS(N, param) BOOST_PP_COMMA_IF(N) args...> : std::integral_constant<int, 0 BOOST_PP_REPEAT(N, acc_expr, + N + 1 - param)> {};

BOOST_PP_REPEAT(BOOST_PP_LIMIT_REPEAT, specialize,)

    (Es wurde noch etwas abgeändert - siehe Code unten)
    Aber auch hier muss der Compiler alle Spezialisierungen prüfen, was also keinen Vorteil gegenüber dem ursprünglichen Problem bietet.

    Zusammen:

    #include <type_traits>

template<int ... args>
struct index_list
{
    typedef index_list identity;
    static constexpr int arr[]{args...};
};
template<int ... args>
constexpr int index_list<args...>::arr[];

template<typename, typename> struct concat;
template<int ... args1, int ... args2>
struct concat<index_list<args1...>, index_list<args2...>> : index_list<args1..., args2...> {};

template<int N>
struct make_indices : concat<index_list<N>, typename make_indices<N-1>::identity> {};

#include <boost/preprocessor.hpp>

#define specialize(z,N,t) \ 
    template<> \ 
    struct make_indices<N> : index_list<BOOST_PP_ENUM_PARAMS(N,)> {}; 
BOOST_PP_REPEAT(BOOST_PP_LIMIT_REPEAT, specialize,) 

#undef number_text
#undef specialize

template<int counter, int ... args> struct accumulate{};

#define acc_expr(a, N, text) text##N
#define specialize(z,N,text) \
    template< BOOST_PP_ENUM_PARAMS(N, int param) BOOST_PP_COMMA_IF(N) int ... args> \
    struct accumulate<N, BOOST_PP_ENUM_PARAMS(N, param) BOOST_PP_COMMA_IF(N) args...> : std::integral_constant<int, 0 BOOST_PP_REPEAT(N, acc_expr, + N + 1 - param)> {};

BOOST_PP_REPEAT(BOOST_PP_LIMIT_REPEAT, specialize,)

template<typename,
         typename>
struct partial_sum_impl;

template<int ... values,
         int ... indices>
struct partial_sum_impl<index_list<values...>, index_list<indices...>> :
    index_list< accumulate<sizeof...(indices) - indices, values...>::value...> {};

template<int ... args>
struct partial_sum :
    partial_sum_impl<index_list<args...>, typename make_indices<sizeof...(args)>::identity> {};

#include <iostream>
#include <iterator>

int main()
{
    typedef partial_sum<1, 2, 3, 4> mul;
    std::copy(std::begin(mul::arr), std::end(mul::arr), std::ostream_iterator<int>(std::cout, ", "));
}
    0
  • E

    Sone, wenn dir langweilig ist - ich hätte eine sogar sinnvolle TMP-Aufgabe für dich. :p
    Da ich so ne TMP-Niete bin kann ich nicht einschätzen ob dich das grob unterfordert oder nicht. Also:

    - Eine Liste von ints, die sortiert vorliegen. (Schön wäre es wenn ein static_assert feuert falls die Liste nicht sortiert ist) (Oder die Liste gleich per TMP-Quicksort sortieren? :p )
    - Die Liste bietet eine contains(int) Funktion an, die true zurück gibt wenn die gesuchte Zahl in der Liste enthalten ist. (Die gesuchte Zahl ist keine Compilezeit-Konstante)
    - Es wird nicht linear gesucht sondern per binärer Suche.
    - Die ganze binäre Suche ist über Template-Rekursion implementiert, dh. ohne for etc.

    Bsp:

    assert(search_list<1, 3, 12, 88, 177>::contains(7) == false);
assert(search_list<1, 3, 12, 88, 177>::contains(177) == true);

    Vermutlich wird man die search_list in 2 listen aufsplitten und auf die beiden contains() aufrufen.

    Das wäre unglaublich praktisch um mit minimalem Aufwand prüfen zu können ob ein Wert ein gültiger enum Wert ist oder nicht. Gibt sicher noch mehr nette Einsatzgebiete dafür...

    0
  • S

    Ethon schrieb:

    Sone, wenn dir langweilig ist - ich hätte eine sogar sinnvolle TMP-Aufgabe für dich. :p

    Ich lese gerade "Standard C++ IOStreams and Locales". 😉

    - Die ganze binäre Suche ist über Template-Rekursion implementiert, dh. ohne for etc.

    Das ist unmöglich. Wenn der Wert erst zur Laufzeit feststeht, muss auch mit Methoden zur Laufzeit gearbeitet werden. Was spricht gegen std::binary_search ?
    Ich würde da mit

    template<int first, int second, int ... args>
struct is_sorted : std::integral_constant<bool, is_sorted<first, second>::value && is_sorted<second, args...>::value> {};
template<int first, int second>
struct is_sorted<first, second> : std::integral_constant<bool, (first <= second)> {};

    prüfen und

    private:
    bool contains( int val, std::true_type )
    {
        // ...
    }

    bool contains( int val, std::false_type )
    {
        // ...
    }

public:
    bool contains( int val )
    {
        contains( val, std::integral_constant<bool, is_sorted<args...>::value> );
    }

    Bei index_list einfügen.

    0
  • C
    Mod

    - Die ganze binäre Suche ist über Template-Rekursion implementiert, dh. ohne for etc.

    Gemeint ist, dass (per Templaterekursion) eine Funktion zu implementieren ist, die zur Laufzeit prüft, ob ein erst dann bekannter Wert in einem bereits beim Compilieren vorliegenden Set vorkommen. Das ist selbstverständlich möglich. Das Splitten von Listen war, glaube ich, auch eine von meinen Aufgaben.

    template<int first, int second, int ... args>
struct is_sorted : std::integral_constant<bool, is_sorted<first, second>::value && is_sorted<second, args...>::value> {};
template<int first, int second>
struct is_sorted<first, second> : std::integral_constant<bool, (first <= second)> {};

    Das geht auch ohne Rekursion (analog zu all_same)

    Hast du mal gemessen, wie viel Zeit und Speicher dein Compiler für die partial_sum-Lösung benöigt ?

    0
  • ?

    Ist das etwa so gemeint?

    #include <cstddef>
#include <iostream>

template<int... numbers>            struct is_sorted                { static bool const value = true; }; // f. leere Liste
template<int x>                     struct is_sorted<x>             { static bool const value = true; };
template<int x, int y, int... tail> struct is_sorted<x, y, tail...> { static bool const value = x <= y && is_sorted<y, tail...>::value; };

template<template<int...> class list_template, typename so_far, int next> struct append_to_list;
template<template<int...> class list_template, int next, int... so_far>
struct append_to_list<list_template, list_template<so_far...>, next> {
  typedef list_template<so_far..., next> type;
};

template<template<int...> class list_template, typename so_far, std::size_t to_go, int next, int... tail>
struct sublist_front_builder {
  static_assert(to_go <= sizeof...(tail) + 1, "Liste nicht lang genug.");
  typedef typename sublist_front_builder<list_template,
                                         typename append_to_list<list_template, so_far, next>::type,
                                         to_go - 1,
                                         tail...>::type type;
};

template<template<int...> class list_template, typename so_far, int next, int... tail>
struct sublist_front_builder<list_template, so_far, static_cast<std::size_t>(0), next, tail...>
{
  typedef so_far type;
};

template<template<int...> class list_template, std::size_t pos, int next, int... tail>
struct sublist_back_builder
{
  static_assert(pos <= sizeof...(tail) + 1, "Liste nicht lang genug.");
  typedef typename sublist_back_builder<list_template, pos - 1, tail...>::type type;
  static int const front = sublist_back_builder<list_template, pos - 1, tail...>::front;
};

template<template<int...> class list_template, int next, int... tail>
struct sublist_back_builder<list_template, 0, next, tail...>
{
  static int const front = next;
  typedef list_template<next, tail...> type;
};

template<template<int...> class list_template, int... numbers>
struct bisect_list {
  static_assert(sizeof...(numbers) != 0, "Liste leer.");

  typedef typename sublist_front_builder<list_template, list_template<>, sizeof...(numbers) / 2, numbers...>::type first;
  typedef typename sublist_back_builder <list_template,                  sizeof...(numbers) / 2, numbers...>::type second;

  static int const middle = sublist_back_builder<list_template,         sizeof...(numbers) / 2, numbers...>::front;
};

template<int... numbers>     struct search_list             {
  static_assert(is_sorted<numbers...>::value, "Liste nicht sortiert.");

  static constexpr bool contains(int num) {
    typedef bisect_list<search_list, numbers...> bisect;

    return num < bisect::middle ? bisect::first::contains(num) : bisect::second::contains(num);
  }
};

template<>      struct search_list<>           { static constexpr bool contains(int    ) { return false; } };
template<int x> struct search_list<x>          { static constexpr bool contains(int num) { return num == x; } };

int main() {
  std::cout << search_list<2, 3, 5, 7, 11>::contains(7) << '\n'
            << search_list<2, 3, 5, 7, 11>::contains(9) << '\n'
            << search_list<2, 3, 5, 7, 11>::contains(5) << '\n'
    ;

  for(int i = 0; i < 20; ++i) {
    std::cout << i << ": " << search_list<2, 3, 5, 7, 11, 13, 17, 19>::contains(i) << '\n';
  }

  return 0;
}

    Das ist jetzt erstmal nur so hingekladdet, also kann man da bestimmt noch Dinge dran verschönern. Und es ist nicht ausgiebig getestet.

    0
  • S

    Edit: seldon hat schon was gepostet... bloß nicht meins, bloß nicht meins... 😃

    Hast du mal gemessen, wie viel Zeit und Speicher dein Compiler für die partial_sum-Lösung benöigt ?

    Wahrscheinlich viel mehr... 🤡

    camper schrieb:

    template<int first, int second, int ... args>
struct is_sorted : std::integral_constant<bool, is_sorted<first, second>::value && is_sorted<second, args...>::value> {};
template<int first, int second>
struct is_sorted<first, second> : std::integral_constant<bool, (first <= second)> {};

    Das geht auch ohne Rekursion (analog zu all_same)

    #include <type_traits>

template<int...> struct index_list;

template <typename... T> struct all_same;
template <> struct all_same<>
    : std::true_type {};
template <typename T, typename... U> struct all_same<T, U...>
    : std::is_same<all_same<T, U...>, all_same<U..., T>> {};

template<typename, typename>
struct is_sorted_impl;
template<int ... args1, int ... args2>
struct is_sorted_impl<index_list<args1...>, index_list<args2...>> : all_same<std::integral_constant<bool, (args1 <= args2)>...> {};

#include <limits>

template<int ... args> struct is_sorted;
template<> struct is_sorted<> : std::true_type {};
template<int first, int ... args>
struct is_sorted<first, args...> : is_sorted_impl<index_list<first, args...>, index_list<args..., std::numeric_limits<int>::max()>> {};

    ?

    Das Splitten von Listen war, glaube ich, auch eine von meinen Aufgaben.

    Die erste, ja.
    Aber was soll das bringen?:

    #include <type_traits>

typedef unsigned int_type;

template<int_type ... args>
struct index_list
{
    typedef index_list identity;
    static constexpr auto length = sizeof...(args);
    static constexpr int_type arr[]{args...};

    static bool contains(int_type);
};
template<int_type ... args>
constexpr int_type index_list<args...>::arr[];

template<typename, typename> struct concat;
template<int_type ... args1, int_type ... args2>
struct concat<index_list<args1...>, index_list<args2...>> : index_list<args1..., args2...> {};

template<std::size_t N>
struct make_indices : concat<typename make_indices<N-1>::identity, index_list<N-1>> {}; // Edit²: Ok, zweiter Bug gefixt. Jetzt geht es aber. Hoffentlich.
template<> struct make_indices<0> : index_list<> {};

template<typename, typename, std::size_t start, std::size_t len> struct sub_list_impl;
template<int_type ... args, int_type ... indices, std::size_t start, std::size_t len>
struct sub_list_impl<index_list<args...>, index_list<indices...>, start, len> :
    index_list< index_list<args...>::arr[indices + start]...> {};

template<typename, std::size_t start, std::size_t len> struct sub_list;
template<int_type ... args, std::size_t start, std::size_t len>
struct sub_list<index_list<args...>, start, len> : sub_list_impl<index_list<args...>, typename make_indices<len>::identity, start, len>
{
    static_assert( start + len <= sizeof...(args), "invalid range!" );
};

template<int_type ... args>
bool index_list<args...>::contains(int_type val)
{
    // contains muss noch für Listen mit Größe null und eins "spezialisiert" werden

    if( length == 1 )
        return val == arr[0];

    return val > arr[length / 2 - 1] ?
            sub_list<identity, length / 2, length / 2 + length % 2>::contains(val)
          : sub_list<identity, 0, length / 2>::contains(val);
}

#include <iostream>
int main()
{
    std::cout << index_list<1, 2, 3, 4, 5>::contains(2);
}
    0
  • S

    Mir fällt auf, mein sub_list -Konstrukt ist schön. Keine Rekursion. Schön direkt.
    Daher kann man verschiedene Dinge damit schön schreiben:

    template<typename, std::size_t> struct cyclic_shift_list;
template<int_type... args, std::size_t size>
struct cyclic_shift_list<index_list<args...>, size> :
    concat<typename sub_list<index_list<args...>, size, sizeof...(args) - size>::identity,
           typename sub_list<index_list<args...>, 0, size>::identity> {};

    Oder

    template<typename> struct accumulate;

template<int_type ... args>
struct accumulate<index_list<args...>>
{
    typedef index_list<args...> list;
    static constexpr int_type value = list::arr[list::length - 1] 
                                    + accumulate<typename sub_list<list, 0, list::length - 1>::identity>::value;
};

template<int_type first>
struct accumulate<index_list<first>> :
    std::integral_constant<int_type, first> {};

    Das interessante an dieser Definition von accumulate ist die Tatsache, dass accumulate<1, 2, 3, 4> zu 4 + accumulate<1, 2, 3>::value wird - aber accumulate<1, 2, 3> wurde schon,
    im Zuge der Expansions-Reihenfolge von partial_sum(_impl) , vorher instantiiert(!).
    Also keine wirkliche Rekursion, da im Prinzip nur zwei vorhandene Werte addiert werden. Natürlich nur beim speziellen Fall von partial_sum .
    Daher ist das recht effizient. Und das ganze ist dann auch campers Aufgabe entsprechend - es gibt zwar eine Rekursion, aber nur bei make_indices .
    Dieses Prinzip, wo die Rekursion erschnellt wird in dem die Spezialisierungen alle von unten nach oben instantiiert werden, kann man bestimmt auch auf andere Dinge übertragen.

    #include <type_traits>

typedef unsigned int_type;

template<int_type ... args>
struct index_list
{
    typedef index_list identity;
    static constexpr auto length = sizeof...(args);
    static constexpr int_type arr[]{args...};
};
template<int_type ... args>
constexpr int_type index_list<args...>::arr[];

/// concat + make_indices: ///////////////////////////////////////////////////////////////////////////////////////

template<typename, typename> struct concat;
template<int_type ... args1, int_type ... args2>
struct concat<index_list<args1...>, index_list<args2...>> : index_list<args1..., args2...> {};

template<std::size_t N>
struct make_indices : concat<typename make_indices<N-1>::identity, index_list<N-1>> {};
template<> struct make_indices<0> : index_list<> {};

/// sub-list: ///////////////////////////////////////////////////////////////////////////////////////

template<typename, typename, std::size_t start, std::size_t len> struct sub_list_impl;
template<int_type ... args, int_type ... indices, std::size_t start, std::size_t len>
struct sub_list_impl<index_list<args...>, index_list<indices...>, start, len> :
    index_list< index_list<args...>::arr[indices + start]...> {};

template<typename, std::size_t start, std::size_t len> struct sub_list;
template<int_type ... args, std::size_t start, std::size_t len>
struct sub_list<index_list<args...>, start, len> : sub_list_impl<index_list<args...>, typename make_indices<len>::identity, start, len>
{
    static_assert( start + len <= sizeof...(args), "invalid range!" );
};

/// accumulate: ///////////////////////////////////////////////////////////////////////////////////////

template<typename> struct accumulate;

template<int_type ... args>
struct accumulate<index_list<args...>>
{
    typedef index_list<args...> list;
    static constexpr int_type value = list::arr[list::length - 1]
                                    + accumulate<typename sub_list<list, 0, list::length - 1>::identity>::value;
};

template<int_type first>
struct accumulate<index_list<first>> :
    std::integral_constant<int_type, first> {};

/// partial-sum: ///////////////////////////////////////////////////////////////////////////////////////

template<typename,
         typename>
struct partial_sum_impl;

template<int_type ... values,
         int_type ... indices>
struct partial_sum_impl<index_list<values...>, index_list<indices...>> :
    index_list< accumulate< typename sub_list<index_list<values...>, 0, indices + 1>::identity >::value... > {};

template<int_type ... args>
struct partial_sum :
    partial_sum_impl<index_list<args...>, typename make_indices<sizeof...(args)>::identity> {};

/// ///////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <iterator>
int main()
{
    typedef partial_sum<1, 2, 3, 4> mul;
    std::copy(std::begin(mul::arr), std::end(mul::arr), std::ostream_iterator<int_type>(std::cout, ", "));
}
    0
  • K

    Ihr sucht Aufgaben: Generierung einer Sortierfunktion basierend auf Sortiernetzwerke. Breite, also Anzahl der zu sortierenden Elemente, ist zur Kompilezeit bekannt.

    0
Anmelden zum Antworten