Bagaimana saya bisa membuat produk Cartesian dari daftar tipe di C ++?

26

Cukup jelas.

Pada dasarnya, katakan saya memiliki daftar jenis seperti:

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

Mereka bisa menjadi nomor variadic dari daftar jenis.

Bagaimana cara saya mendapatkan daftar produk Cartesian?

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

Saya mencoba-coba tentang cara membuat produk Cartesian dua arah seperti yang diberikan di sini: Bagaimana cara membuat produk Cartesian dari daftar jenis? , tapi n jalan sepertinya tidak begitu sepele.

Untuk saat ini saya sedang mencoba ...

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

Saya hanya akan mengatakan bahwa mengingat betapa sulitnya untuk melakukannya dengan benar, gunakan saja dorongan seperti dalam jawaban oleh Barry. Sayangnya saya harus terjebak dengan pendekatan linting tangan karena menggunakan boost atau tidak adalah keputusan yang berasal dari tempat lain :(

themagicalyang
sumber
8
Oof, Anda rakus untuk hukuman 😏
Lightness Races in Orbit
Saya agak payah dalam hal itu, tetapi dapatkah Anda memodifikasi produk kartesian 2 arah dengan cara: 1) pengetik pertama sebenarnya adalah pengetik dari pengetik tipe 1; 2) alih-alih menggabungkan dua jenis dari daftar ketik, metafungsi akan menambahkan jenis dari daftar kedua ke daftar "anak" dari daftar ketik pertama (dalam cara-produk-kartesius)? Jika layak, masalahnya dapat dengan mudah diselesaikan dengan algoritma rekursif.
smitsyn
1
Kesulitan nyata dalam implementasi rekursif adalah bahwa itu cartesian_productadalah daftar daftar tipe, dan pada setiap langkah rekursi Anda ingin menambahkan item ke setiap daftar tipe dalam. Masuk ke tingkat pengemasan kedua dari paket ini membutuhkan pengurangan ...
Max Langhof
1
Saya kira Anda juga bisa mengimplementasikannya "secara linear" dengan melihat ini sebagai "tipe ruang" N-dimensi di mana Anda ingin melintasi setiap "titik tipe grid". Anda menghitung jumlah titik kisi, lalu Anda hanya melewatinya seperti yang Anda lakukan melalui array ND rata dan menghitung jenis di setiap titik kisi. Sesuatu untuk dipertimbangkan ...
Max Langhof
1
@ MaxLanghof Sesuatu di sepanjang baris " Sebuah produk cartesian dari tuple di C ++ 17 "?
Deduplicator

Jawaban:

14

Dengan Boost.Mp11 , ini adalah one-liner pendek (seperti biasa):

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

Demo .

Barry
sumber
1
Astaga ... Tapi saya merasa berkewajiban untuk menunjukkan bahwa (mengambil sampel setiap kode beberapa kali di godbolt) versi Mp11 membutuhkan waktu dua kali lebih lama untuk dikompilasi. Tidak yakin berapa banyak overhead yang mem-parsing header boost itu sendiri dan berapa banyak template instantiating ...
Max Langhof
1
@ MaxLanghof Tentu. 1.5x jika Anda hanya memasukkan algorithm.hppsemua MP11. Dan bahkan kemudian kita berbicara 0,08 vs 0,12. Harus memperhitungkan berapa lama aku menulis ini juga.
Barry
8
@ Larry: Dari sudut pandang rekayasa perangkat lunak, dengan Anda 100%. Ada juga betapa mudahnya membaca vs pendekatan linting. Juga ada sedikit atau tidak ada pengujian yang diperlukan untuk memastikan kebenaran solusi perpustakaan. Secara keseluruhan kode yang lebih sedikit dan kepercayaan yang lebih tinggi akan menyebabkan biaya perawatan yang lebih rendah untuk masa pakainya.
AndyG
Saya setuju ini cukup sederhana tapi sayangnya ada tim yang tidak senang.
themagicalyang
ada tim yang tidak menyukai segalanya. ini bukan alasan untuk tidak menggunakannya.
Tomaz Canabrava
13

OK mengerti. Itu tidak cantik tapi berhasil:

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

Saya meninggalkan static_asserttes saya sendiri di sana untuk ... Yah, saya harap mereka membantu.

Juga, saya yakin harus ada solusi yang lebih baik. Tapi ini adalah jalan "Aku tahu ini pada akhirnya akan mengarah ke tujuan". Saya akhirnya harus menggunakan menambahkan concatatau macam-macam, saya yakin itu bisa digunakan lebih awal untuk melewati sebagian besar cruft.

Max Langhof
sumber
4
Template pemrograman yang bisa saya ikuti. Itu luar biasa. Saya belajar sesuatu hari ini.
Jerry Jeremiah
add membutuhkan dua type_lists. Bagaimana Anda melewati beberapa daftar tipe untuk ditambahkan dalam concat?
themagicalyang
@ themagicalyang Terlihat dengan baik, itu bug (yang tes tidak menemukan karena semua daftar yang terlibat hanya panjang 2). The ...harus masuk ke dalam recursive concatpanggilan, bukan di luar. Jawaban (termasuk kasus uji) dikoreksi. Buktikan Barry benar tentang ekspektasi kebenaran :)
Max Langhof
Bukankah panggilan produk cartesian ke multiply_all pada dasarnya multiple_one?
themagicalyang
@themagicalyang No. cartesian_productmengimplementasikan rekursi. multiply_allmelakukan multiply_oneuntuk setiap daftar tipe dalam TLspaket. cartesian_product::typeadalah daftar daftar jenis. multiply_allmengambil daftar jenis dan daftar daftar jenis. multiply_oneDibutuhkan dua daftar jenis a1, a2, a3dan b1, b2, b3dan menciptakan a1, b1, b2, b3, a2, b1, b2, b3, a3, b1, b2, b3. Anda memerlukan dua level deduksi ( multiply_all, multiply_one) ini karena Anda harus menurunkan dua level "variadicness", lihat komentar pertama saya pada pertanyaan.
Max Langhof
9

Lipat ekspresi untuk menyelamatkan lagi

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

Dan kamu sudah selesai. Ini memiliki manfaat tambahan atas rekursi memiliki kedalaman instantiasi 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>);
Melewati
sumber
Ini membuat saya penasaran. Apakah ada cara untuk menggambarkannya sebagai TL1 * TL2 * TL3 = hasil crossporduct?
themagicalyang
@themagicalyang Apa yang Anda maksud dengan "hasil lintas produk"?
Passer By
pada dasarnya alih-alih using result = product_t<t1,t2,t3>... beberapa cara untuk menggambarkannya sebagai using result = decltype(t1{} * t2{} * t3{});. Hmm, nah sekarang sudah dipikir-pikir, karena decltypetidak bisa dihindari, cukup menggunakan alias yang Anda berikan lebih intuitif.
themagicalyang
Menarik! Menggunakan overloading operator memberi Anda lipat ekspresi alih-alih rekursi yang harus saya lakukan. Juga membuatnya lebih ringkas. Saya akan mengingatnya untuk waktu berikutnya!
Max Langhof
@ PaserBy Apakah semua operator pembantu dan fungsinya harus berada dalam namespace yang sama? Saya mendapatkan masalah dengan meletakkan segala sesuatu di dalam namespace dan mengakses product_t menggunakan alias dari luar namespace.
themagicalyang