flatten_t<> in O(1)?

5cript

Ich suche die Effizienteste (nach Rekursionstiefe) Implementierung für folgende Metafunktion:

using tup = std::tuple <int, float, std::tuple <double, char>, long>;
using flat = flatten_t <tup>; // -> std::tuple <int, float, double, char, long>

meine pseudo lösung in O(n) [Rekursionstiefe].
EDIT: (mein if ist lazy)
EDIT: Die Pseudolösung nimmt auch kein tuple, sondern args. Aber das ist egal.

template <typename T, typename... List>
struct flatten {
    using type = 
    if_ <is_tuple <T>::value, /* do merge with recursive flatten::type O(1) */, 
                              /* push_back / push_front with recursive flatten::type O(1) */>::type; 
};

template <typename T>
struct flatten <T> {
    using type = 
    if_ <is_tuple <T>::value, T, 
                              std::tuple <T> >::type
};

Ist das auch in konstanter Rekursionstiefe machbar?

EDIT: Das ist die tatsächliche Implementierung, aber da die eh niemand ausprobieren kann...

// fundamental
#include "../fundamental/eval_if.hpp"

// control
#include "../control/if.hpp"

// tuple
#include "../tuple/is_tuple.hpp"
#include "../tuple/concat.hpp"
#include "../tuple/apply.hpp"

// algorithm
#include "merge.hpp"

// functional
#include "../functional/lift.hpp"

namespace mplex
{
    namespace internal {
        struct flatten_impl;

        struct flatten_impl {
            template <typename Head, typename... Tail>
            struct apply
            {
                using _is_tuple = typename is_tuple::template apply <Head>::type;
                using _is_not_tuple = bool_ <!_is_tuple::value>;

                using type = lazy_if_t <_is_tuple,
                                        then_ <lift<concat>, Head, eval_if_default_t <_is_tuple, std::tuple<>, flatten_impl, Tail...>>,
                                        else_ <lift<push_front>, eval_if_default_t <_is_not_tuple, std::tuple<>, flatten_impl, Tail...>, Head>>;
            };

        };

        template <typename Head>
        struct flatten_impl::apply <Head> {
            using type = if_t <typename is_tuple::template apply <Head>::type,
                               Head, std::tuple <Head>>;
        };
    }

    /**
     *  Flattens a tuple, but not deep.
     *
     *  std::tuple<int, float, std::tuple <char, long>, double>
     *  becomes std::tuple<int, float, char, long, double>
     *
     */
    template <typename Tuple>
    struct flatten {
        using type = typename apply_t <Tuple, internal::flatten_impl::template apply>::type;
    };

    template <typename Tuple>
    using flatten_t = typename flatten <Tuple>::type;
}

Columbo

Man kann logarithmische Tiefe erreichen. Ich denke, folgendes funktioniert - nur schnell heruntergetippt, geht wahrscheinlich viel eleganter (und effizienter):

#include <type_traits>

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

template <std::size_t ... args>
struct index_list {using type=index_list;};

template <typename T> using eval = typename T::type;

template <typename...> struct pack {};

template <typename> constexpr std::size_t length=0;
template <typename... xs>
constexpr auto length<pack<xs...>> = sizeof...(xs);

template <typename, typename> struct duplicate;
template <std::size_t... is, std::size_t... ts>
struct duplicate<index_list<is...>, index_list<ts...>> : index_list<is..., (sizeof...(is)+is)...,
                                                                         (2*sizeof...(is)+ts)...> {};

template <std::size_t N>
struct make_index_list :
	duplicate< eval<make_index_list<N/2>>,
	           eval<make_index_list<N%2>> > {};

template <> struct make_index_list<1> : index_list<0> {};
template <> struct make_index_list<0> : index_list<> {};

template <std::size_t N>
using make_index_list_t = eval<make_index_list<N>>;

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

template <typename T, std::size_t>
struct type_node {using type=T;};
template <std::size_t I, typename U>
identity<U> type_deducer(type_node<U,I>);

template <typename P, typename=make_index_list_t<length<P>>>
struct type_map;
template <typename... T, std::size_t... indices>
struct type_map<pack<T...>, index_list<indices...>> : type_node<T, indices>... {};

template <typename M, std::size_t I>
using get_t = eval<decltype(type_deducer<I>(M()))>;

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

template <typename, typename> struct cat;
template <typename... ls, typename... rs>
struct cat<pack<ls...>, pack<rs...>> {using type=pack<ls...,rs...>;};
template <typename A, typename B> using cat_t = eval<cat<A,B>>;

template <typename P, std::size_t I=0, std::size_t L=length<P>>
struct flatten : cat<typename flatten<P, I, L/2>::type, typename flatten<P, I+L/2, L/2 + L%2>::type> {};
template <typename P, std::size_t I>
struct flatten<P, I, 1> {
	template <typename _> struct aux {using type=pack<_>;};
	template <typename... _>
	struct aux<pack<_...>> : flatten<pack<_...>> {};

	using type = typename aux<typename decltype(type_deducer<I>(type_map<P>()))::type>::type;
};
template <> struct flatten<pack<>, 0, 0> {using type=pack<>;};

template <typename P>
using flatten_t = eval<flatten<P>>;

static_assert(std::is_same<flatten_t<pack<int, float, pack<double, pack<long>>, pack<int>>>,
                                     pack<int, float, double, long, int>>{});

5cript

Ich wusste du würdest antworten
Erster Eindruck: Holy ****

template <typename T> using eval = typename T::type;

Ist das eine Denksache?

template <typename...> struct pack {};

Ich muss auch nochmal umstellen.

Ich brauche glaube ich noch ein bisschen Zeit, bis ich den Code komplett verstanden habe ^^.

EDIT: ah, das ist viel hilfcode und nicht so viel zum eigentlichen problem.

Columbo

Habe den Code nochmal angepasst. Hilft aber alles nix. Läuft nämlich linear in der Länge der resultierenden Liste.

template <int N>
struct construct {using type=pack<int, double, float, char, bool, long, typename construct<N-1>::type>;};
template <>
struct construct<0> {using type=pack<>;};

using F = flatten_t<construct<64>::type>;

Packen GCC und Clang in genau 322 Instantiierungen, wobei die resultierende Liste aber 384 ist.
flatten_t<construct<128>::type> braucht exakt 643 Instantiierungen für eine doppelt so lange Liste.

Sorry, hab' mich nicht richtig mit dem Problem auseinandergesetzt. Habe ein paar Ideen, die ich mir anschauen werde.

Ich muss auch nochmal umstellen.

pack kompiliert deutlich schneller als tuple . Siehe e.g. hier, wo das verwenden von pack die Effizienz krass gesteigert hat.

ah, das ist viel hilfcode und nicht so viel zum eigentlichen problem.

Ja, ich wollte nämlich logarithmische Instantiierungstiefe für make_index_list , was Implementierungen von std::make_index_sequence in libc++ und libstdc++ momentan nicht vorzeigen können.

5cript

Packen GCC und Clang in genau 322 Instantiierungen, wobei die resultierende Liste aber 384 ist.
flatten_t<construct<128>::type> braucht exakt 643 Instantiierungen für eine doppelt so lange Liste.

Wie weißt du das so genau?

pack kompiliert deutlich schneller als tuple. Siehe e.g. hier, wo das verwenden von pack die Effizienz krass gesteigert hat.

Ja das habe ich vor ein paar Wochen gehört, vom boost Hana Schöpfer (in einem seiner talks).

Columbo

Habe mich vertan, es scheint, dass pro Schachtelungstiefe ein logarithmischer Overhead besteht. Hier wohl 5 - einer für aux , ein anderer für die Spezialisierung von type_deducer um auf den Typ zuzugreifen, und $\lceil \text{lb} 7 \rceil$ . Daher 5*128 = 640, plus drei Instantiierungen drum herum. Das scheint im Nachhinein von der Komplexität ziemlich optimal zu sein, schließlich brauchen wir auf jeder Ebene auch mindestens einen logarithmischen Overhead zum konkatenieren.

Eine Idee wäre zumindest, nur Indizen auf die packs zu speichern, diese dann parallel(!!!) zu flatten und anschließend die Konkatenierung der resultierenden packs und der ursprünglichen, nicht-pack Typen rekursiv vorzunehmen. Das werd' ich mir mal anschauen.

5cript schrieb:

Woher weißt du das so genau?

Du kannst eine Intervall schachtelnde Bash-Anweisung schreiben, die den Rückgabewert des Compilers als Vergleichsprädikat nimmt (1 => kleiner, 0 <= größer) und das Argument an -ftemplate-depth anpasst.

5cript

Du kannst eine Intervall schachtelnde Bash-Anweisung schreiben, die den Rückgabewert des Compilers als Vergleichsprädikat nimmt (1 => kleiner, 0 <= größer) und das Argument an -ftemplate-depth anpasst.

smart!

Columbo

Ja, meine Idee hat sehr geholfen. construct<64> braucht kaum mehr 76 Instantiierungen, construct<128> 140. Die Linearität in der Verschachtelungstiefe hat sich natürlich nicht geändert (immer noch $\Theta(n)$ ), was sich auch nicht ändern kann, aber wir haben nun einen Overhead, der logarithmisch in der Länge des längsten, rekursiv enthaltenen Packs wächst. I.e. wenn jedes pack in construct<64> stattdessen 32 Member hat, bekommen wir 78, was natürlich bei zwei zusätzlichen (binären) Größenordnungen über 8 ziemlich einleuchtend ist.

#include <type_traits>

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

template <std::size_t... args>
struct index_list{
	using type=index_list;
	static constexpr std::size_t arr[] = {args...};
};

template <typename T> using eval = typename T::type;

template <typename...> struct pack {using type=pack;};

template <typename> constexpr std::size_t length=0;
template <typename... xs>
constexpr auto length<pack<xs...>> = sizeof...(xs);

template <typename, typename> struct duplicate;
template <std::size_t... is, std::size_t... ts>
struct duplicate<index_list<is...>, index_list<ts...>> : index_list<is..., (sizeof...(is)+is)...,
                                                                         (2*sizeof...(is)+ts)...> {};

template <std::size_t N>
struct make_index_list :
	duplicate< eval<make_index_list<N/2>>,
	           eval<make_index_list<N%2>> > {};

template <> struct make_index_list<1> : index_list<0> {};
template <> struct make_index_list<0> : index_list<> {};

template <std::size_t N>
using make_index_list_t = eval<make_index_list<N>>;

template <typename IL, std::size_t start, std::size_t len, typename=make_index_list_t<len>>
struct sub_list;
template <typename IL, std::size_t start, std::size_t len, std::size_t... indices>
struct sub_list<IL, start, len, index_list<indices...>> : index_list<IL::arr[start+indices]...> {};

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

template <typename T, std::size_t>
struct type_node {using type=T;};
template <std::size_t I, typename U>
identity<U> type_deducer(type_node<U,I>);

template <typename P, typename=make_index_list_t<length<P>>>
struct type_map;
template <typename... T, std::size_t... indices>
struct type_map<pack<T...>, index_list<indices...>> : type_node<T, indices>... {};

template <typename M, std::size_t I>
using get_t = typename decltype(type_deducer<I>(M()))::type;
template <typename P, std::size_t I>
using pack_get_t = typename decltype(type_deducer<I>(type_map<P>()))::type;

template <typename P, std::size_t start, std::size_t len, typename=make_index_list_t<len>>
struct sub_pack;
template <typename P, std::size_t start, std::size_t len, std::size_t... indices>
struct sub_pack<P, start, len, index_list<indices...>> : pack<pack_get_t<P, start+indices>...> {};

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

template <typename, typename> struct cat;
template <typename... ls, typename... rs>
struct cat<pack<ls...>, pack<rs...>> {using type=pack<ls...,rs...>;};
template <std::size_t... ls, std::size_t... rs>
struct cat<index_list<ls...>, index_list<rs...>> {using type=index_list<ls...,rs...>;};
template <typename A, typename B> using cat_t = eval<cat<A,B>>;

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

template <template<typename, std::size_t> typename F, typename State>
struct reccat {
	template <std::size_t I, std::size_t L>
	struct apply : cat<typename apply<I, L/2>::type,
	                   typename apply<I+L/2, L/2 + L%2>::type> {};
	template <std::size_t I>
	struct apply<I, 1> {using type=typename F<State, I>::type;};
};
template <template<typename, std::size_t> typename F, typename State, std::size_t L>
using reccat_t = typename reccat<F, State>::template apply<0, L>::type;

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

template <typename P, std::size_t I>
struct getIndicesImpl {
	template <typename> struct aux : index_list<> {};
	template <typename... _>
	struct aux<pack<_...>> : index_list<I> {};

	using type = typename aux<pack_get_t<P, I>>::type;
};
template <typename P>
struct getIndices : reccat_t<getIndicesImpl, P, length<P>> {};
template <>
struct getIndices<pack<>> : index_list<> {};

template <typename P, typename=typename getIndices<P>::type>
struct flatten;

template <typename P, std::size_t... pack_indices>
struct flatten<P, index_list<pack_indices...>>
{
	using flattened_packs = pack<typename flatten<pack_get_t<P, pack_indices>>::type...>;

	template <typename, std::size_t I>
	struct merge {
		static constexpr auto start_index = I==0? 0 : index_list<pack_indices...>::arr[I-1]+1;
		template <typename=make_index_list_t<index_list<pack_indices...>::arr[I] - start_index>>
		struct aux;
		template <std::size_t... indices>
		struct aux<index_list<indices...>> : cat<pack<pack_get_t<P, start_index+indices>...>,
		                                         pack_get_t<flattened_packs, I>> {};
		using type = eval<aux<>>;
	};

	static constexpr auto tail_start_index = index_list<pack_indices...>::arr[sizeof...(pack_indices)-1]+1;
	using type = cat_t<reccat_t<merge, void, sizeof...(pack_indices)>,
	                   typename sub_pack<P, tail_start_index, length<P>-tail_start_index>::type>;
};

template <typename _> struct flatten<_, index_list<>> {using type = _;};
template <typename... _> struct flatten<pack<pack<_...>>, index_list<0>> {using type = eval<flatten<pack<_...>>>;};

template <typename P>
using flatten_t = eval<flatten<P>>;

/// TESTS:

static_assert(std::is_same<flatten_t<pack<int, float, pack<double, pack<long>, int>, pack<int>, float>>,
                                     pack<int, float,      double,      long,  int,       int,  float>>{});

template <int N>
struct construct {using type=pack<int, double, float, char, bool, long, typename construct<N-1>::type, unsigned long>;};
template <>
struct construct<0> {using type=pack<>;};

using F = flatten_t<construct<64>::type>;

5cript

Oh mein Gott

Das versuch ich gar nicht mehr nachzuvollziehen
Das schafft ja sogar rekursiv (flatten_deep), wenn ich das richtige sehe.

Da bleibt mir nur noch Danke zu sagen.

EDIT: Man könnte vielleicht noch optimieren, wenn man die Reihenfolge außer Acht lässt, was aber zumindest in meinem Anwendungsfall leider nicht geht.
(Dafür hatte ich eine Idee mit pack expansion, habe aber den Gedanken noch nicht ganz zu Ende gebracht.).

Columbo

5cript schrieb:

Das schafft ja sogar rekursiv (flatten_deep), wenn ich das richtige sehe.

Na darum ging's doch?

5cript

Eine Ebene hätte auch (erstmal) gereicht

flatten_t&lt;&gt; in O(1)?

flatten_t<> in O(1)?