Применение теории множеств к C++ 11 вариационных шаблонов

Question

Скажем, у меня есть два вариативных шаблона; typename... T, typename... U, как бы я нашел их;

1. Concatenation
2. Максимальная общая подпоследовательность
3. Inverse максимальной общей подпоследовательности

Итак, насколько я понимаю, конкатенация проста; (t..., u...), но как насчет нахождения максимальной общей подпоследовательности двух? - возможно ли это?

Answer 1

Здесь вы найдете решение, которое вычисляет функции для пар типов кортежей. Я предполагаю, что кортежи могут быть использованы для хранения переменных пакетов аргументов, так что, как только у вас есть 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 
} 

---

Framework:

Вот несколько простых мета -функции, которые являются общими для всех основных мета-функций ниже:

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 - Наибольшая общая подпоследовательность

Это один несколько сложнее:

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 - Инверсия

Вот черта для инвертирования последовательности типа (возвращает кортеж со списком перевернутого типа):

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 - Пересечение

Это не было предложено, но предоставляется в качестве бонуса:

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!" 
     );