Создайте список типов комбинаций типов в C ++ - PullRequest
11 голосов
/ 05 марта 2019

Я пытаюсь создать какой-то инструмент для создания списка типов на основе комбинаций других типов.

Допустим, у нас есть три типа

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

Я хочу получить список кортежей, который имеет каждую возможную комбинацию из N типов A, B или C.

Дляв случае N = 2 это будет

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>

Идея состоит в том, чтобы создать кортеж, содержащий контейнер для всех этих типов, чтобы впоследствии я мог сохранить любой из этих типов в списке контейнеров.

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

У меня уже есть механизм для вставки конкретного элемента внутрь контейнера, в который он помещается, но я понятия не имею, как создать комбинации.

В комментариях людей предлагается использовать std::vector<Combination<std::variant<A,C,B>, std::variant<A,B,C>>>.Хотя это технически решает проблему, я предпочитаю не использовать его, как A, BC и имеет очень разные размеры, и я не хочу посещать варианты во время выполнения.Кроме того, в какой-то момент мне нужно будет загрузить все данные из контейнеров в

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

в графический процессор, поэтому я не могу использовать std :: variable здесь.

Как я могу это сделать?

Спасибо!

PD: Это связано с этим вопросом Комбинированный взрыв значения перечисления (729 комбинаций ...) В этом вопросе я спросил, как я могу легко генерировать типы, которые будут идти внутри контейнера.Теперь мне нужно сгенерировать контейнеры.

Ответы [ 2 ]

5 голосов
/ 05 марта 2019

У меня уже есть механизм для вставки конкретного элемента внутрь контейнера, в который он помещается, но я понятия не имею, как создавать комбинации.

Предположим, у вас есть список типов (скажем, A, B, C) и целое число без знака N. Я предлагаю using

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

, который определяется какstd::tuple, содержащий список std::tuple s со всеми комбинациями.

Так, например,

Combinations<2u, A, B, C>

становится

  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>>

Следующее является полнымпример компиляции C ++ 11

#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, "!" );
 }
5 голосов
/ 05 марта 2019

Используя аналогию с хранением двумерной матрицы в линейном хранилище, все возможные пары A, B и C помечены одномерными целыми числами 0,1,...,8 следующим образом:

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>

Таким образом, мы можем построить список пар следующим образом. Эти функции работают в C ++ 14 и более. Например, Combinations<A,B,C>::types равно 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;
};
...