Jak mogę stworzyć sposób kartezjańskiego produktu list typów w C ++?

26

Wyjaśniające.

Zasadniczo powiedz, że mam takie listy typów:

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

Mogą to być różne listy typów.

Jak uzyskać listę typową produktu kartezjańskiego?

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

Zastanawiałem się, jak stworzyć dwukierunkowy produkt kartezjański, jak podano tutaj: Jak stworzyć produkt kartezjański z listy typów? , ale żaden sposób nie wydaje się taki trywialny.

Na razie próbuję ...

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

Powiem tylko, że biorąc pod uwagę, jak trudno jest to zrobić poprawnie, po prostu użyj wzmocnienia, jak w odpowiedzi Barry'ego. Niestety muszę utknąć w podejściu ręcznie toczonym, ponieważ użycie boosta lub nie jest decyzją, która pochodzi z innego miejsca :(

themagicalyang
źródło
8
O, jesteś żarłokiem za karę 😏
Lightness Races in Orbit
W pewnym sensie jestem do niczego, ale czy możesz zmodyfikować dwukierunkowy kartezjański produkt w taki sposób, że: 1) pierwsza lista jest faktycznie listą typów 1 typu; 2) zamiast łączenia dwóch typów z list maszynopisu, metafunkcja dodawałaby typy z drugiej listy do „potomnych” list pierwszej listy (w sposób kartezjański)? Jeśli jest to wykonalne, problem można łatwo rozwiązać za pomocą algorytmu rekurencyjnego.
smitsyn,
1
Prawdziwa trudność w implementacji rekurencyjnej polega na tym, że cartesian_productjest to lista list typów, a na każdym kroku rekursji chcesz dołączyć elementy do każdej wewnętrznej listy typów. Wejście na drugi poziom pakowania paczki wymaga pewnej dedukcji ...
Max Langhof,
1
Wydaje mi się, że można to również zaimplementować „liniowo”, patrząc na to jako „przestrzeń typu N”, w której chcesz przechodzić przez każdy „punkt siatki typu”. Obliczasz liczbę punktów siatki, a następnie przechodzisz przez nią tak, jak w przypadku spłaszczonej tablicy ND i obliczasz typy w każdym punkcie siatki. Coś do rozważenia ...
Max Langhof
1
@MaxLanghof Coś w stylu „ Kartezjańskiego produktu krotek w C ++ 17 ”?
Deduplicator,

Odpowiedzi:

14

W przypadku Boost.Mp11 jest to krótki linijka (jak zawsze):

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

Demo .

Barry
źródło
1
Święta krowa ... Ale czuję się zobowiązany do wskazania, że ​​(próbkowanie każdego kodu kilka razy na godbolt) kompilacja wersji MP11 trwa około dwa razy dłużej. Nie jestem pewien, ile z tego narzutu parsuje sam nagłówek boost, a ile tworzy szablony ...
Max Langhof
1
@MaxLanghof Sure. 1,5x, jeśli podasz tylko algorithm.hppzamiast Mp11. I nawet wtedy mówimy o 0,08s vs 0,12s. Muszę wziąć pod uwagę, ile czasu zajęło mi napisanie tego.
Barry
8
@ Barry: Z punktu widzenia inżynierii oprogramowania, z tobą w 100%. Jest też to, jak łatwo to odczytać w porównaniu z podejściem wykonywanym ręcznie. Ponadto niewiele jest wymaganych testów, aby zapewnić poprawność rozwiązania bibliotecznego. Ogólnie mniej kodu i większa pewność doprowadzą do obniżenia kosztów utrzymania przez cały okres jego użytkowania.
AndyG,
Zgadzam się, że jest to dość proste, ale niestety istnieją zespoły, które marszczą brwi po wzmocnieniu.
themagicalyang
są drużyny, które marszczą brwi na wszystko. nie jest to powód, aby go nie używać.
Tomaz Canabrava,
13

Ok, rozumiem. To nie jest ładne, ale działa:

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

Zostawiłem tam własne static_asserttesty dla ... Mam nadzieję, że pomogą.

Jestem też pewien, że musi być lepsze rozwiązanie. Ale to była oczywista ścieżka „wiem, że ostatecznie doprowadzi to do celu”. W końcu musiałem skorzystać z dodania a concatlub sorts, jestem pewien, że można go użyć znacznie wcześniej, aby pominąć większość cruft.

Max Langhof
źródło
4
Programowanie szablonów, które mogę śledzić. To cudownie. Nauczyłem się dziś czegoś.
Jerry Jeremiah
add zajmuje dwie listy_typów. Jak mijasz wiele list typów do dodania w konkat?
themagicalyang
@themagicalyang Dobrze zauważony, to błąd (którego testy nie znalazły, ponieważ wszystkie zaangażowane listy miały tylko długość 2). ...Musi przejść wewnątrz rekurencyjnego concatwywołania, a nie na zewnątrz. Odpowiedź (w tym przypadki testowe) poprawiona. Udowadnia, że ​​Barry ma rację co do oczekiwań dotyczących poprawności :)
Max Langhof
Czy kartezjańskie wywołanie produktu do multiply_all nie jest po prostu multip_one?
themagicalyang
@themagicalyang No. cartesian_productimplementuje rekurencję. multiply_allrobi multiply_onedla każdej listy typów w TLspaczce. cartesian_product::typeto lista list typów. multiply_allpobiera listę typów i listę list typów. multiply_onezajmuje dwie listy typu a1, a2, a3a b1, b2, b3i tworzy a1, b1, b2, b3, a2, b1, b2, b3, a3, b1, b2, b3. Potrzebujesz tych dwóch poziomów dedukcji ( multiply_all, multiply_one), ponieważ musisz zejść o dwa poziomy „różnorodności”, patrz mój pierwszy komentarz do pytania.
Max Langhof,
9

Ponownie złóż wyrażenia na ratunek

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{}) ^ ...));

I jesteś skończony. Ma to dodatkową zaletę w stosunku do rekurencji o głębokość tworzenia instancji O (1).

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>);
Przechodzień
źródło
To mnie intryguje. Czy istnieje sposób, aby przedstawić go jako wynik TL1 * TL2 * TL3 = wynik krzyżówki?
themagicalyang
@themagicalyang Co rozumiesz przez „wynik krzyżowy produktu”?
Przechodzień Do
w zasadzie zamiast using result = product_t<t1,t2,t3>... w jakiś sposób przedstawić to jako using result = decltype(t1{} * t2{} * t3{});. Hmm, cóż, teraz, gdy się nad tym zastanowić, ponieważ decltypejest to nieuniknione, po prostu użycie podanego aliasu jest bardziej intuicyjne.
themagicalyang
Ciekawy! Korzystanie z przeciążania operatora daje wyrażenia składane zamiast rekurencji, które musiałem wykonać. Sprawia również, że jest bardziej zwięzły. Będę o tym pamiętać następnym razem!
Max Langhof,
@PasserBy Czy wszyscy operatorzy pomocniczy i funkcje muszą znajdować się w tej samej przestrzeni nazw? Mam problemy z umieszczaniem wszystkiego w przestrzeni nazw i uzyskiwaniem dostępu do product_t przy użyciu aliasu z zewnętrznej przestrzeni nazw.
themagicalyang