I'd like to create the cross product of a list of types using variadic templates.
Here's what I have so far:
#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 cross_product
{
typedef type_list<typename row<T,T...>::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;
}
This program outputs:
$ g++ -std=c++0x cross_product.cpp ; ./a.out
type_list<type_list<type_pair<int, int>, type_pair<int, float>, type_pair<int, short> >, type_list<type_pair<float, int>, type_pair<float, float>, type_pair<float, short> >, type_list<type_pair<short, int>, type_pair<short, float>, type_pair<short, short> > >
But I'd like it to output:
type_list<type_pair<int,int>, type_pair<int,float>, type_pair<int,short>, type_pair<float,int>,...>
That is, without the nested type_list
s.
Is there a direct way to do this without the row
helper, or should the solution "unwrap" the nested type_list
s somehow?
Get Cartesian Product in Python Using the itertools ModuleThe product(*iterables, repeat=1) method of the itertools module takes iterables as input and returns their cartesian product as output. The cartesian product order will be the order of each set/list in the provided argument iterables .
The cartesian product (or cross product) of A and B, denoted by A x B, is the set A x B = {(a,b) | a ∈ A and b ∈ B}. The elements (a,b) are ordered pairs. For example if A = {1,2} and B = {4,5,6} then the cartesian products of A and B is AxB = {(1,4),(1,5),(1,6),(2,4),(2,5),(2,6)}.
The Cartesian product of two sets is. A x B = {a, d}, {a, e}, {a, f}, {b, d}, {b, e}, {b, f}, {c, d}, {c, e}, {c, f}} A has 3 elements and B also has 3 elements. The Cartesian Product has 3 x 3 = 9 elements.
It's just the same symbol, and definitely not the same thing: the Cartesian product is a set (of vectors), the cross product is a vector.
A nice clean version I think:
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
detail/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
Output:
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)}
(I noticed on Windows using Chrome that the cross product unicode character is not coming out well. Sorry, I don't know how to fix that.)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With