Generate<P<3>, P<5,0>, P<4,0,0>, P<3,0,1>>::type
是
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>
表示存在n = 0,1,2的P<n>
; P<5,0>
表示存在A<0,n>
且n = 0、1、2、3、4; P<4,0,0>
表示存在n = 0,1,2,3的A<0,0,n>
; P<3,0,1>
表示存在A<0,1,n>
且n = 0,1,2。在排序方面,如果x A<n1,n2,n3,...,nk,x,...>将始终在
A<n1,n2,n3,...,nk,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中只剩下2个装的情况。谁能帮我继续吗?
想法:对于2个包,只需分别生成,合并两个
Pack
,然后排序?但是,排序将是我认为最困难的部分。 最佳答案
诀窍在于,您已经从每个“生成”过程中获得的序列已经过排序,并且问题减少到合并多个排序后的列表。
为简单起见,我将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>()));
两个
A
的词典比较: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 {};
合并两个
A
的排序包: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...>;
};
合并
A
的许多排序包: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;
};
Demo。