¿Cómo puedo crear un producto cartesiano de listas de tipos en C ++?

26

Autoexplicativo.

Básicamente, digamos que tengo listas de tipos así:

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

Pueden ser un número variado de listas de tipos.

¿Cómo obtengo una lista de tipos de productos cartesianos?

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

Aprendí cómo crear un producto cartesiano bidireccional como se indica aquí: ¿Cómo crear el producto cartesiano de una lista de tipos? , pero parece que no es tan trivial.

Por ahora estoy intentando ...

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

Solo diré que teniendo en cuenta lo difícil que es hacerlo bien, solo usa boost como en la respuesta de Barry. Desafortunadamente, tengo que estar atascado con un enfoque enrollado a mano porque usar boost o no es una decisión que proviene de otro lugar :(

themagicalyang
fuente
8
Oof, eres un glotón para el castigo 😏
Lightness Races in Orbit
Me apesta un poco, pero ¿puede modificar el producto cartesiano de 2 vías de una manera que: 1) la primera lista de tipos es en realidad una lista de tipos de listas de tipos de 1 tipo; 2) en lugar de concatenar dos tipos de listas de tipos, la metafunción agregaría los tipos de la segunda lista a las listas "secundarias" de la primera lista de tipos (de una manera cartesiana-producto)? Si es factible, el problema se puede resolver fácilmente con un algoritmo recursivo.
smitsyn
1
La verdadera dificultad en una implementación recursiva es que cartesian_productes una lista de listas de tipos, y en cada paso de recursión desea agregar cosas a cada lista de tipos interna. Entrar en ese segundo nivel de empaquetamiento de paquete lleva algún deducción ...
Max Langhof
1
Supongo que también podría implementarlo "linealmente" al ver esto como un "espacio de tipo" N-dimensional donde desea atravesar cada "punto de cuadrícula de tipo". Calcula el número de puntos de la cuadrícula, luego lo atraviesa como lo haría a través de una matriz ND aplanada y calcula los tipos en cada punto de la cuadrícula. Algo a tener en cuenta ...
Max Langhof
1
@MaxLanghof ¿Algo parecido a " Un producto cartesiano de tuplas en C ++ 17 "?
Deduplicador el

Respuestas:

14

Con Boost.Mp11 , este es un breve resumen (como siempre):

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

Demostración .

Barry
fuente
1
Santa vaca ... Pero me siento obligado a señalar que (muestreando cada código varias veces en godbolt) la versión Mp11 tarda aproximadamente el doble de tiempo en compilarse. No estoy seguro de cuánto de esa sobrecarga está analizando el encabezado de impulso en sí y cuánto está instanciando plantillas ...
Max Langhof
1
@MaxLanghof Claro. 1.5x si solo incluye en algorithm.hpplugar de todo Mp11. E incluso entonces estamos hablando 0.08s vs 0.12s. Tengo que tener en cuenta cuánto tiempo me llevó escribir esto también.
Barry
8
@Barry: desde el punto de vista de la ingeniería de software, con usted al 100%. También está lo fácil que es leer frente a un enfoque manual. Además, se requiere poca o ninguna prueba para garantizar la corrección de la solución de la biblioteca. En general, menos código y una mayor confianza conducirán a menores costos de mantenimiento durante su vida útil.
AndyG
Estoy de acuerdo en que esto es bastante simple, pero desafortunadamente existen equipos que desaprueban el impulso.
themagicalyang
Hay equipos que desaprueban todo. Esta no es una razón para no usarlo.
Tomaz Canabrava
13

Ok lo tengo. No es bonito pero funciona:

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

Dejé mis propias static_assertpruebas allí para ... Bueno, espero que me ayuden.

Además, estoy seguro de que tiene que haber una mejor solución. Pero este era el camino obvio "Sé que esto eventualmente conducirá a la meta". Eventualmente tuve que recurrir a agregar una concato más, estoy seguro de que podría usarse mucho antes para omitir la mayor parte del cruft.

Max Langhof
fuente
44
Programación de plantillas que puedo seguir. Eso es genial. Aprendí algo hoy.
Jerry Jeremiah
add toma dos type_lists. ¿Cómo pasa múltiples listas de tipos para agregar en concat?
themagicalyang
@themagicalyang Bien visto, eso es un error (que las pruebas no encontraron porque todas las listas involucradas eran solo de longitud 2). El ...tiene que ir dentro de la recursiva concatllamada, no afuera. Respuesta (incluidos los casos de prueba) corregida. Prueba que Barry tiene razón con respecto a las expectativas de corrección :)
Max Langhof
¿No es la llamada del producto cartesiano a multiply_all básicamente un multiple_one?
themagicalyang
@themagicalyang No. cartesian_productimplementa la recursividad. multiply_allhace una multiply_onelista para cada tipo en el TLspaquete. cartesian_product::typees una lista de listas de tipos. multiply_alltoma una lista de tipos y una lista de listas de tipos. multiply_onetoma dos tipos de listas a1, a2, a3y b1, b2, b3y crea a1, b1, b2, b3, a2, b1, b2, b3, a3, b1, b2, b3. Necesita estos dos niveles de deducción ( multiply_all, multiply_one) porque necesita descender por dos niveles de "variabilidad", vea mi primer comentario sobre la pregunta.
Max Langhof
9

Doblar expresiones al rescate otra vez

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

Y tu estas listo. Esto tiene el beneficio adicional sobre la recursividad de tener O (1) profundidad de instanciación.

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>);
Transeúnte
fuente
Esto me intriga. ¿Hay alguna manera de representarlo como TL1 * TL2 * TL3 = resultado del producto cruzado?
themagicalyang
@themagicalyang ¿Qué quiere decir con "resultado de producto cruzado"?
Pasador antes del
básicamente en lugar de using result = product_t<t1,t2,t3>... alguna forma de representarlo como using result = decltype(t1{} * t2{} * t3{});. Hmm, bueno, ahora que lo piensa, ya que decltypees inevitable, simplemente usar el alias que le dio es más intuitivo.
themagicalyang
¡Interesante! El uso de la sobrecarga del operador le da expresiones plegables en lugar de las recursiones que tuve que hacer. También lo hace mucho más conciso. Lo tendré en cuenta para la próxima vez!
Max Langhof
@PasserBy ¿Todos esos operadores y funciones auxiliares deben estar en el mismo espacio de nombres? Tengo problemas para poner todo dentro de un espacio de nombres y acceder a product_t usando un alias del espacio de nombres externo.
themagicalyang