假设我有两个可变参数模板； typename...T，typename...U，我该如何找到它们；

1. 串联
2. 最大公共(public)子序列
3. 最大公共(public)子序列的逆

据我了解，连接很简单； (t..., u...)，但是如何找到两者的最大公共(public)子序列呢？ - 这有可能吗？

最佳答案

这是一个计算对元组类型对的集合操作的解决方案。我假设元组可以用来保存变量参数包，所以一旦你有了 Ts...和 Us... ，你这样做:

typename tuple_intersect<std::tuple<Ts...>, std::tuple<Us...>>::type

这为您提供了一个元组，其中 Vs...是Ts...的交集和 Us... .如果需要提取Vs...再次作为参数包，只需提供元组作为接受 tuple<Ts...> 的函数的输入。 :

template<typename... Vs>
void func(std::tuple<Vs...>)
{
    // Here, you have Vs... (= Us... & Ts...) as an argument pack
}

框架:

以下是一些简单的元函数，它们对以下所有主要元函数都是通用的:

template<typename T, typename... Ts>
struct is_member_of_type_seq { static const bool value = false; };

template<typename T, typename U, typename... Ts>
struct is_member_of_type_seq<T, U, Ts...>
{
    static const bool value = std::conditional<
        std::is_same<T, U>::value,
        std::true_type,
        is_member_of_type_seq<T, Ts...>
        >::type::value;
};

template<typename, typename>
struct append_to_type_seq { };

template<typename T, typename... Ts>
struct append_to_type_seq<T, std::tuple<Ts...>>
{
    using type = std::tuple<Ts..., T>;
};

template<typename, typename>
struct prepend_to_type_seq { };

template<typename T, typename... Ts>
struct prepend_to_type_seq<T, std::tuple<Ts...>>
{
    using type = std::tuple<T, Ts...>;
};

1 - Concatenation

这个很简单:

template<typename, typename>
struct concat_type_seq { };

template<typename... Ts, typename... Us>
struct concat_type_seq<std::tuple<Ts...>, std::tuple<Us...>>
{
    using type = std::tuple<Ts..., Us...>;
};

还有一些测试:

static_assert(
    std::is_same<
        concat_type_seq<
            std::tuple<char, int, bool>,
            std::tuple<double, double, int>
            >::type,
        std::tuple<char, int, bool, double, double, int>
        >::value,
    "Error"
    );

2 - Longest common subsequence

这个稍微更复杂:

namespace detail
{
    // Meta-function that returns, given two sequences S1 and S2, the longest
    // subsequence of S1 in S2 that starts with the first element of S1 and
    // begins at the first element of S2 (in other words, it returns the
    // subsequence S2[0]..S2[N] such that S1[i] = S2[i] for each 0 <= i <= N.
    template<typename, typename>
    struct match_seq_in_seq_from_start
    {
        using type = std::tuple<>;
    };

    template<typename T, typename U, typename... Ts, typename... Us>
    struct match_seq_in_seq_from_start<std::tuple<T, Ts...>, std::tuple<U, Us...>>
    {
        using type = typename std::conditional<
            std::is_same<T, U>::value,
            typename prepend_to_type_seq<
                T,
                typename match_seq_in_seq_from_start<
                    std::tuple<Ts...>,
                    std::tuple<Us...>
                    >::type
                >::type,
            std::tuple<>
            >::type;
    };

    // Some testing...
    static_assert(
        std::is_same<
            match_seq_in_seq_from_start<
                std::tuple<int, double, char>,
                std::tuple<int, double, long>
                //         ^^^^^^^^^^^
                >::type,
            std::tuple<int, double>
            >::value,
        "Error!"
        );

    // Meta-function that returns the same as the meta-function above,
    // but starting from the first element of S2 which is identical to
    // the first element of S1.
    template<typename, typename>
    struct match_first_seq_in_seq
    {
        using type = std::tuple<>;
    };

    template<typename T, typename U, typename... Ts, typename... Us>
    struct match_first_seq_in_seq<std::tuple<T, Ts...>, std::tuple<U, Us...>>
    {
        using type = typename std::conditional<
            std::is_same<T, U>::value,
            typename match_seq_in_seq_from_start<
                std::tuple<T, Ts...>,
                std::tuple<U, Us...>
                >::type,
            typename match_first_seq_in_seq<
                std::tuple<T, Ts...>,
                std::tuple<Us...>
                >::type
            >::type;
    };

    // Some testing...
    static_assert(
        std::is_same<
            match_first_seq_in_seq<
                std::tuple<int, double, char>,
                std::tuple<bool, char, int, double, long, int, double, char>
                //                     ^^^^^^^^^^^
                >::type,
            std::tuple<int, double>
            >::value,
        "Error!"
        );

    // Meta-function that returns, given two sequences S1 and S2, the longest
    // subsequence of S1 in S2 that starts with the first element of S1.
    template<typename T, typename U>
    struct match_seq_in_seq
    {
        using type = std::tuple<>;
    };

    template<typename U, typename... Ts, typename... Us>
    struct match_seq_in_seq<std::tuple<Ts...>, std::tuple<U, Us...>>
    {
        using type1 = typename match_first_seq_in_seq<
            std::tuple<Ts...>,
            std::tuple<U, Us...>
            >::type;

        using type2 = typename match_seq_in_seq<
            std::tuple<Ts...>, 
            std::tuple<Us...>
            >::type;

        using type = typename std::conditional<
            (std::tuple_size<type1>::value > std::tuple_size<type2>::value),
            type1,
            type2
            >::type;
    };

    // Some testing...
    static_assert(
        std::is_same<
            match_seq_in_seq<
                std::tuple<int, double, char>,
                std::tuple<char, int, double, long, int, double, char>
                //                                  ^^^^^^^^^^^^^^^^^
                >::type,
            std::tuple<int, double, char>
            >::value,
        "Error!"
        );
}

// Meta-function that returns, given two sequences S1 and S2, the longest
// subsequence of S1 in S2 (longest common subsequence).
template<typename T, typename U>
struct max_common_subseq
{
    using type = std::tuple<>;
};

template<typename T, typename... Ts, typename... Us>
struct max_common_subseq<std::tuple<T, Ts...>, std::tuple<Us...>>
{
    using type1 = typename detail::match_seq_in_seq<
        std::tuple<T, Ts...>,
        std::tuple<Us...>
        >::type;

    using type2 = typename max_common_subseq<
        std::tuple<Ts...>,
        std::tuple<Us...>
        >::type;

    using type = typename std::conditional<
        (std::tuple_size<type1>::value > std::tuple_size<type2>::value),
        type1,
        type2
        >::type;
};

还有一些测试:

// Some testing...
static_assert(
    std::is_same<
        max_common_subseq<
            std::tuple<int, double, char>,
            std::tuple<char, int, char, double, char, long, int, bool, double>
            >::type,
        std::tuple<double, char>
        >::value,
    "Error!"
    );

// Some more testing...
static_assert(
    std::is_same<
        max_common_subseq<
            std::tuple<int, double, char, long, long, bool>,
            //                      ^^^^^^^^^^^^^^^^
            std::tuple<char, long, long, double, double, char>
            //         ^^^^^^^^^^^^^^^^
            >::type,
        std::tuple<char, long, long>
        >::value,
    "Error!"
    );

3 - Inversion

这是一个反转类型序列的特征(返回一个带有反转类型列表的元组):

template<typename... Ts>
struct revert_type_seq
{
    using type = std::tuple<>;
};

template<typename T, typename... Ts>
struct revert_type_seq<T, Ts...>
{
    using type = typename append_to_type_seq<
        T,
        typename revert_type_seq<Ts...>::type
        >::type;
};

还有一些测试:

// Some testing...
static_assert(
    std::is_same<
        revert_type_seq<char, int, bool>::type,
        std::tuple<bool, int, char>
        >::value,
    "Error"
    );

4 - Intersection

这不是要求的，而是作为奖励提供的:

template<typename, typename>
struct intersect_type_seq
{
    using type = std::tuple<>;
};

template<typename T, typename... Ts, typename... Us>
struct intersect_type_seq<std::tuple<T, Ts...>, std::tuple<Us...>>
{
    using type = typename std::conditional<
        !is_member_of_type_seq<T, Us...>::value,
        typename intersect_type_seq<
            std::tuple<Ts...>,
            std::tuple<Us...>>
            ::type,
        typename prepend_to_type_seq<
            T,
            typename intersect_type_seq<
                std::tuple<Ts...>,
                std::tuple<Us...>
                >::type
            >::type
        >::type;
};

还有一些测试:

// Some testing...
static_assert(
    std::is_same<
        intersect_type_seq<
            std::tuple<char, int, bool, double>,
            std::tuple<bool, long, double, float>
            >::type,
        std::tuple<bool, double>
        >::value,
        "Error!"
        );

关于c++ - 将集合论应用于 C++11 可变参数模板，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15274816/