Как я могу создать способ декартово произведение списков типов в C ++?

26

Самоочевидно.

В основном, скажем, у меня есть списки типов, например, так:

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

Они могут быть различными числами списков типов.

Как я могу получить список картезианского продукта?

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

Я попробовал создать двустороннее декартово произведение, как показано здесь: Как создать декартово произведение списка типов? , но русский путь, кажется, не так тривиально.

Сейчас я пытаюсь ...

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

Я просто скажу, что, учитывая, насколько сложно это сделать правильно, просто используйте повышение, как в ответе Барри. К сожалению, я должен быть застрял с ручным подходом, потому что использовать повышение или нет - решение, которое приходит откуда-то еще :(

themagicalyang
источник
8
Оф, ты жаждешь наказания 😏
Гонки
Я вроде бы отстой, но можете ли вы модифицировать двустороннее декартово произведение таким образом, чтобы: 1) первый список типов был фактически списком типов 1 типа; 2) вместо объединения двух типов из списков типов, метафункция добавит типы из второго списка в «дочерние» списки первого списка типов (в декартовой-путевой форме)? Если это возможно, проблема может быть легко решена с помощью рекурсивного алгоритма.
Смицын
1
Реальная трудность в рекурсивной реализации состоит в том, что cartesian_productэто список списков типов, и на каждом шаге рекурсии вы хотите добавлять материал в каждый внутренний список типов. Попадание в этот второй уровень упаковки требует некоторого вычета ...
Макс Лангхоф
1
Я думаю, вы также можете реализовать это «линейно», рассматривая это как N-мерное «пространство типов», где вы хотите пересечь каждую «точку сетки типов». Вы вычисляете количество точек сетки, затем просто проходите его, как если бы вы делали плоский массив ND, и вычисляете типы в каждой точке сетки. Что-то, чтобы рассмотреть ...
Макс
1
@MaxLanghof Что-то вроде " Декартово произведение кортежей в C ++ 17 "?
Дедупликатор

Ответы:

14

С Boost.Mp11 это короткий однострочный (как всегда):

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

Demo .

Барри
источник
1
Святая корова ... Но я чувствую себя обязанным отметить, что (выборка каждого кода несколько раз на Godbolt) версия Mp11 компилируется примерно вдвое дольше. Не уверен, сколько из этих накладных расходов разбирает сам заголовок
Max
1
@MaxLanghof Конечно. 1.5x, если вы включаете только algorithm.hppвсе Mp11. И даже тогда мы говорим 0,08 с 0,12 с. Нужно учитывать, сколько времени мне понадобилось, чтобы написать это тоже.
Барри
8
@ Барри: С точки зрения разработки программного обеспечения, с вами 100%. Есть также, как легко это читать против ручного подхода. Кроме того, тестирование практически не требуется для обеспечения правильности решения библиотеки. В целом, меньше кода и более высокая достоверность приведут к снижению затрат на обслуживание в течение всего срока его службы
AndyG
Я согласен, что это довольно просто, но, к сожалению, есть команды, которые нахмурились на повышение.
themagicalyang
есть команды, которые осуждают все. это не причина не использовать это.
Томаз Канабрава
13

Хорошо понял. Это не красиво, но это работает:

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

Я оставил там свои собственные static_assertтесты для ... Ну, я надеюсь, они помогут.

Кроме того, я уверен, что должно быть лучшее решение. Но это был очевидный путь «я знаю, что это в конечном итоге приведет к цели». В конце концов мне пришлось прибегнуть к добавлению concatили сортировки, я уверен, что это можно было использовать намного раньше, чтобы пропустить большую часть промахов.

Макс Лангоф
источник
4
Шаблонное программирование, которому я могу следовать. Это потрясающе. Я кое-что узнал сегодня.
Джерри Иеремия
add занимает два type_lists. Как вы передаете несколько списков типов для добавления в concat?
themagicalyang
@themagicalyang Хорошо заметили, что это ошибка (которую тесты не обнаружили, потому что все задействованные списки были только длиной 2). ...Должен идти внутри рекурсивного concatвызова, а не снаружи. Ответ (включая контрольные примеры) исправлен. Доказывает, что Барри прав в отношении правильности ожиданий :)
Макс
Разве декартово произведение не призывает к multiply_all в основном множественный_one?
themagicalyang
@themagicalyang Нет. cartesian_productреализует рекурсию. multiply_allделает multiply_oneдля каждого списка типов в TLsпакете. cartesian_product::typeсписок списков типов multiply_allпринимает список типов и список списков типов. multiply_oneпринимает два списка типа a1, a2, a3и b1, b2, b3и создает a1, b1, b2, b3, a2, b1, b2, b3, a3, b1, b2, b3. Вам нужны эти два уровня дедукции ( multiply_all, multiply_one), потому что вам нужно спуститься вниз на два уровня «вариативности», см. Мой первый комментарий к вопросу.
Макс
9

Сложите выражения снова на помощь

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

И вы сделали. Это имеет дополнительное преимущество по сравнению с рекурсией, имея 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>);
Прохожий
источник
Это меня интригует. Есть ли способ представить его как TL1 * TL2 * TL3 = кросс-проводной результат?
themagicalyang
@themagicalyang Что вы подразумеваете под "результатом перекрестного продукта"?
Прохожий
в основном вместо using result = product_t<t1,t2,t3>... какой-то способ представить это как using result = decltype(t1{} * t2{} * t3{});. Хм, хорошо, теперь, когда он думает об этом, поскольку decltypeэто неизбежно, просто использование псевдонима, как вы дали, является более интуитивным.
themagicalyang
Интересно! Использование перегрузки операторов дает вам выражения сгиба вместо рекурсий, которые я должен был сделать. Также делает это намного более кратким. Я буду помнить это в следующий раз!
Макс Лангхоф
@PasserBy Должны ли все эти вспомогательные операторы и функции находиться в одном пространстве имен? У меня возникают проблемы с помещением всего в пространство имен и доступом к product_t с использованием псевдонима из внешнего пространства имен.
themagicalyang