Как создать декартово произведение списка типов?

Ответ 1

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

#include <iostream>
#include <typeinfo>
#include <cxxabi.h>

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

template<typename T1, typename T2> struct type_pair {};

template<typename T, typename... Rest>
  struct row
{
  typedef type_list<type_pair<T,Rest>...> type;
};

template <typename... T> struct concat;
template <typename... S, typename... T>
struct concat<type_list<S...>, type_list<T...>>
{
    typedef type_list<S..., T...> type;
};

template <typename... T>
struct expand
{
    typedef type_list<T...> type;
};
template <> struct expand<> { typedef type_list<> type; };
template <typename... T, typename... L>
struct expand<type_list<T...>, L...>
{
    typedef typename concat<typename expand<T...>::type, typename expand<L...>::type>::type type;
};

template<typename... T>
  struct cross_product
{
    typedef typename expand<type_list<typename row<T,T...>::type...>>::type type;

};

int main()
{
  int s;
  typedef cross_product<int, float, short>::type result;
  std::cout << abi::__cxa_demangle(typeid(result).name(), 0, 0, &s) << std::endl;

  return 0;
}

Ответ 2

Хорошая чистая версия, я думаю:

cross_product.cpp:

#include "type_printer.hpp"

#include <iostream>

template<typename ...Ts> struct type_list {};
template<typename T1, typename T2> struct pair {};

// Concatenation
template <typename ... T> struct concat;
template <typename ... Ts, typename ... Us>
struct concat<type_list<Ts...>, type_list<Us...>>
{
    typedef type_list<Ts..., Us...> type;
};

// Cross Product
template <typename T, typename U> struct cross_product;

// Partially specialise the empty case for the first type_list.
template <typename ...Us>
struct cross_product<type_list<>, type_list<Us...>> {
    typedef type_list<> type;
};

// The general case for two type_lists. Process:
// 1. Expand out the head of the first type_list with the full second type_list.
// 2. Recurse the tail of the first type_list.
// 3. Concatenate the two type_lists.
template <typename T, typename ...Ts, typename ...Us>
struct cross_product<type_list<T, Ts...>, type_list<Us...>> {
    typedef typename concat<
        type_list<pair<T, Us>...>,
        typename cross_product<type_list<Ts...>, type_list<Us...>>::type
    >::type type;
};

struct A {};
struct B {};
struct C {};
struct D {};
struct E {};
struct F {};

template <typename T, typename U>
void test()
{
    std::cout << print_type<T>() << " \u2a2f " << print_type<U>() << " = "
        << print_type<typename cross_product<T, U>::type>() << std::endl;
}

int main()
{
    std::cout << "Cartesian product of type lists\n";
    test<type_list<>, type_list<>>();
    test<type_list<>, type_list<A>>();
    test<type_list<>, type_list<A, B>>();
    test<type_list<A, B>, type_list<>>();
    test<type_list<A>, type_list<B>>();
    test<type_list<A>, type_list<B, C, D>>();
    test<type_list<A, B>, type_list<B, C, D>>();
    test<type_list<A, B, C>, type_list<D>>();
    test<type_list<A, B, C>, type_list<D, E, F>>();
    return 0;
}

type_printer.hpp:

#ifndef TYPE_PRINTER_HPP
#define TYPE_PRINTER_HPP

#include "detail/type_printer_detail.hpp"

template <typename T>
std::string print_type()
{
    return detail::type_printer<T>()();
}

#endif

деталь /type _printer_detail.hpp:

#ifndef DETAIL__TYPE_PRINTER_DETAIL_HPP
#define DETAIL__TYPE_PRINTER_DETAIL_HPP

#include <typeinfo>
#include <cxxabi.h>
#include <string>

template <typename ...Ts> struct type_list;
template <typename T1, typename T2> struct pair;

namespace detail {

// print scalar types
template <typename T>
struct type_printer {
    std::string operator()() const {
        int s;
        return abi::__cxa_demangle(typeid(T).name(), 0, 0, &s);
    }   
};

// print pair<T, U> types
template <typename T, typename U>
struct type_printer<pair<T, U>> {
    std::string operator()() const {
        return "(" + type_printer<T>()() + "," + type_printer<U>()() + ")";
    }   
};

// print type_list<T>
template <>
struct type_printer<type_list<>> {
    std::string operator()() const {
        return "\u2205";
    }   
};

template <typename T>
struct type_printer<type_list<T>> {
    std::string operator()() const {
        return "{" + type_printer<T>()() + "}";
    }   
    std::string operator()(const std::string& sep) const {
        return sep + type_printer<T>()();
    }   
};

template <typename T, typename ...Ts>
struct type_printer<type_list<T, Ts...>> {
    std::string operator()() const {
        return "{" + type_printer<T>()() + type_printer<type_list<Ts...>>()(std::string(", ")) + "}";
    }   
    std::string operator()(const std::string& sep) const {
        return sep + type_printer<T>()() + type_printer<type_list<Ts...>>()(sep);
    }   
};
}

#endif

Run:

g++ -std=c++0x cross_product.cpp && ./a.out

Вывод:

Cartesian product of type lists
∅ ⨯ ∅ = ∅
∅ ⨯ {A} = ∅
∅ ⨯ {A, B} = ∅
{A, B} ⨯ ∅ = ∅
{A} ⨯ {B} = {(A,B)}
{A} ⨯ {B, C, D} = {(A,B), (A,C), (A,D)}
{A, B} ⨯ {B, C, D} = {(A,B), (A,C), (A,D), (B,B), (B,C), (B,D)}
{A, B, C} ⨯ {D} = {(A,D), (B,D), (C,D)}
{A, B, C} ⨯ {D, E, F} = {(A,D), (A,E), (A,F), (B,D), (B,E), (B,F), (C,D), (C,E), (C,F)}

(Я заметил, что в Windows с использованием Chrome символ юникода с перекрестным продуктом не выходит хорошо. Извините, я не знаю, как это исправить.)

Ответ 3

Возможно, что-то вроде этого:

template <typename ...Args> struct typelist { };

template <typename S, typename T> struct typelist_cat;

template <typename ...Ss, typename ...Ts>
struct typelist_cat<typelist<Ss...>, typelist<Ts...>>
{
    typedef typelist<Ss..., Ts...> type;
};


template <typename S, typename T> struct product;

template <typename S, typename ...Ss, typename ...Ts>
struct product<typelist<S, Ss...>, typelist<Ts...>>
{
    // the cartesian product of {S} and {Ts...}
    // is a list of pairs -- here: a typelist of 2-element typelists
    typedef typelist<typelist<S, Ts>...> S_cross_Ts;

    // the cartesian product of {Ss...} and {Ts...} (computed recursively)
    typedef typename product<typelist<Ss...>, typelist<Ts...>>::type
        Ss_cross_Ts;

    // concatenate both products
    typedef typename typelist_cat<S_cross_Ts, Ss_cross_Ts>::type type;
};

// end the recursion
template <typename ...Ts>
struct product<typelist<>, typelist<Ts...>>
{
    typedef typelist<> type;
};

Теперь вы сможете использовать product<typelist<A,B,C>, typelist<D,E,F>>::type.

Ответ 4

Здесь другое решение.

#include <iostream>
#include <typeinfo>
#include <cxxabi.h>

template <typename ...Args> struct typelist { };
template <typename, typename> struct typepair { };

template <typename S, typename T> struct product;
template <typename S, typename T> struct append;

template<typename ...Ss, typename ...Ts>
struct append<typelist<Ss...>, typelist<Ts...>> {
  typedef typelist<Ss..., Ts...> type;
};

template<>
struct product<typelist<>, typelist<>> {
  typedef typelist<> type;
};

template<typename ...Ts>
struct product<typelist<>, typelist<Ts...>> {
  typedef typelist<> type;
};

template<typename ...Ts>
struct product<typelist<Ts...>, typelist<>> {
  typedef typelist<> type;
};

template<typename S, typename T, typename ...Ss, typename ...Ts>
struct product<typelist<S, Ss...>, typelist<T, Ts...>> {
  typedef typename
          append<typelist<typepair<S, T>,
                          typepair<S, Ts>...,
                          typepair<Ss, T>...>,
        typename product<typelist<Ss...>, typelist<Ts...>>::type>::type type;
};

int main(void)
{
  int s;
  std::cout << abi::__cxa_demangle(
  typeid(product<typelist<int, float>, typelist<short, double>>::type).name(), 0, 0, &s)     << "\n";
  return 0;
}

Ответ 5

Пока все решения имеют недостатки, ненужные зависимости, ненужные помощники, и все они ограничены декартовой степенью двух. Следующее решение не имеет таких недостатков и поддерживает:

• Любая декартова мощность, включая 0.
• Возврат пустого набора, если любой из факторов является пустым.
• Код является самодостаточным и не зависит от каких-либо файлов include.
• Входы функции могут быть любого типа шаблона.
• Тип выходного списка можно указать с помощью первого шаблона параметр.

На самом деле было труднее реализовать (но хорошо, как домашнее задание), тогда я подумал. Я на самом деле думаю о создании небольшого генератора, который позволяет мне расширенный синтаксис шаблона, который делает эти вещи очень легкими.

Упрощенный код работает следующим образом: product преобразует список ввода tuple<A...>,tuple<B...>,tuple<C...> в tuple<tuple<A>...>, tuple<B...>, tuple<C...>. Затем этот второй список передается в product_helper, который выполняет вычисление рекурсивных декартовых произведений.

template <typename... T> struct cat2;

template <template<typename...> class R, typename... As, typename... Bs>
struct cat2 <R<As...>, R<Bs...> > {
        using type = R <As..., Bs...>;
};

template <typename... Ts> struct product_helper;

template <template<typename...> class R, typename... Ts>
struct product_helper < R<Ts...> > { // stop condition
        using type = R< Ts...>;
};

template <template<typename...> class R, typename... Ts>
struct product_helper < R<R<> >, Ts... > { // catches first empty tuple
        using type = R<>;
};

template <template<typename...> class R, typename... Ts, typename... Rests>
struct product_helper < R<Ts...>, R<>, Rests... > { // catches any empty tuple except first
        using type = R<>;
};

template <template<typename...> class R, typename... X, typename H, typename... Rests>
struct product_helper < R<X...>, R<H>, Rests... > {
        using type1 = R <typename cat2<X,R<H> >::type...>;
        using type  = typename product_helper<type1, Rests...>::type;
};

template <template<typename...> class R, typename... X, template<typename...> class Head, typename T, typename... Ts, typename... Rests>
struct product_helper < R<X...>, Head<T, Ts...>, Rests... > {
        using type1 = R <typename cat2<X,R<T> >::type...>;
        using type2 = typename product_helper<R<X...> , R<Ts...> >::type;
        using type3 = typename cat2<type1,type2>::type;
        using type  = typename product_helper<type3, Rests...>::type;
};

template <template<typename...> class R, typename... Ts> struct product;

template <template<typename...> class R>
struct product < R > { // no input, R specifies the return type
    using type = R<>;
};

template <template<typename...> class R, template<typename...> class Head, typename... Ts, typename... Tail>
struct product <R, Head<Ts...>, Tail... > { // R is the return type, Head<A...> is the first input list
    using type = typename product_helper< R<R<Ts>...>, Tail... >::type;
};

Вот компилируемый пример того, как код можно использовать.

Ответ 6

Примечание. Это НЕ то, о чем попросил ОП... но может иметь отношение к другим (как и я), которые спотыкаются на этот вопрос. Вот как это можно сделать, используя Loki:: TypeList (т.е. предшествующий С++ - 11), возможно, имеющий исторический интерес или для обеспечения совместимости.

Кроме того, возможно, я самонадеянно загрязняю пространство имен loki. YMMV.

crossproduct.h

#include "loki/NullType.h"
#include "loki/Typelist.h"

namespace Loki {
namespace   TL {

/// a pair of two types
template <typename A_t, typename B_t>
struct TypePair
{
    typedef A_t A;
    typedef B_t B;
};


/// a template which takes one type and pairs it with all other types
/// in another typelist
template <class T, class TList > struct DistributePair;

/// specialization of Distribute for the nulltype
template < class TList >
struct DistributePair< NullType, TList >
{
     typedef NullType type;
};


/// specialization of Distribute where the second parameter is nulltype
template <class T >
struct DistributePair< T, NullType >
{
     typedef NullType type;
};

/// specialization of Distribute where the first parameter is a
/// typelist
template <class T, class Head, class Tail >
struct DistributePair< T, Typelist<Head,Tail> >
{
     typedef Typelist<
                 TypePair<T,Head>,
                 typename DistributePair<T,Tail>::type
                     > type;
};

/// performs cartesion product of two typelists
template <class TListA, class TListB> struct CrossProduct;

/// specialization of CrossProduct for NullType
template <class TListB>
struct CrossProduct< NullType, TListB >
{
    typedef NullType type;
};

/// specialization of CrossProduct for recursion
template <class Head, class Tail, class TListB>
struct CrossProduct< Typelist<Head,Tail>, TListB >
{
    typedef typename Append<
            typename DistributePair< Head,TListB >::type,
            typename CrossProduct< Tail, TListB >::type
              >::Result type;
};

} // namespace TL
} // namespace Loki

test.cpp

#include <crossproduct.h>
#include <loki/HierarchyGenerators.h>
#include <iostream>

struct A{};
struct B{};
struct C{};

struct D{};
struct E{};
struct F{};

typedef LOKI_TYPELIST_3(A,B,C)  TypeListA_t;
typedef LOKI_TYPELIST_3(D,E,F)  TypeListB_t;

typedef typename Loki::TL::CrossProduct< TypeListA_t, TypeListB_t >::type Cross_t;

template <typename T> const char* toString();

template <> const char* toString<A>(){ return "A"; };
template <> const char* toString<B>(){ return "B"; };
template <> const char* toString<C>(){ return "C"; };
template <> const char* toString<D>(){ return "D"; };
template <> const char* toString<E>(){ return "E"; };
template <> const char* toString<F>(){ return "F"; };

template <typename T> struct Printer
{
    Printer()
    {
        std::cout << toString<T>() << ", ";
    }
};

template <typename T1, typename T2>
struct Printer< Loki::TL::TypePair<T1,T2> >
{
    Printer()
    {
        std::cout << "(" << toString<T1>() << "," << toString<T2>() << "), ";
    }
};


typedef Loki::GenScatterHierarchy< TypeListA_t, Printer > PrinterA_t;
typedef Loki::GenScatterHierarchy< TypeListB_t, Printer > PrinterB_t;
typedef Loki::GenScatterHierarchy< Cross_t, Printer >     PrinterCross_t;

int main(int argc, char** argv)
{
    std::cout << "\nType list A: \n   ";
    PrinterA_t a;
    std::cout << "\nType list B: \n   ";
    PrinterB_t b;
    std::cout << "\nType list Cross: \n   ";
    PrinterCross_t cross;

    return 0;
}

Выход

Type list A: 
   A, B, C, 
Type list B: 
   D, E, F, 
Type list Cross: 
   (A,D), (A,E), (A,F), (B,D), (B,E), (B,F), (C,D), (C,E), (C,F), 

Ответ 7

Действительно понравилось это задание "домашняя работа":)

Оба решения ниже создают класс, полный typedefs type_list, а также функции-члены, которые будут проверять, существует ли определенный список типов в классе как type_list.

Первое решение создает все возможные комбинации типов от 1 до N типов для каждого типа_list (параметр width определяет N). Только проверил поверхностное тестирование, но я уверен, что он создает все возможные комбо. Второе решение создает только пары типов.

Первое решение

template<typename... Ts> struct type_list { typedef type_list<Ts...> type; };

template<size_t, typename...> struct xprod_tlist_ {};

template<typename... Ts, typename... Us>
struct xprod_tlist_<1, type_list<Ts...>, Us...> {};

template<size_t width, typename... Ts, typename... Us>
struct xprod_tlist_<width, type_list<Ts...>, Us...>
: type_list<Ts..., Us>...
, xprod_tlist_<width - 1, type_list<Ts..., Us>, Us...>... {};

template<size_t width, typename... Ts> struct xprod_tlist
: type_list<Ts>..., xprod_tlist_<width, type_list<Ts>, Ts...>... {
    template<typename... Us> struct exists
    : std::is_base_of<type_list<Us...>, xprod_tlist<width, Ts...>> {};

    template<typename... Us> struct assert_exists {
        static_assert(exists<Us...>::value, "Type not present in list");
    };
};

Использование:

typedef xprod_tlist<5, int, char, string, float, double, long> X;

//these pass
X::assert_exists<int, int, int, int, int> assert_test1;
X::assert_exists<double, float, char, int, string> assert_test2;

//these fail
X::assert_exists<char, char, char, char, char, char> assert_test3;
X::assert_exists<int, bool> assert_test4;

//true
auto test1 = X::exists<int, int, int, int, int>::value;
auto test2 = X::exists<double, float, char, int, string>::value;

//false
auto test3 = X::exists<char, char, char, char, char, char>::value;
auto test4 = X::exists<int, bool>::value;

Второе решение

template<class T, class U> struct type_pair { typedef type_pair<T, U> type; };
template<class... Ts> struct type_list {};
template<class...> struct xprod_tlist_ {};

template<class T, class... Ts, class... Us>
struct xprod_tlist_<type_list<T, Ts...>, type_list<Us...>>
: type_pair<T, Us>..., xprod_tlist_<type_list<Ts...>, type_list<Us...>> {};

template<class... Ts>
struct xprod_tlist : xprod_tlist_<type_list<Ts...>, type_list<Ts...>> {
    template<class T, class U> struct exists
    : std::is_base_of<type_pair<T, U>, xprod_tlist<Ts...>> {};

    template<class T, class U> struct assert_exists {
        static_assert(exists<T, U>::value, "Type not present in list");
    };
};

Использование:

typedef xprod_tlist<int, float, string> X;

//these pass
X::assert_exists<int, int> assert_test1;
X::assert_exists<int, float> assert_test2;
X::assert_exists<int, string> assert_test3;
X::assert_exists<float, int> assert_test4;
X::assert_exists<float, float> assert_test5;
X::assert_exists<float, string> assert_test6;
X::assert_exists<string, int> assert_test7;
X::assert_exists<string, float> assert_test8;
X::assert_exists<string, string> assert_test9;

//this fails
X::assert_exists<int, char> assert_test10;

//true
auto test1 = X::exists<int, int>::value;
auto test2 = X::exists<int, float>::value;
auto test3 = X::exists<int, string>::value;
auto test4 = X::exists<float, int>::value;
auto test5 = X::exists<float, float>::value;
auto test6 = X::exists<float, string>::value;
auto test7 = X::exists<string, int>::value;
auto test8 = X::exists<string, float>::value;
auto test9 = X::exists<string, string>::value;

//false
auto test10 = X::exists<int, char>::value;