Перестановка P (N, R) типов во время компиляции
Я написал рабочий код для вычисления P (N, R) для пакетов, когда пакет имеет все различные типы, например
PermutationN<2, P<int, char, bool>>
должна быть
P< P<int, char>, P<int, bool>, P<char, int>, P<char, bool>, P<bool, int>, P<bool, char> >
Но когда есть повторяющиеся элементы, я получаю неправильные результаты. Например,
PermutationN<2, P<int, int, char>>
должно быть
P< P<int, int>, P<int, char>, P<char, int> >
Вот мой рабочий код, когда все типы разные. Я застрял на том, как адаптировать его так, чтобы он давал правильные результаты, когда в пакете есть повторяющиеся типы. Любая помощь будет оценена.
#include <iostream>
#include <type_traits>
template <typename, typename> struct Merge;
template <template <typename...> class P, typename... Ts, typename... Us>
struct Merge<P<Ts...>, P<Us...>> {
using type = P<Ts..., Us...>;
};
template <std::size_t N, typename Pack, typename Previous, typename... Output> struct PermutationNHelper;
template <std::size_t N, template <typename...> class P, typename First, typename... Rest, typename... Prev, typename... Output>
struct PermutationNHelper<N, P<First, Rest...>, P<Prev...>, Output...> : Merge<
// P<Prev..., Rest...> are the remaining elements, thus ensuring that the next
// element chosen will not be First. The new Prev... is empty since we now start
// at the first element of P<Prev..., Rest...>.
typename PermutationNHelper<N-1, P<Prev..., Rest...>, P<>, Output..., First>::type,
// Using P<Rest...> ensures that the next set of permutations will begin with the
// type after First, and thus the new Prev... is Prev..., First.
typename PermutationNHelper<N, P<Rest...>, P<Prev..., First>, Output...>::type
> {};
template <std::size_t N, template <typename...> class P, typename Previous, typename... Output>
struct PermutationNHelper<N, P<>, Previous, Output...> {
using type = P<>;
};
template <template <typename...> class P, typename First, typename... Rest, typename... Prev, typename... Output>
struct PermutationNHelper<0, P<First, Rest...>, P<Prev...>, Output...> {
using type = P<P<Output...>>;
};
template <template <typename...> class P, typename Previous, typename... Output>
struct PermutationNHelper<0, P<>, Previous, Output...> {
using type = P<P<Output...>>;
};
template <typename Pack> struct EmptyPack;
template <template <typename...> class P, typename... Ts>
struct EmptyPack<P<Ts...>> { using type = P<>; };
template <std::size_t N, typename Pack>
using PermutationN = typename PermutationNHelper<N, Pack, typename EmptyPack<Pack>::type>::type;
// Testing
template <typename...> struct P;
int main() {
std::cout << std::is_same<
PermutationN<2, P<int, char, bool>>,
P< P<int, char>, P<int, bool>, P<char, int>, P<char, bool>, P<bool, int>, P<bool, char> >
>::value << '\n'; // true
std::cout << std::is_same<
PermutationN<2, P<int, int, int>>,
P< P<int, int>, P<int, int>, P<int, int>, P<int, int>, P<int, int>, P<int, int> >
>::value << '\n'; // true (but the answer should be P< P<int, int> >.
}
Нотабене Я ищу элегантное (и эффективное) решение, которое не просто выполняет вышеуказанное, а затем просто удаляет все повторяющиеся пакеты из выходных данных (я уже могу это сделать, но отказываюсь писать такое уродливое, неэффективное решение, которое не решить суть проблемы), а точнее получить правильный вывод напрямую. Вот где я застрял.
Решение
Основная идея состоит в том, чтобы обработать начальный список типов в список (type, count) пары, и работать оттуда. Во-первых, некоторые примитивы:
template<class, size_t> struct counted_type {};
template<class...> struct pack {};
Наше представительство будет pack из counted_types. Чтобы построить его, нам нужно добавить в него тип:
template<class T, class CT> struct do_push;
template<class T, class...Ts, size_t... Is>
struct do_push<T, pack<counted_type<Ts, Is>...>>{
using type = std::conditional_t<std::disjunction_v<std::is_same<Ts, T>...>,
pack<counted_type<Ts, Is + (std::is_same_v<Ts, T>? 1 : 0)>...>,
pack<counted_type<Ts, Is>..., counted_type<T, 1>>
>;
};
template<class T, class CT> using push = typename do_push<T, CT>::type;
Если тип уже существует, мы добавляем 1 к счетчику; в противном случае мы добавляем counted_type<T, 1>,
И чтобы использовать его позже, нам нужно будет удалить из него тип:
template<class T, class CT> struct do_pop;
template<class T, class...Ts, std::size_t... Is>
struct do_pop<T, pack<counted_type<Ts, Is>...>>{
using type = remove<counted_type<T, 0>,
pack<counted_type<Ts, Is - (std::is_same_v<Ts, T>? 1 : 0)>...>>;
};
template<class T, class CT> using pop = typename do_pop<T, CT>::type;
remove<T, pack<Ts...>> удаляет первый экземпляр T от Ts..., если он существует, и возвращает полученный пакет (если T не существует, пакет возвращается без изменений). (Довольно скучная) реализация оставлена читателю в качестве упражнения.
С push мы можем легко построить pack из counted_typeс из pack типов:
template<class P, class CT = pack<> >
struct count_types_imp { using type = CT; };
template<class CT, class T, class... Ts>
struct count_types_imp<pack<T, Ts...>, CT>
: count_types_imp<pack<Ts...>, push<T, CT>> {};
template<class P>
using count_types = typename count_types_imp<P>::type;
Теперь фактическая реализация
template<class T> struct identity { using type = T; };
template <std::size_t N, typename CT, typename = pack<> > struct PermutationNHelper;
// Workaround for GCC's partial ordering failure
template <std::size_t N, class CT, class> struct PermutationNHelper1;
template <std::size_t N, class... Types, std::size_t... Counts, class... Current >
struct PermutationNHelper1<N, pack<counted_type<Types, Counts>...>, pack<Current...>> {
// The next item can be anything in Types...
// We append it to Current... and pop it from the list of types, then
// recursively generate the remaining items
// Do this for every type in Types..., and concatenate the result.
using type = concat<
typename PermutationNHelper<N-1, pop<Types, pack<counted_type<Types, Counts>...>>,
pack<Current..., Types>>::type...
>;
};template <std::size_t N, class... Types, std::size_t... Counts, class... Current >
struct PermutationNHelper<N, pack<counted_type<Types, Counts>...>, pack<Current...>> {
using type = typename std::conditional_t<
N == 0,
identity<pack<pack<Current...>>>,
PermutationNHelper1<N, pack<counted_type<Types, Counts>...>,
pack<Current...>>
>::type;
// Note that we don't attempt to evaluate PermutationNHelper1<...>::type
// until we are sure that N > 0
};template <std::size_t N, typename Pack>
using PermutationN = typename PermutationNHelper<N, count_types<Pack>>::type;
Обычно это может быть сделано в одном шаблоне с двумя частичными специализациями (одна для N> 0 и одна для N == 0), но частичное упорядочение GCC является ошибочным, поэтому я отправил явно с conditional, Фактически оценивая расширение пакета в PermutationNHelper1 с N равный 0 взорвется ужасно, так что имя PermutationNHelper1 вводится для обеспечения дополнительного уровня косвенности и предотвращения взрыва.
concat это всего лишь вариационная версия вашего Merge (Что ж, typename Merge<...>::type). Реализация оставлена в качестве упражнения для читателя.
Другие решения
Других решений пока нет …
detector