Wie kann ich ein kartesisches Produkt von Typlisten in C ++ erstellen?

26

Selbsterklärend.

Angenommen, ich habe Typlisten wie folgt:

using type_list_1 = type_list<int, somestructA>;
using type_list_2 = type_list<somestructB>;
using type_list_3 = type_list<double, short>;

Sie können eine variable Anzahl von Typlisten sein.

Wie erhalte ich eine Typeliste für kartesische Produkte?

result = type_list<
type_list<int, somestructB, double>,
type_list<int, somestructB, short>,
type_list<somestructA, somestructB, double>,
type_list<somestructA, somestructB, short>
>;

Ich habe versucht, ein kartesisches Zwei-Wege-Produkt zu erstellen, wie hier angegeben: Wie erstelle ich das kartesische Produkt einer Typenliste? , aber n Weg scheint nicht so trivial zu sein.

Im Moment versuche ich ...

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

// To concatenate
template <typename... Ts, typename... Us>
constexpr auto operator|(type_list<Ts...>, type_list<Us...>) {
   return type_list{Ts{}..., Us{}...};
}

template <typename T, typename... Ts, typename... Us>
constexpr auto cross_product_two(type_list<T, Ts...>, type_list<Us...>) {
    return (type_list<type_list<T,Us>...>{} | ... | type_list<type_list<Ts, Us>...>{});
}

template <typename T, typename U, typename... Ts>
constexpr auto cross_product_impl() {
    if constexpr(sizeof...(Ts) >0) {
        return cross_product_impl<decltype(cross_product_two(T{}, U{})), Ts...>();
    } else {
        return cross_product_two(T{}, U{});
    }
}

Ich werde nur sagen, wenn man bedenkt, wie schwierig es ist, es richtig zu machen, benutze einfach Boost wie in der Antwort von Barry. Leider muss ich mich an einen handgerollten Ansatz halten, denn Boost zu verwenden oder nicht, ist eine Entscheidung, die von irgendwo anders kommt :(

themagicalyang
quelle
8
Oof, du bist ein Vielfraß zur Bestrafung 😏
Leichtigkeitsrennen im Orbit
Ich lutsche ein bisschen daran, aber können Sie das kartesische 2-Wege-Produkt so modifizieren, dass: 1) die erste Typeliste tatsächlich eine Typeliste von Typelisten eines Typs ist; 2) Anstatt zwei Typen aus Typelisten zu verketten, würde die Metafunktion Typen aus der zweiten Liste an "untergeordnete" Listen der ersten Typeliste anhängen (auf kartesische Produktart). Wenn es machbar ist, kann das Problem leicht mit einem rekursiven Algorithmus gelöst werden.
Smitsyn
1
Die eigentliche Schwierigkeit bei einer rekursiven Implementierung besteht darin, dass cartesian_productes sich um eine Liste von Typlisten handelt und dass Sie bei jedem Rekursionsschritt Inhalte an jede innere Typliste anhängen möchten. Der Einstieg in diese zweite Packstufe erfordert einen gewissen Abzug ...
Max Langhof
1
Ich denke, Sie könnten es auch "linear" implementieren, indem Sie dies als einen N-dimensionalen "Typraum" betrachten, in dem Sie jeden "Typgitterpunkt" durchlaufen möchten. Sie berechnen die Anzahl der Gitterpunkte, durchlaufen sie dann einfach wie durch ein abgeflachtes ND-Array und berechnen die Typen an jedem Gitterpunkt. Etwas zu beachten ...
Max Langhof
1
@MaxLanghof Etwas in der Art von " Ein kartesisches Produkt von Tupeln in C ++ 17 "?
Deduplikator

Antworten:

14

Bei Boost.Mp11 ist dies (wie immer) ein kurzer Einzeiler :

using result = mp_product<
    type_list,
    type_list_1, type_list_2, type_list_3>;

Demo .

Barry
quelle
1
Heilige Kuh ... Aber ich fühle mich verpflichtet darauf hinzuweisen, dass das Kompilieren der Mp11-Version etwa doppelt so lange dauert (jeder Code wird mehrmals auf Godbolt abgetastet). Ich bin mir nicht sicher, wie viel von diesem Overhead den Boost-Header selbst analysiert und wie viel Vorlagen instanziiert ...
Max Langhof
1
@ MaxLanghof Sicher. 1,5x wenn Sie nur algorithm.hppanstelle von Mp11 einschließen. Und selbst dann sprechen wir von 0,08 s gegen 0,12 s. Ich muss berücksichtigen, wie lange ich gebraucht habe, um das auch zu schreiben.
Barry
8
@Barry: Aus softwaretechnischer Sicht zu 100% bei Ihnen. Es gibt auch, wie einfach dies im Vergleich zu einem handgerollten Ansatz zu lesen ist. Außerdem sind kaum oder gar keine Tests erforderlich, um die Richtigkeit der Bibliothekslösung sicherzustellen. Insgesamt führen weniger Code und ein höheres Vertrauen zu niedrigeren Wartungskosten für die gesamte Lebensdauer.
AndyG
Ich bin damit einverstanden, dass dies recht einfach ist, aber leider gibt es Teams, die die Stirn runzeln.
themagicalyang
Es gibt Teams, die alles missbilligen. Dies ist kein Grund, es nicht zu verwenden.
Tomaz Canabrava
13

OK habe es. Es ist nicht schön, aber es funktioniert:

template<class ... T>
struct type_list{};

struct somestructA{};
struct somestructB{};

using type_list_1 = type_list<int, somestructA, char>;
using type_list_2 = type_list<somestructB>;
using type_list_3 = type_list<double, short, float>;

template<class TL1, class TL2>
struct add;

template<class ... T1s, class ... T2s>
struct add<type_list<T1s...>, type_list<T2s...>>
{
    using type = type_list<T1s..., T2s...>;
};

template<class ... TL>
struct concat;

template<class TL, class ... TLs>
struct concat<TL, TLs...>
{
    using type = typename add<TL, typename concat<TLs...>::type>::type;
};

template<class TL>
struct concat<TL>
{
    using type = TL;
};

static_assert(std::is_same_v<type_list<int, somestructA, char, double, short, float>, typename add<type_list_1, type_list_3>::type>);

template<class TL1, class TL2>
struct multiply_one;

// Prepends each element of T1 to the list T2.
template<class ... T1s, class ... T2s>
struct multiply_one<type_list<T1s...>, type_list<T2s...>>
{
    using type = typename concat<type_list<type_list<T1s, T2s...>...>>::type;
};

static_assert(std::is_same_v<
    type_list<
        type_list<int, double, short, float>,
        type_list<somestructA, double, short, float>,
        type_list<char, double, short, float>
        >,
    typename multiply_one<type_list_1, type_list_3>::type>);

// Prepends each element of TL to all type lists in TLL.
template<class TL, class TLL>
struct multiply_all;

template<class TL, class ... TLs>
struct multiply_all<TL, type_list<TLs...>>
{
    using type = typename concat<typename multiply_one<TL, TLs>::type...>::type;
};

static_assert(std::is_same_v<
    type_list<
        type_list<int, double, short, float>,
        type_list<somestructA, double, short, float>,
        type_list<char, double, short, float>
        >,
    typename multiply_all<type_list_1, type_list<type_list_3>>::type>);

static_assert(std::is_same_v<
    type_list<
        type_list<int, somestructB>,
        type_list<somestructA, somestructB>,
        type_list<char, somestructB>,
        type_list<int, double, short, float>,
        type_list<somestructA, double, short, float>,
        type_list<char, double, short, float>
        >,
    typename multiply_all<type_list_1, type_list<type_list_2, type_list_3>>::type>);

template<class TL, class ... TLs>
struct cartesian_product
{
    using type = typename multiply_all<TL, typename cartesian_product<TLs...>::type>::type;
};

template<class ... Ts>
struct cartesian_product<type_list<Ts...>>
{
    using type = type_list<type_list<Ts>...>;
};


using expected_result = type_list<
    type_list<int, somestructB, double>,
    type_list<somestructA, somestructB, double>,
    type_list<char, somestructB, double>,
    type_list<int, somestructB, short>,
    type_list<somestructA, somestructB, short>,
    type_list<char, somestructB, short>,
    type_list<int, somestructB, float>,
    type_list<somestructA, somestructB, float>,
    type_list<char, somestructB, float>
>;

static_assert(std::is_same_v<expected_result,
    cartesian_product<type_list_1, type_list_2, type_list_3>::type>);

https://godbolt.org/z/L5eamT

Ich habe meine eigenen static_assertTests dort gelassen für ... Nun, ich hoffe, sie helfen.

Ich bin mir auch sicher, dass es eine schönere Lösung geben muss. Aber dies war der offensichtliche Weg "Ich weiß, dass dies irgendwann zum Ziel führen wird". Ich musste schließlich auf das Hinzufügen eines concatoder mehrerer Sorten zurückgreifen. Ich bin sicher, dass es viel früher verwendet werden könnte, um den größten Teil der Kruft zu überspringen.

Max Langhof
quelle
4
Vorlagenprogrammierung, der ich folgen kann. Das ist großartig. Ich habe heute etwas gelernt.
Jerry Jeremiah
add benötigt zwei type_lists. Wie übergeben Sie mehrere Typlisten, um sie in concat hinzuzufügen?
themagicalyang
@themagicalyang Gut entdeckt, das ist ein Fehler (den die Tests nicht fanden, da alle beteiligten Listen nur Länge 2 hatten). Das ...muss innerhalb des rekursiven concatAufrufs gehen, nicht außerhalb. Antwort (einschließlich Testfälle) korrigiert. Beweist Barry Recht in Bezug auf Korrektheitserwartungen :)
Max Langhof
Ist der kartesische Produktaufruf zu multiplizieren_all nicht grundsätzlich ein multiple_one?
Themagicalyang
@themagicalyang No. cartesian_productimplementiert die Rekursion. multiply_allführt multiply_onefür jede Typliste im TLsPaket eine aus. cartesian_product::typeist eine Liste von Typlisten. multiply_allNimmt eine Typliste und eine Liste von Typlisten. multiply_onenimmt zwei Typenlisten a1, a2, a3und b1, b2, b3und schafft a1, b1, b2, b3, a2, b1, b2, b3, a3, b1, b2, b3. Sie benötigen diese beiden Abzugsebenen ( multiply_all, multiply_one), da Sie zwei Ebenen der "Variadizität" herabsteigen müssen, siehe meinen ersten Kommentar zu der Frage.
Max Langhof
9

Falten Sie die Ausdrücke zur Rettung erneut

template<typename... Ts>
typelist<typelist<Ts>...> layered(typelist<Ts...>);

template<typename... Ts, typename... Us>
auto operator+(typelist<Ts...>, typelist<Us...>)
    -> typelist<Ts..., Us...>;

template<typename T, typename... Us>
auto operator*(typelist<T>, typelist<Us...>)
    -> typelist<decltype(T{} + Us{})...>;

template<typename... Ts, typename TL>
auto operator^(typelist<Ts...>, TL tl)
    -> decltype(((typelist<Ts>{} * tl) + ...));

template<typename... TLs>
using product_t = decltype((layered(TLs{}) ^ ...));

Und du bist fertig. Dies hat den zusätzlichen Vorteil gegenüber der Rekursion, dass die Instanziierungstiefe O (1) beträgt.

struct A0;
struct A1;
struct B0;
struct B1;
struct C0;
struct C1;
struct C2;

using t1 = typelist<A0, A1>;
using t2 = typelist<B0, B1>;
using t3 = typelist<C0, C1, C2>; 

using p1 = product_t<t1, t2>;
using p2 = product_t<t1, t2, t3>;

using expect1 = typelist<typelist<A0, B0>,
                         typelist<A0, B1>,
                         typelist<A1, B0>,
                         typelist<A1, B1>>;

using expect2 = typelist<typelist<A0, B0, C0>,
                         typelist<A0, B0, C1>,
                         typelist<A0, B0, C2>,
                         typelist<A0, B1, C0>,
                         typelist<A0, B1, C1>,
                         typelist<A0, B1, C2>,
                         typelist<A1, B0, C0>,
                         typelist<A1, B0, C1>,
                         typelist<A1, B0, C2>,
                         typelist<A1, B1, C0>,
                         typelist<A1, B1, C1>,
                         typelist<A1, B1, C2>>;

static_assert(std::is_same_v<p1, expect1>);
static_assert(std::is_same_v<p2, expect2>);
Passant von
quelle
Das fasziniert mich. Gibt es eine Möglichkeit, es als TL1 * TL2 * TL3 = Crossporduct-Ergebnis darzustellen?
themagicalyang
@themagicalyang Was meinst du mit "produktübergreifendes Ergebnis"?
Passant Bis zum
im Grunde statt using result = product_t<t1,t2,t3>... eine Art, es als darzustellen using result = decltype(t1{} * t2{} * t3{});. Hmm, nun, da es darüber nachdenkt, da decltypees unvermeidlich ist, ist es intuitiver, einfach den von Ihnen angegebenen Alias ​​zu verwenden.
themagicalyang
Interessant! Wenn Sie die Operatorüberladung verwenden, erhalten Sie Falzausdrücke anstelle der Rekursionen, die ich durchführen musste. Macht es auch viel prägnanter. Ich werde es für das nächste Mal im Hinterkopf behalten!
Max Langhof
@PasserBy Müssen sich alle diese Hilfsoperatoren und Funktionen im selben Namespace befinden? Ich habe Probleme damit, alles in einen Namespace zu stellen und über einen Alias ​​von einem externen Namespace auf product_t zuzugreifen.
themagicalyang