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

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

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

我已经写好了相关的helper structs（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;
};

"is U a prefix of 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<>;
};

Answer 2

我还没有阅读 T.C. 的解决方案，因为我坚持我的方法。以下代码通过了 6 个测试用例，但我不知道它是否适用于任何可能的情况。

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

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)> {};

struct Failed;

template <typename PackOfPacks, typename Untried, typename Output, typename Match> struct FindPacksToMergeImpl;
template <typename PackOfPacks, typename Untried, typename Output, typename Match, typename Result> struct Check;
template <typename PackOfPacks, typename Untried, typename Output, typename Match> struct FindPacksToMergeHelper;
template <typename PackOfPacks, typename Untried, typename Output, typename Match, bool> struct CheckIfPackTooBig;
template <typename PackOfPacks, typename Untried, typename Output, typename Match, bool> struct CheckIfAnswerFound;
template <typename PackOfPacks, typename Untried, typename Output, typename Match, bool> struct CheckHead;

template <typename PackOfPacks, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct CheckIfPackTooBig<PackOfPacks, P<First, Rest...>, P<Output...>, Match, true> :
    FindPacksToMergeImpl<PackOfPacks, P<Rest...>, P<Output...>, Match> {};  // Move on to the next of the untried packs.

template <typename PackOfPacks, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct CheckIfPackTooBig<PackOfPacks, P<First, Rest...>, P<Output...>, Match, false> :
    CheckIfAnswerFound<PackOfPacks, P<First, Rest...>, P<Output...>, Match, std::is_same<First, Match>::value> {};

template <typename PackOfPacks, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct CheckIfAnswerFound<PackOfPacks, P<First, Rest...>, P<Output...>, Match, true> : Identity<P<Output..., First>> {};  // We are done.

template <typename PackOfPacks, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct CheckIfAnswerFound<PackOfPacks, P<First, Rest...>, P<Output...>, Match, false> :
    CheckHead<PackOfPacks, P<First, Rest...>, P<Output...>, Match, std::is_same<First, typename split<pack_size<First>::value, Match>::head>::value> {};  // Check if the head of Match is the same as First.

template <typename PackOfPacks, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct CheckHead<PackOfPacks, P<First, Rest...>, P<Output...>, Match, true> :
    FindPacksToMergeImpl<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.

template <typename PackOfPacks, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct CheckHead<PackOfPacks, P<First, Rest...>, P<Output...>, Match, false> :
    FindPacksToMergeImpl<PackOfPacks, P<Rest...>, P<Output...>, Match> {};  // Move on to the next of the untried packs.

template <typename PackOfPacks, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct FindPacksToMergeHelper<PackOfPacks, P<First, Rest...>, P<Output...>, Match> :
    CheckIfPackTooBig<PackOfPacks, P<First, Rest...>, P<Output...>, Match, pack_size<Match>::value < pack_size<First>::value> {};

template <typename PackOfPacks, template <typename...> class P, typename... Output, typename Match>
struct FindPacksToMergeHelper<PackOfPacks, P<>, P<Output...>, Match> : Identity<Failed> {};

template <typename PackOfPacks, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match, typename Result>
struct Check<PackOfPacks, P<First, Rest...>, P<Output...>, Match, Result> : Identity<Result> {};  // We are done.

template <typename PackOfPacks, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct Check<PackOfPacks, P<First, Rest...>, P<Output...>, Match, Failed> :
    FindPacksToMergeImpl<PackOfPacks, P<Rest...>, P<Output...>, Match> {};  // Move on to the next of the untried packs.

template <typename PackOfPacks, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct FindPacksToMergeImpl<PackOfPacks, P<First, Rest...>, P<Output...>, Match> :
    Check<PackOfPacks, P<First, Rest...>, P<Output...>, Match, typename FindPacksToMergeHelper<PackOfPacks, P<First, Rest...>, P<Output...>, Match>::type> {};

template <typename PackOfPacks, template <typename...> class P, typename... Output, typename Match>
struct FindPacksToMergeImpl<PackOfPacks, P<>, P<Output...>, Match> : Identity<Failed> {};  // This should never be reached, but is needed to compile (it was really hard to check why though).

template <typename> struct EmptyPack;

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

template <typename PackOfPacks, typename Match>
using FindPacksToMerge = typename FindPacksToMergeImpl<PackOfPacks, PackOfPacks, typename EmptyPack<PackOfPacks>::type, Match>::type;

// Testing
template <typename...> struct P;

int main() {
    std::cout << std::boolalpha << std::is_same<
        FindPacksToMerge< P<P<int, char, long>, P<int>, P<double, bool>, P<bool, char, int>>, P<bool, char, int> >,
        P< P<bool, char, int> >
    >::value << '\n';  // true

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

    std::cout << std::is_same<
        FindPacksToMerge< P<P<int, char, long>, P<int>, P<double, bool>, P<bool, char, int>>, P<bool, char, int, double, bool> >,
        P< P<bool, char, int>, P<double, bool> >
    >::value << '\n';  // 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> >,
        P< P<int>, P<bool, char, int>, P<int>, P<double, bool> >
    >::value << '\n';  // true

    std::cout << std::is_same<
        FindPacksToMerge< P< P<int, bool>, P<int, char, long>, P<int>, P<double, bool>, P<bool, char, int> >, P<int, bool, char, int, int, double, bool> >,
        P< P<int>, P<bool, char, int>, P<int>, P<double, bool> >
    >::value << '\n';  // true (this works even though P<int, bool> is tried (and fails) before P<int> is tried)

    std::cout << std::is_same<
        FindPacksToMerge< P< P<int, bool>, P<int, char, long>, P<bool>, P<int>, P<double, bool>, P<bool, char, int> >, P<int, bool, char, int, int, double, bool> >,
        P< P<int>, P<bool, char, int>, P<int>, P<double, bool> >
    >::value << '\n';  // true (this works even though after P<int> is correctly tried (after P<int, bool> is tried and failed), then P<bool> is tried (and fails) before P<bool, char, int> is tried)
}

我现在将研究 T.C. 的想法。

对于那些想知道的人，这是 FindTypesToMerge 的一个应用程序，它激发了这一点：

#include <iostream>
#include <tuple>
#include <vector>
#include <type_traits>
#include <utility>

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)> {};

struct Failed;

template <typename Pack, typename Untried, typename Output, typename Match> struct FindPacksToMergeImpl;
template <typename Pack, typename Untried, typename Output, typename Match, typename Result> struct Check;
template <typename Pack, typename Untried, typename Output, typename Match> struct FindPacksToMergeHelper;
template <typename Pack, typename Untried, typename Output, typename Match, bool> struct CheckIfPackTooBig;
template <typename Pack, typename Untried, typename Output, typename Match, bool> struct CheckIfAnswerFound;
template <typename Pack, typename Untried, typename Output, typename Match, bool> struct CheckHead;

template <typename Pack, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct CheckIfPackTooBig<Pack, P<First, Rest...>, P<Output...>, Match, true> :
    FindPacksToMergeImpl<Pack, P<Rest...>, P<Output...>, Match> {};  // Move on to the next of the untried packs.

template <typename Pack, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct CheckIfPackTooBig<Pack, P<First, Rest...>, P<Output...>, Match, false> :
    CheckIfAnswerFound<Pack, P<First, Rest...>, P<Output...>, Match, std::is_same<typename First::argument_type, Match>::value> {};

template <typename Pack, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct CheckIfAnswerFound<Pack, P<First, Rest...>, P<Output...>, Match, true> : Identity<P<Output..., First>> {};  // We are done.

template <typename Pack, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct CheckIfAnswerFound<Pack, P<First, Rest...>, P<Output...>, Match, false> :
    CheckHead<Pack, P<First, Rest...>, P<Output...>, Match, std::is_same<typename First::argument_type, typename split<pack_size<typename First::argument_type>::value, Match>::head>::value> {};  // Check if the head of Match is the same as First::argument_type.

template <typename Pack, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct CheckHead<Pack, P<First, Rest...>, P<Output...>, Match, true> :
    FindPacksToMergeImpl<Pack, Pack, P<Output..., First>, typename split<pack_size<typename First::argument_type>::value, Match>::tail> {};  // Try with the tail now, starting back at the first type in Pack.

template <typename Pack, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct CheckHead<Pack, P<First, Rest...>, P<Output...>, Match, false> :
    FindPacksToMergeImpl<Pack, P<Rest...>, P<Output...>, Match> {};  // Move on to the next of the untried packs.

template <typename Pack, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct FindPacksToMergeHelper<Pack, P<First, Rest...>, P<Output...>, Match> :
    CheckIfPackTooBig<Pack, P<First, Rest...>, P<Output...>, Match, pack_size<Match>::value < pack_size<typename First::argument_type>::value> {};

template <typename Pack, template <typename...> class P, typename... Output, typename Match>
struct FindPacksToMergeHelper<Pack, P<>, P<Output...>, Match> : Identity<Failed> {};

template <typename Pack, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match, typename Result>
struct Check<Pack, P<First, Rest...>, P<Output...>, Match, Result> : Identity<Result> {};  // We are done.

template <typename Pack, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct Check<Pack, P<First, Rest...>, P<Output...>, Match, Failed> :
    FindPacksToMergeImpl<Pack, P<Rest...>, P<Output...>, Match> {};  // Move on to the next of the untried packs.

template <typename Pack, template <typename...> class P, typename First, typename... Rest, typename... Output, typename Match>
struct FindPacksToMergeImpl<Pack, P<First, Rest...>, P<Output...>, Match> :
    Check<Pack, P<First, Rest...>, P<Output...>, Match, typename FindPacksToMergeHelper<Pack, P<First, Rest...>, P<Output...>, Match>::type> {};

template <typename Pack, template <typename...> class P, typename... Output, typename Match>
struct FindPacksToMergeImpl<Pack, P<>, P<Output...>, Match> : Identity<Failed> {};  // This should never be reached, but is needed to compile (it was really hard to check why though).

template <typename> struct EmptyPack;

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

template <typename Pack, typename Match>
using FindPacksToMerge = typename FindPacksToMergeImpl<Pack, Pack, typename EmptyPack<Pack>::type, Match>::type;

template <typename... Ts>
class Storage {
    std::tuple<std::vector<Ts*>...> inventory;
    template <typename> struct AddDifferentTypes;
public:
    template <typename... Args>
    void addDifferentTypes (Args&&... args) {
        using TypesTuple = FindPacksToMerge<std::tuple<Ts...>, std::tuple<Args...>>;  // FindPacksToMerge adapted from the FindPacksToMerge.cpp program.
        AddDifferentTypes<TypesTuple>::execute(this, std::forward<Args>(args)...);
    }

    template <typename T>
    const std::vector<T*>& get() const {return std::get<std::vector<T*>>(inventory);}
private:
    template <typename T, typename... Args>
    void addItem (Args&&... args) {
        std::get<std::vector<T*>>(inventory).emplace_back(new T{std::forward<Args>(args)...});
    }
};

template <typename... Ts>
template <template <typename...> class P, typename... Vs>
struct Storage<Ts...>::AddDifferentTypes<P<Vs...>> {
    template <typename... Args>
    static void execute (Storage<Ts...>* storage, Args&&... args) {
        executeHelper<0, 0, P<Vs...>, std::tuple_size<typename Vs::argument_type>::value...>(storage, std::tie(args...));
    }
private:
    template <std::size_t N, std::size_t Offset, typename TypesTuple, std::size_t First, std::size_t... Rest, typename ArgsTuple>
    static void executeHelper (Storage<Ts...>* storage, const ArgsTuple& tuple) {
        add<N, Offset, TypesTuple>(storage, tuple, std::make_index_sequence<First>{});
        executeHelper<N + 1, Offset + First, TypesTuple, Rest...>(storage, tuple);
    }

    template <std::size_t N, std::size_t Offset, typename TypesTuple, typename ArgsTuple>
    static void executeHelper (Storage<Ts...>*, const ArgsTuple&) {}  // End of recursion. 

    template <std::size_t N, std::size_t Offset, typename TypesTuple, typename ArgsTuple, std::size_t... Is>
    static void add (Storage<Ts...>* storage, const ArgsTuple& tuple, std::index_sequence<Is...>) {
        storage->template addItem<std::tuple_element_t<N, TypesTuple>>(std::get<Offset + Is>(tuple)...);
    }
};

// Testing
struct Object {
    int a;
    bool b;
    char c;
    double d;
    using argument_type = std::tuple<int, bool, char, double>;
};

struct Thing {
    int a, b;
    char c;
    using argument_type = std::tuple<int, int, char>;
};

struct Number {
    int num;
    using argument_type = std::tuple<int>;
};

struct SemiObject {
    int a;
    bool b;
    char c;
    using argument_type = std::tuple<int, bool, char>;
};

int main() {
    Storage<Number, SemiObject, Object, Thing> storage;
    storage.addDifferentTypes (1,true,'a',3.5,   1,2,'t',   5,6,'p',  3,false,'b',1.8,   3,true,'t',  8,  3,  4,5,'s');  // Object, Thing, Thing, Object, SemiObject, Number, Number, Thing

    std::cout << "Objects: " << storage.get<Object>().size() << '\n';  // 2
    std::cout << "Things: " << storage.get<Thing>().size() << '\n';  // 3
    std::cout << "Numbers: " << storage.get<Number>().size() << '\n';  // 2
    std::cout << "SemiObjects: " << storage.get<SemiObject>().size() << '\n';  // 1
}

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

Finding a set of packs to merge to equal a given pack

c++

templates

variadic-templates

c++11