Create a type list combination of types in C++

Question

Im trying to create some tool to create a list of types based on combinations of other types.

Lets say we have three types

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

I want to get a list of tuples which has every possible combination of N types A,B or C.

For a N=2 case, this would be

std::tuple<A,A>
std::tuple<A,B>
std::tuple<A,C>
std::tuple<B,A>
std::tuple<B,B>
std::tuple<B,C>
std::tuple<C,A>
std::tuple<C,B>
std::tuple<C,C>

The idea is to create a tuple which holds a container for all those types, so I can later store any of those types inside the container list.

template <typename ...Combinations>
using CombinationList = std::tuple<std::vector<Combinations>...>;

I already have a mechanism to inserting a particupar element inside the container in which it fits, but I have no clue on how to create the combinatios.

On the comments people has suggestes using std::vector<Combination<std::variant<A,C,B>, std::variant<A,B,C>>>. Althought this technically solve the problem, I prefer not to use it, as A, B C and has very different sizes and I dont want to visit the variants at runtime. Also, at some point I will need to upload the all the data in the containers in

std::tuple<std::vector<Combination>...>

to the GPU, so I cant use std::variant here.

How could I do this?

Thanks!

PD: This is related to this question Combination explosion of an enum value (729 combinations...) In that question I asked how I could generate easily the types that would go inside the container. Now I need to generate the containers .

Baronetcy

A std::variant (en.cppreference.com/w/cpp/utility/variant) would be a lot less work. – Demean

How would you do it? Im not sure how to implemented using a variant... – Baronetcy

How about using something like std::vector<std::tuple<std::variant<A, B, C>, std::variant<A, B, C>>>? – Grommet

A, B and C can have very different sizes. This is for a physics simulator, during bootstrap I dont care about performance, but during simulation I care (a lot) about it. That why I prefer not to use a variant like that. Also, at some point I will to upload all the data to GPU – Baronetcy

@Baronetcy I am more less sure it is possible because generating combinations can be done statelessly. Writing it would be tough yet possible chore – Pejsach

You cannot create a vector that holds objects of different types. There is no such thing in C++. Your options are (1) vector of variants or (2) vector to (smart) pointers to some (abstract) base class, whereas derived classes are responsible for concrete types. – Tyra

@jjcasmar: "This is for a physics simulator" That sounds very much like you're trying to take an OOP approach to multi-object collision. Giving each object a different type, and then having functions for each of the cross product of the possible interacting types.That's the wrong approach to take, and it will only end in tears. – Feretory

Do you require the container to contain more than one tuple at a time? What's wrong with having a struct that contains an A, a B, and a C and just ignoring one of them, using whatever mechanism you use to select the tuple member you want? – Demean

Is not for a collision system. Is for the computation of forces. Giving an Element which contains nodes which can be A, B or C, I need the 3d position of the nodes to compute the forces of the element. I dont want to pay the check to decide which kind of node I have in the element while computing the forces. I can preproces it. I will have millions of elements, that's why I want to avoid as much computations as possible in the hot path – Baronetcy

Answer 1

I already have a mechanism to inserting a particupar element inside the container in which it fits, but I have no clue on how to create the combinatios.

Suppose you have a list of types (say A, B, C) and an unsigned integer N, I propose a using

template <std::size_t N, typename ... Ts>
using Combinations = ???

that is defined as a std::tuple containing a list of std::tuples with all combinations.

So, by example,

Combinations<2u, A, B, C>

become

  std::tuple<
      std::tuple<A,A>, std::tuple<A,B>, std::tuple<A,C>,
      std::tuple<B,A>, std::tuple<B,B>, std::tuple<B,C>,
      std::tuple<C,A>, std::tuple<C,B>, std::tuple<C,C>>

The following is a full compiling C++11 example

#include <tuple>
#include <vector>
#include <type_traits>

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

template <typename T, typename ... Ts>
constexpr std::tuple<T, Ts...> addTupleType (std::tuple<Ts...>);

template <typename T, typename ... Ts>
constexpr auto addType ()
   -> std::tuple<decltype(addTupleType<T>(std::declval<Ts>()))...>;

template <typename ... Ts, typename ... Us>
constexpr auto getCombinations (std::integral_constant<std::size_t, 0u>,
                                std::tuple<Ts...> t, std::tuple<Us ...> u)
   -> decltype( u );

template <std::size_t N, typename ... Ts, typename ... Us,
          typename std::enable_if<(N > 0u), bool>::type = true>
constexpr auto getCombinations (std::integral_constant<std::size_t, N>,
                                std::tuple<Ts...> t, std::tuple<Us ...>)
   -> decltype (getCombinations(
         std::integral_constant<std::size_t, N-1u>{}, t,
         std::tuple_cat(addType<Ts, Us...>()...)));

template <std::size_t N, typename ... Ts>
using Combinations
   = decltype(getCombinations(
         std::integral_constant<std::size_t, N-1u>{},
         std::declval<std::tuple<Ts...>>(),
         std::declval<std::tuple<std::tuple<Ts>...>>()));

template <typename ... Ts>
constexpr auto CombListHelper (std::tuple<Ts...>)
   -> std::tuple<std::vector<Ts>...>;

template <typename T>
using CombinationList = decltype(CombListHelper(std::declval<T>()));


int main()
 {
   using type_1 = Combinations<2u, A, B, C>;
   using type_2 = std::tuple<
      std::tuple<A,A>, std::tuple<A,B>, std::tuple<A,C>,
      std::tuple<B,A>, std::tuple<B,B>, std::tuple<B,C>,
      std::tuple<C,A>, std::tuple<C,B>, std::tuple<C,C>>;

   static_assert( std::is_same<type_1, type_2>::value, "!" );

   using type_3 = CombinationList<Combinations<2u, A, B, C>>;
   using type_4 = std::tuple<
      std::vector<std::tuple<A,A>>, std::vector<std::tuple<A,B>>,
      std::vector<std::tuple<A,C>>, std::vector<std::tuple<B,A>>,
      std::vector<std::tuple<B,B>>, std::vector<std::tuple<B,C>>,
      std::vector<std::tuple<C,A>>, std::vector<std::tuple<C,B>>,
      std::vector<std::tuple<C,C>>>;

   static_assert( std::is_same<type_3, type_4>::value, "!" );
 }

Sadick

Althought is doesn't completely solve my problem, I think I can take this as a starting point. Now i only need to generate a vector for each one of the possible combinations. Thanks a lot! – Baronetcy

@Baronetcy - not sure to understand what do you exactly want but... answer improved with a CombinationList (see type_3 and type_4 in main()) – Sadick

wow, impressive. This is exactly what I wanted. Thanks you very much! – Baronetcy

typename std::enable_if<(N > 0u), bool>::type = true seems unneeded. overload with std::integral_constant<std::size_t, 0u> would be better match. – Bunyan

And, as there are only declarations, constexpr is unneeded too. – Bunyan

You might start at getCombinations( std::integral_constant<std::size_t, N>{}, std::declval<std::tuple<Ts...>>(), std::declval<std::tuple<>>()) to handle Combinations<0, Ts...>. – Bunyan

@Bunyan - I was convinced too that the std::integral_constant<std::size_t, 0u> would a better match (and that the SFINAE part was unneeded) but clang++ (that select the other version and gives error reaching the recursion limit) and g++ (that goes in loop and force me to reboot my computer) disagree. And I don't understand why. – Sadick

@Bunyan - Not so simple about start getCombination(): a not empty list inside the second std::declval() is needed to expand Ts in addType(); with your solution, type_1 become std::tuple<>. But you're right: my solution has the defect that doesn't handle the N == 0 case. – Sadick

Oh, it seems due to return type determination... getCombinations hides the overload, using ::getCombinations solves that Demo. – Bunyan

Answer 2

Using the analogy with storing two dimensional matrix in linear storage, all possible pairs of A, B and C are labeled by one dimensional integers 0,1,...,8 like this:

0 -> (0/3, 0%3) = (0,0) -> std::tuple<A,A>
1 -> (1/3, 1%3) = (0,1) -> std::tuple<A,B>
...
8 -> (8/3, 8%3) = (2,2) -> std::tuple<C,C>

Thus we can construct the list of pairs as follows. These functions work in C++14 and over. For instance, Combinations<A,B,C>::types is equal to std::tuple<std::vector<std::tuple<A,A>>, std::vector<std::tuple<A,B>>, ...>:

Live DEMO

template<std::size_t I, typename Tuple>
struct make_pair_vector
{
    static constexpr std::size_t  left_index = I/std::tuple_size<Tuple>::value;
    static constexpr std::size_t right_index = I%std::tuple_size<Tuple>::value;

    using type = std::vector<
                    std::tuple<typename std::tuple_element< left_index, Tuple>::type,
                               typename std::tuple_element<right_index, Tuple>::type>>;
};

template <typename T, typename Is>
struct make_combinations;

template <typename Tuple, std::size_t... Is>
struct make_combinations<Tuple, std::index_sequence<Is...>>
{
    using tuples = std::tuple<typename make_pair_vector<Is, Tuple>::type...>;
};

template<typename ...Args>
struct Combinations
{
    using types = typename make_combinations
                    <std::tuple<Args...>,
                     std::make_index_sequence<(sizeof...(Args))*(sizeof...(Args))>>
                    ::tuples;
};

Spine

This is a nice try, but it only works for combinations of two elements (AA, AB, AC, AB), but doesnt work for three elements (AAA, ABB, AAB...) THanks you anyway, is a very nice code. – Baronetcy

division and modulo to select the types... intriguing idea. – Sadick

@Baronetcy (and max66), many thx. I hope you will go well. BTW, generalizing this approach to triples or more large dimensions may not be so difficult. – Spine

@Spine nice idea. May I edit your answer to the general case? Here is my proposal: wandbox.org/permlink/aAQ3ZJX73IfViZax . – Hecht

@Hecht Ah, nice code! But I want to keep current my answer because, simply, that is not my code :). Needless to say, you can post it as your own answer. Thank you anyway, nice work! – Spine