3. Du Suchst Übung!?

Du Suchst Übung!?

  • S

    1500 Punkte ... Platz 3

    0
  • S

    Verdammt! Zehn Punkte vor Platz 2! 😡

    0
  • S

    Hehe, camper hat sich also doch angemeldet! 😃

    0
  • C
    Mod

    Ich habe jetzt noch ein filter ohne merge&co & expliziter rekursion im Algorithmus (die Rekursion steckt hier wie üblich in make_index_list und derived_tag).. Funktioniert aber leider wieder nur mit clang.

    #include <type_traits>

namespace tmpalg {
  template <typename T>
  struct identity_ {
    using type = T;
  };
  template <typename T>
  using identity = T;

  template <typename... T>
  struct type_list
    : identity_<type_list<T...>> {};

  template <int... i>
  struct index_list
    : identity_<index_list<i...>> {};

  template <typename T>
  struct true_pred
    : std::true_type {};

  template <int N, typename = index_list<>>
  struct make_index_list_;
  template <int N, typename T = index_list<>>
  using make_index_list = typename make_index_list_<N, T>::type;
  template <int N, int... i>
  struct make_index_list_<N, index_list<i...>>
    : make_index_list<N-1, index_list<0, 1+i...>> {};
  template <int... i>
  struct make_index_list_<0, index_list<i...>>
    : index_list<i...> {};

  template <int I>
  struct tag {};

  template <typename TL>
  struct size_;
  template <typename TL>
  using size = typename size_<TL>::type;
  template <typename... T>
  struct size_<type_list<T...>>
    : std::integral_constant<int, sizeof...(T)> {};

  template <typename TL, template <typename> class F>
  struct transform_;
  template <typename TL, template <typename> class F>
  using transform = typename transform_<TL, F>::type;
  template <typename... T, template <typename> class F>
  struct transform_<type_list<T...>, F>
    : type_list<F<T>...> {};

  template <int I, bool b, typename T>
  struct helper
    : std::integral_constant<bool, b>
  {
    friend identity_<T> at_adl(tag<I>, helper);
  };

  template <typename TL, template <typename> class Pred = true_pred, typename I = make_index_list<size<TL>::value>>
  struct apply_pred_;
  template <typename... T, template <typename> class Pred, int... i>
  struct apply_pred_<type_list<T...>, Pred, index_list<i...>>
    : helper<i, Pred<T>::value, T>... {};

  template <typename TL, int N>
  struct at_
    : identity_<typename decltype(at_adl(tag<N>{}, apply_pred_<TL>{}))::type> {};
  template <typename TL, int N>
  using at = typename at_<TL, N>::type;

  template <int I>
  struct indexed_value
  {
    constexpr indexed_value(int v) : value(v) {}
    int value;
  };

  template <typename TL, template <typename> class Pred = true_pred, typename I = make_index_list<size<TL>::value>>
  struct apply_pred;
  template <typename... T, template <typename> class Pred, int... i>
  struct apply_pred<type_list<T...>, Pred, index_list<i...>>
    : apply_pred_<type_list<T...>, Pred, index_list<i...>>, indexed_value<-1>, indexed_value<i>...
  {
    constexpr apply_pred() : indexed_value<-1>(0), indexed_value<i>(get<i-1>()+Pred<T>::value)... {}
    constexpr int count() const { return get<sizeof...(i)-1>(); }
    template <int I> constexpr int get() const { return indexed_value<I>::value; }
  };

  template <int I>
  struct derived_tag : derived_tag<I-1> {};
  template <>
  struct derived_tag<0> {};

  template <typename TL, template <typename> class Pred, typename I = make_index_list<size<TL>::value>, typename J = make_index_list<apply_pred<TL, Pred>().count()>>
  struct filter_;
  template <typename TL, template <typename> class Pred = true_pred>
  using filter = typename filter_<TL, Pred>::type;
  template <typename TL, template <typename> class Pred, int... i, int... j>
  struct filter_<TL, Pred, index_list<i...>, index_list<j...>>
  {
    static constexpr apply_pred<TL, Pred> x{};
    template <int x, int y>
    struct ordered_pair
    {
      friend constexpr int find_first(int derived_tag<x>::*, tag<y>, ordered_pair) { return x; }
    };
    struct bimap
      : ordered_pair<i, x.template get<i>()>... {};
    using type = type_list<at<TL,find_first(static_cast<int derived_tag<0>::*>(nullptr), tag<j+1>(), bimap())>...>;
  };

  template <typename TL, template <typename> class Pred = true_pred>
//  using all_of = std::integral_constant<bool, !std::is_base_of<std::false_type, apply_pred_<TL, Pred>>::value>;
  using all_of = std::integral_constant<bool, apply_pred<TL, Pred>().count() == size<TL>::value>;

  template <typename TL, template <typename> class Pred = true_pred>
//  using any_of = std::is_base_of<std::true_type, apply_pred_<TL, Pred>>;
  using any_of = std::integral_constant<bool, apply_pred<TL, Pred>().count() != 0>;

  template <typename TL, template <typename> class Pred = true_pred>
//  using none_of = std::integral_constant<bool, !std::is_base_of<std::true_type, apply_pred_<TL, Pred>>::value>;
  using none_of = std::integral_constant<bool, apply_pred<TL, Pred>().count() == 0>;
}
    0
  • S

    Yes! Zweiter!

    Edit: Ach menno. Und camper hat wieder einen Bosscode. 😞 😞

    0
  • ?

    Alle Achtung camper, auch dein at ist sehr elegant.

    0
  • S

    Ich habe fast die lookup-Table fertig... 🙂
    Edit: Ja, campers Code ist fast perfekt.

    0
  • S

    So, fertig! Ich frag mal gar nicht sondern Poste:

    #include <array>

typedef uint_least64_t fac_result_t;
typedef uint8_t fac_of_t;
fac_of_t constexpr N = 20;
typedef std::array<fac_result_t, N> array_t;

constexpr fac_result_t fak(fac_of_t n) { return n > 1 ? fak(n-1)*n : 1; }

/// *** Hier wird es interessant:
template<fac_of_t still, fac_result_t F(fac_of_t), fac_of_t ... args> struct table_impl
{ static array_t constexpr table = table_impl<still - 1, F, args..., N - still>::table; };
template<fac_of_t ... args, fac_result_t F(fac_of_t)> struct table_impl<0, F, args...>
{ static array_t constexpr table { F(args)... }; };
/// ***
array_t constexpr table = table_impl<N, fak>::table;

#include <cassert>
int main()
{
    for (unsigned i=0; i<N; ++i)
        assert(table[i] == fak(i));
}

    Die Lösung ist bereits eingereicht 🙂

    0
  • ?

    Verbesserungsvorschlag: Verzichte auf die explizite Rekursion unter Benutzung von campers make_index_list.

    0
  • C
    Mod

    Meine Lösung zu all_equal

    template <typename... Ts> struct all_equal;
template <typename T, typename... Ts> struct all_equal<T, Ts...>
  : std::is_same<tmpalg::type_list<T, Ts...>, tmpalg::type_list<Ts..., T>> {};
template <> struct all_equal<> : std::true_type {};

    (nicht ganz das Geforderte).

    Edit: Wenn ich recht darüber nachdenke, kann man so dann auch all_of&co schreiben:

    template <typename TL, template <typename> class Pred>
struct all_of;
template <typename... T, template <typename> class Pred>
struct all_of<type_list<T...>>
  : all_equal<std::true_type, std::integral_constant<bool, Pred<T>::value>...> {};

template <typename TL, template <typename> class Pred>
struct none_of;
template <typename... T, template <typename> class Pred>
struct none_of<type_list<T...>>
  : all_equal<std::false_type, std::integral_constant<bool, Pred<T>::value>...> {};

template <typename TL, template <typename> class Pred>
struct any_of
  : std::integral_constant<bool, !none_of<TL, Pred>::value> {};

    mit minimalem Instantiierungsaufwand.

    0
  • S
     

    template <typename... Ts> struct all_equal; 
template <typename T, typename... Ts> struct all_equal<T, Ts...> 
  : std::is_same<tmpalg::type_list<T, Ts...>, tmpalg::type_list<Ts..., T>> {}; 
template <> struct all_equal<> : std::true_type {};

    😮 Das ist genial!

    0
  • ?

    Camper, hast du auch eine Lösung für #40 ohne merge&co & explizite Rekursion?

    template <typename... T> struct type_list { typedef type_list type; };
template <typename T> struct identity_ { typedef T type; };

template <template<typename>class A, typename TL> struct transform_32;
template <template<typename>class A, typename... T>
struct transform_32<A, type_list<T...> > : type_list<typename A<T>::type...> {};

template <typename TL> struct head;
template <typename T, typename... Ts> struct head<type_list<T, Ts...> >
  : identity_<T> {};

template <typename TL> struct tail;
template <typename T, typename... Ts> struct tail<type_list<T, Ts...> >
  : identity_<type_list<Ts...> > {};

template <template <typename...> class F, typename TL> struct call;
template <template <typename...> class F, typename... Ts>
struct call<F, type_list<Ts...> > : identity_<typename F<Ts...>::type> {};

template <typename T, typename TL> struct cons;
template <typename T, typename... Ts>
struct cons<T, type_list<Ts...> > : identity_<type_list<T, Ts...> > {};

template <template <typename...> class F, typename... TLs>
struct transform_;
template <template <typename...> class F, typename... TLs>
using transform = typename transform_<F, TLs...>::type;

template <template <typename...> class F, typename... TLs>
struct transform_<F, type_list<>, TLs...> : identity_<type_list<> > {};

template <template <typename...> class F>
struct transform_<F> : identity_<type_list<> > {};

template <template <typename...> class F, typename TL>
struct call_transform {
  template <typename... TLs> using trans = transform<F, TLs...>;
  using type = typename call<trans, TL>::type;
};

template <template <typename...> class F, typename... TLs>
struct transform_
  : identity_<typename cons<typename call<F, typename transform_32<head, type_list<TLs...> >::type>::type,
                            typename call_transform<F, typename transform_32<tail, type_list<TLs...> >::type>::type>::type
              > {};
    0
  • C
    Mod

    Ich habe mir bisher nicht die Mühe gemacht, selbst eine Lösung zu erstellen.
    Eine Merge ohne Rekursion ist allerdings möglich, wenn man at etwas verallgemeinert...
    Ich schreibs mal auf, wenn Sone seine Lösung abgeliefert hat.

    0
  • S

    Ich schreibs mal auf, wenn Sone seine Lösung abgeliefert hat.

    Sone hat Fragen zur Aufgabe.
    Und zwar, nach welchen Kriterien soll entschieden werden ob alle Elemente einer Typliste zu einem neuen Element der neuen TL verschmelzen, oder ob jedes Element jeder Typliste zur neuen Typliste dazuzählt?

    0
  • C
    Mod

    Verstehe die Frage nicht. Hast du ein Beispiel?

    0
  • ?

    Unter Benutzung von Campers make_index_list und den Helfern at , size und identity_ aus #32:

    template <template <typename...> class F, typename TL> struct call;
template <template <typename...> class F, typename... Ts>
struct call<F, type_list<Ts...> > : identity_<typename F<Ts...>::type> {};

template <template <typename...> class F, typename I, typename... TLs>
struct transform_;
template <template <typename...> class F, typename... TLs>
using transform = typename transform_<F, make_index_list<size<at<type_list<TLs...>, 0> >::value>, TLs...>::type;
template <template <typename...> class F, int... I, typename... TLs>
struct transform_<F, index_list<I...>, TLs...> {
  template <int i> struct tlat : identity_<type_list<at<TLs, i>...> > {};
  using type = type_list<typename call<F, typename tlat<I>::type>::type...>;
};

    (Mich wundert, dass wenn man Zeile 11 durch template <int i> using tlat = identity_<type_list<at<TLs, i>...> >; ersetzt, sowohl GCC als auch Clang den Code ablehnen, weil sie Pack Expansion über beide Template Parameter zu machen versuchen.)

    0
  • C
    Mod

    g++ kommt bei mir mit dem Code gar nicht zurecht

    $ LC_MESSAGES=en_US.utf8 g++-4.8.0-alpha20121216 -std=c++11 test.cpp -Wno-non-template-friend
test.cpp: In substitution of ‘template<template<class ...> class F, class ... TLs> using transform = typename tmpalg::transform_<F,
 typename tmpalg::make_index_list_<typename tmpalg::size_<typename tmpalg::at_<tmpalg::type_list<Ts ...>, 0ul>::type>::type:: value,
 tmpalg::index_list<> >::type, TLs ...>::type [with F = std::add_pointer; TLs = {tmpalg::type_list<int, char, double>}]’:
test.cpp:79:62:   required from here
test.cpp:67:112: error: invalid use of incomplete type ‘struct tmpalg::transform_<std::add_pointer, tmpalg::index_list<0ul, 1ul, 2ul>,
 tmpalg::type_list<int, char, double> >’
 using transform = typename transform_<F, make_index_list<size<at<type_list<TLs...>, 0> >::value>, TLs...>::type;
                                                                                                                ^
test.cpp:65:8: error: declaration of ‘struct tmpalg::transform_<std::add_pointer, tmpalg::index_list<0ul, 1ul, 2ul>, tmpalg::type_list<int, char, double> >’
 struct transform_;
        ^
test.cpp:79:95: error: template argument 1 is invalid
 static_assert( std::is_same<transform<std::add_pointer, list1>, type_list<int*, char*, double*>>::value, "transform failed!" );

    g++ 4.7.2 ist analog. clang macht dagegen keine Probleme, auch nicht mit

    template <int i> using tlat = identity_<type_list<at<TLs, i>...> >;

    $ LC_MESSAGES=en_US.utf8 g++-4.7.2 --version
g++-4.7.2 (Gentoo 4.7.2 p1.3, pie-0.5.5) 4.7.2

$ LC_MESSAGES=en_US.utf8 g++-4.8.0-alpha20121216 --version
g++-4.8.0-alpha20121216 (Gentoo 4.8.0_alpha20121216) 4.8.0-alpha20121216 20121216 (experimental)

$ LC_MESSAGES=en_US.utf8 clang++ --version
clang version 3.2 (tags/RELEASE_32/final)

    evtl. ist deine Version veraltet?

    0
  • ?

    Naja, der gepostete Code kompiliert bei mir mit g++ und clang++.

    % clang++ --version    
Debian clang version 3.1-8 (branches/release_31) (based on LLVM 3.1)
Target: i386-pc-linux-gnu
Thread model: posix
% g++ --version 
g++ (Debian 4.7.2-5) 4.7.2
Copyright (C) 2012 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

    Keine Ahnung, wie aktuell die sind, ich nehme einfach die aus den Paketquellen und warte bis sie sich von selber aktualisieren.

    0
  • C
    Mod

    mit clang-3.2 läuft auch dieser Code

    Es gibt noch ein paar Bugs in g++, wenn Aliastemplates als Templateparemeter eingesetzt werden.

    0
  • ?

    Stimmt. Das ist nett, weil jetzt kann man ihn verkürzen (und clang kompiliert ihn immer noch).

    template <int i> using tlat = type_list<at<TLs, i>...>;
  using type = type_list<typename call<F, tlat<I> >::type...>;
    0
Anmelden zum Antworten