c++ - 查找要合并的一组包以等于给定的包

Question

typename FindPacksToMerge<P<Packs...>, P<Ts...>>::type是P<As...>这样 As...是来自 Packs... 的一系列包(可能有重复)和

std::is_same< typename concat<As...>::type, P<Ts...> >::value == true

例如，

std::cout << std::is_same<
    FindPacksToMerge< P< P<int, char, long>, P<int>, P<double, bool>, P<bool, char, int> >, P<int, bool, char, int, int, double, bool> >::type,
    P< P<int>, P<bool, char, int>, P<int>, P<double, bool> >
>::value << '\n';

应该输出 true。现在让我们满足于得到任何答案，以防有多个答案。

我已经编写了相关的辅助结构(concat 合并任意数量的包，split<N, Pack> 拆分一个包以便获得具有 N 种类型的头部和尾部，pack_size 给出类型的数量在包中):

template <typename T> struct Identity { using type = T; };

template <typename...> struct concat;

template <template <typename...> class P, typename... Ts, typename... Us>
struct concat<P<Ts...>, P<Us...>> {
    using type = P<Ts..., Us...>;
};

template <typename Pack>
struct concat<Pack> : Identity<Pack> {};

template <typename Pack1, typename Pack2, typename... Packs>
struct concat<Pack1, Pack2, Packs...> {
    using type = typename concat<Pack1, typename concat<Pack2, Packs...>::type>::type;
};

template <std::size_t N, typename Intput, typename... Output> struct split;

template <std::size_t N, template <typename...> class P, typename First, typename... Rest, typename... Output>
struct split<N, P<First, Rest...>, Output...> : split<N-1, P<Rest...>, Output..., First> {};

template <template <typename...> class P, typename First, typename... Rest, typename... Output>
struct split<0, P<First, Rest...>, Output...> {
    using head = P<Output...>;
    using tail = P<First, Rest...>;
};

template <template <typename...> class P, typename... Output>
struct split<0, P<>, Output...> {
    using head = P<Output...>;
    using tail = P<>;
};

template <typename Pack> struct pack_size;

template <template <typename...> class P, typename... Ts>
struct pack_size<P<Ts...>> : std::integral_constant<std::size_t, sizeof...(Ts)> {};

但问题是递归。假设在 P<Packs...> 中的类型中，我们正在测试类型 Pack .如果split<pack_size<Pack>::value, P<Ts...>>::head火柴Pack , 然后用 split<pack_size<Pack>::value, P<Ts...>>::tail 重复搜索(从 P<Packs...> 中的第一个包开始搜索)。我们一路将所有找到的包存储在一个输出包中。当我们接近 P<Ts...> 的末尾时并发现剩余的尾部比P<Packs...>中最短的尾部更短或相等, 并且不匹配 P<Packs...> 中的任何包, 那么沿着这条线的搜索就失败了。因此，我们必须重新开始搜索。但从哪里来？从最后一次尝试的包开始(我们现在必须尝试之后的包)。而如果之后的所有狼群也都没有给出答案，那我们就得再退一步，可是那又在哪里呢？这是一个树遍历，但如何记住我们在任何几代人之后都停止了？或者也许有更好的方法？尝试合并来自 P<Packs...> 的所有可能组合直到匹配 P<Ts...>不可能是一个可行的解决方案。

这是我目前正在处理的模板特化，需要修复。我感觉我无法解决的问题很短。

template <typename PackOfPacks, typename Untried, typename Output, typename Match> struct FindPacksToMergeHelper;

template <typename PackOfPacks, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct FindPacksToMergeHelper<PackOfPacks, P<First, Rest...>, P<Output...>, Match> : std::conditional_t<
    pack_size<Match>::value < pack_size<First>::value,
    FindPacksToMergeHelper<PackOfPacks, P<Rest...>, P<Output...>, Match>,  // Move on to the next of the untried packs.
    std::conditional_t<
        std::is_same<First, Match>::value,
        Identity<P<Output..., First>>,  // Answer found.
        std::conditional_t<
            std::is_same<First, typename split<pack_size<First>::value, Match>::head>::value,  // Check if the head of Match is the same as First.
            FindPacksToMergeHelper<PackOfPacks, PackOfPacks, P<Output..., First>, typename split<pack_size<First>::value, Match>::tail>,  // Try with the tail now, starting back at the first type in PackOfPacks.
            FindPacksToMergeHelper<PackOfPacks, P<Rest...>, P<Output...>, Match>  // Move on to the next of the untried packs.
        >
    >
> {};

Answer 1

一包:

template<class... > class pack {};

通过谓词过滤一组类型:

template<class, class Pred> struct filter;

template<class... Ts, class F>
struct filter<pack<Ts...>, F>
{
    using type = typename concat<std::conditional_t<F::template apply<Ts>::value,
                                                    pack<Ts>,
                                                    pack<>>...>::type;
};

“U 是 T 的前缀”的谓词:

template<class T>
struct is_prefix_of
{
    template<class U, bool = pack_size<T>::value >= pack_size<U>::value>
    struct apply;
    template<class U>
    struct apply<U, true> 
        : std::is_same<U, typename split<pack_size<U>::value, T>::head> { };
    template<class U>
    struct apply<U, false> : std::false_type {};
};

用于指示失败的标记类型:

struct fail;

野兽:

template<class Packs, class Pack,
         class Current = typename filter<Packs, is_prefix_of<Pack>>::type> 
struct find_packs_to_merge;

template<class Packs, class Pack, class First, class... Rest>
struct find_packs_to_merge<Packs, Pack, pack<First, Rest...>>
{
    // Get the remainder of the pack we still need to work on
    using Remaining = typename split<pack_size<First>::value, Pack>::tail;
    // search for the packs needed for the tail
    using PR = typename find_packs_to_merge<Packs, Remaining>::type;

    // on failure, try the next pack 
    // on success, concat First to PR and we are done.
    // Note the short circuiting.
    using type = typename std::conditional_t<std::is_same<fail, PR>::value, 
                                    find_packs_to_merge<Packs, Pack, pack<Rest...>>,
                                    concat<pack<First>, PR>>::type;
};

template<class Packs, class Pack>
struct find_packs_to_merge<Packs, Pack, pack<>>
{
    // we tried everything and nothing works.
    using type = fail;
};

template<class Packs>
struct find_packs_to_merge<Packs, pack<>, pack<>>
{
   // Success - we've used up the pack.
    using type = pack<>;
};