Создание пакета шаблонов

Generate<P<3>, P<5,0>, P<4,0,0>, P<3,0,1>>::type is to be

Pack< A<0>, A<0,0>, A<0,0,0>, A<0,0,1>, A<0,0,2>, A<0,0,3>, A<0,1>, A<0,1,0>, A<0,1,1>, A<0,1,2>, A<0,2>, A<0,3>, A<0,4>, A<1>, A<2> >

потому что P<3> означает, что P<n> существует для n = 0,1,2; P<5,0> означает, что A<0,n> существует для n = 0,1,2,3,4; P<4,0,0> означает, что A<0,0,n> существует для n = 0,1,2,3; и P<3,0,1> означает, что A<0,1,n> существует для n = 0,1,2. Что касается порядка, A<n1,n2,n3,...,nk,x,...> всегда будет предшествовать A<n1,n2,n3,...,nk,y,...>, если x ‹y и A<n1,n2,n3,...,nk> всегда будут предшествовать A<n1,n2,n3,...,nk, ...>, где второе число ... не пусто. Поэтому мне нужно написать реализацию Generate<Packs...>.

Мотивация для этого: если template <int... Is> class Object имеет определенные возможности для своего Is... пакета, определенные константами, такими как 3, 5, 4 и 3 выше, тогда пакет всех его возможных типов позволит генерировать определенные Object<Is...> экземпляры путем итерации по пакету .

Вот что у меня есть на данный момент:

#include <iostream>
#include <type_traits>

template <int...> class A;
template <typename...> struct Pack;
template <int...> struct P;

template <int N, int Count, typename Front, typename Output> struct GenerateHelper;

template <int N, int Count, int... Is, typename... As>
struct GenerateHelper<N, Count, P<Is...>, Pack<As...>> :
    GenerateHelper<N, Count + 1, P<Is...>, Pack<As..., A<Is..., Count>>> {};

template <int N, int... Is, typename... As>
struct GenerateHelper<N, N, P<Is...>, Pack<As...>> {
    using type = Pack<As...>;
};

template <typename...> struct Generate;

// Simple special case just to start off.  Generate has only one pack to deal with.
template <int N, int... Is>
struct Generate<P<N, Is...>> : GenerateHelper<N, 0, P<Is...>, Pack<>> {};

int main() {
    using T = Generate<P<3,0,0>>::type;
    std::cout << std::is_same<T, Pack<A<0,0,0>, A<0,0,1>, A<0,0,2>>>::value << '\n'; // true
}

Но теперь я застрял в случае с двумя пакетами в Generate. Может ли кто-нибудь помочь мне продолжить?

Идея: для двух пакетов просто сгенерируйте отдельно, объедините два Pack, а затем выполните сортировку? Но я думаю, что тогда сортировка будет самой сложной частью.


c++ templates c++11 variadic
person prestokeys    schedule 05.09.2015    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Хитрость заключается в том, чтобы понять, что последовательность, которую вы получаете от каждой процедуры «генерации», уже отсортирована, и проблема сводится к объединению нескольких отсортированных списков.

Для простоты я сделал A, Pack и P пустые структуры.

template <int...> class A {};
template <typename...> struct Pack {};
template <int...> struct P {};

Сгенерируйте пачку A из одного P:

template<int I, int... Tail>
auto do_sequence_for(P<I, Tail...>) -> std::make_integer_sequence<int, I>;

template<class PP>
using sequence_for = decltype(do_sequence_for(PP()));

template<int I, int... Front, int... Tail>
auto do_generate_single(P<I, Front...>, std::integer_sequence<int, Tail...>)
     -> Pack<A<Front..., Tail>...>;

template<class PP>
using generate_single = decltype(do_generate_single(PP(), sequence_for<PP>()));

Лексикографическое сравнение двух As:

template<class A1, class A2>
struct compare; // returns A1 < A2

template<int I, int J, int...Is, int...Js>
struct compare<A<I, Is...>, A<J, Js...>> : std::integral_constant<bool, I < J> {};

template<int I, int...Is, int...Js>
struct compare<A<I, Is...>, A<I, Js...>> : compare<A<Is...>, A<Js...>> {};

template<int...Is>
struct compare<A<Is...>, A<>> : std::false_type {};

template<int J, int...Js>
struct compare<A<>, A<J, Js...>> : std::true_type {};

Объединение двух отсортированных пакетов As:

template<class Pack1, class Pack2, class Result=Pack<>>
struct merge2;

template<class A1, class...A1s, class A2, class...A2s, class...R>
struct merge2<Pack<A1, A1s...>, Pack<A2, A2s...>, Pack<R...>>
    : std::conditional_t<compare<A1, A2>::value,
                         merge2<Pack<A1s...>, Pack<A2, A2s...>, Pack<R..., A1>>,
                         merge2<Pack<A1, A1s...>, Pack<A2s...>, Pack<R..., A2>>>
{};

template<class...A1s, class...R>
struct merge2<Pack<A1s...>, Pack<>, Pack<R...>>
{
    using type = Pack<R..., A1s...>;
};

template<class A2, class...A2s, class...R>
struct merge2<Pack<>, Pack<A2, A2s...>, Pack<R...>>
{
    using type = Pack<R..., A2, A2s...>;
};

Объедините множество отсортированных пакетов As:

template<class... Packs>
struct merge;

template<class P1>
struct merge<P1> {
    using type = P1;
};

template<class P1, class P2, class... Ps>
struct merge<P1, P2, Ps...> : merge<typename merge2<P1, P2>::type, Ps...> {};

Собираем все вместе:

template<class...Ps>
struct Generate{
    using type = typename merge<generate_single<Ps>...>::type;
};

Демо.

person T.C.    schedule 05.09.2015

arrow_upward
0
arrow_downward

К сожалению, Visual Studio 2015 не скомпилирует отличное решение TC (из-за некоторой ошибки), поэтому я адаптировал следующее, которое компилируется как в Visual Studio 2015, так и в GCC 5.1.0 (а также обобщается для любого интегрального типа, любой класс и т.д ...). Требовалось заменить только его generate_single функцию.

#include <iostream>
#include <utility>
#include <type_traits>

// Another way to generate a pack of A's from one P than the above.
template <typename T, template<T...> class Class, T N, T Count, typename Front, typename Output> struct GenerateSingleHelper;

template <typename T, template<T...> class Class, T N, T Count, template <T...> class Z, T... Is, template <typename...> class PackOfPacks, typename... As>
struct GenerateSingleHelper<T, Class, N, Count, Z<Is...>, PackOfPacks<As...>> : GenerateSingleHelper<T, Class, N, Count + 1, Z<Is...>, PackOfPacks<As..., Class<Is..., Count>>> {};

template <typename T, template<T...> class Class, T N, template <T...> class Z, T... Is, template <typename...> class PackOfPacks, typename... As>
struct GenerateSingleHelper<T, Class, N, N, Z<Is...>, PackOfPacks<As...>> {
    using type = PackOfPacks<As...>;
};

template <typename T, template<T...> class Class, template <typename...> class PackOfPacks, typename> struct GenerateSingle;

template <typename T, template<T...> class Class, template <typename...> class PackOfPacks, template <T...> class Z, T N, T... Is>
struct GenerateSingle<T, Class, PackOfPacks, Z<N, Is...>> : GenerateSingleHelper<T, Class, N, 0, Z<Is...>, PackOfPacks<>> {};

// Lexicographical comparison of two A's.
template <typename T, typename A1, typename A2> struct Compare;  // Determines if A1 < A2.

template <typename T, template <T...> class Pack, T I, T J, T... Is, T... Js>
struct Compare<T, Pack<I, Is...>, Pack<J, Js...>> : std::integral_constant<bool, I < J> {};

template <typename T, template <T...> class Pack, T I, T... Is, T... Js>
struct Compare<T, Pack<I, Is...>, Pack<I, Js...>> : Compare<T, Pack<Is...>, Pack<Js...>> {};

template <typename T, template <T...> class Pack, T... Is>
struct Compare<T, Pack<Is...>, Pack<>> : std::false_type {};

template <typename T, template <T...> class Pack, T J, T... Js>
struct Compare<T, Pack<>, Pack<J, Js...>> : std::true_type {};  // J is needed to indicate that Pack<J, Js...> is not empty.

// Merging two sorted packs of A's.
template <typename T, template <typename...> class PackOfPacks, typename PackOfPacks1, typename PackOfPacks2, typename Result = PackOfPacks<>> struct MergeTwoPacks;

template <typename T, template <typename...> class PackOfPacks, typename A1, typename... A1s, typename A2, typename... A2s, typename... Accumulated>
struct MergeTwoPacks<T, PackOfPacks, PackOfPacks<A1, A1s...>, PackOfPacks<A2, A2s...>, PackOfPacks<Accumulated...>> : std::conditional_t<Compare<T, A1, A2>::value,
    MergeTwoPacks<T, PackOfPacks, PackOfPacks<A1s...>, PackOfPacks<A2, A2s...>, PackOfPacks<Accumulated..., A1>>,
    MergeTwoPacks<T, PackOfPacks, PackOfPacks<A1, A1s...>, PackOfPacks<A2s...>, PackOfPacks<Accumulated..., A2>>> {};

template <typename T, template <typename...> class PackOfPacks, typename... A1s, typename... Accumulated>
struct MergeTwoPacks<T, PackOfPacks, PackOfPacks<A1s...>, PackOfPacks<>, PackOfPacks<Accumulated...>> {
    using type = PackOfPacks<Accumulated..., A1s...>;  // Since PackOfPacks<A1s...> is already sorted.
};

template <typename T, template <typename...> class PackOfPacks, typename A2, typename... A2s, typename... Accumulated>
struct MergeTwoPacks<T, PackOfPacks, PackOfPacks<>, PackOfPacks<A2, A2s...>, PackOfPacks<Accumulated...>> {  // A2 is needed to indicate that PackOfPacks<A2, A2s...> is not empty.
    using type = PackOfPacks<Accumulated..., A2, A2s...>;  // Since PackOfPacks<A2s...> is already sorted.
};

// Merging any number of sorted packs of A's.
template <typename T, template <typename...> class PackOfPacks, typename... Packs> struct Merge;

template<typename T, template <typename...> class PackOfPacks, typename First, typename Second, typename... Rest>
struct Merge<T, PackOfPacks, First, Second, Rest...> : Merge<T, PackOfPacks, typename MergeTwoPacks<T, PackOfPacks, First, Second>::type, Rest...> {};

template <typename T, template <typename...> class PackOfPacks, typename Last>
struct Merge<T, PackOfPacks, Last> {
    using type = Last;
};

// Putting it all together.
template <typename T, template <T...> class Class, template <typename...> class PackOfPacks, typename... Packs>
struct Generate : Merge<T, PackOfPacks, typename GenerateSingle<T, Class, PackOfPacks, Packs>::type...> {};

// Testing.
template <int...> class A {};
template <typename...> struct PackOfPacks;
template <int...> struct P;

int main() {
    std::cout << std::boolalpha << std::is_same<
        Generate<int, A, PackOfPacks, P<3>, P<5,0>, P<4,0,0>, P<3,0,1>>::type,
        PackOfPacks< A<0>, A<0,0>, A<0,0,0>, A<0,0,1>, A<0,0,2>, A<0,0,3>, A<0,1>, A<0,1,0>, A<0,1,1>, A<0,1,2>, A<0,2>, A<0,3>, A<0,4>, A<1>, A<2> >
    >::value << '\n';  // true
}
person prestokeys    schedule 05.09.2015