c++ - 将任意数量的类型插入到一组模板参数中

Question

InsertTypes<Pack, P<Ts...>, Is...>::type是类型为 Ts... 的包插入位置Is... ， 分别。例如，

InsertTypes<Pack<int, double, char, long, int>, Pack<short, float, std::string>, 2,4,1>::type,

是

Pack<int, std::string, double, short, char, long, float, int

(在 double 和 char 之间插入 short，在 long 和 int 之间插入 float，在 int 和 double 之间插入 std::string)。

我的方法:对 Is... 进行排序首先按相反顺序(从大到小)，并为 Ts... 中的每种类型应用 Insert和 Is... 中的每个整数为什么反向排序 Is... ？因为如果它们的顺序不对，插入一个类型会使位置偏移一个并弄乱其他插入。但是我的计划有一个缺陷，稍后我会解释。首先让我提供我编写的辅助函数，我测试过它们可以独立正常工作:

Insert<T, P<Types...>, N>::type是包P<Types...> T插入位置N。

template <typename, typename, typename, int> struct InsertHelper;

template <typename T, template <typename...> class P, typename First, typename... Rest, typename... Accumulated>
struct InsertHelper<T, P<First, Rest...>, P<Accumulated...>, 0> {
    using type = P<Accumulated..., T, First, Rest...>;
};

template <typename T, template <typename...> class P, typename First, typename... Rest, typename... Accumulated, int N>
struct InsertHelper<T, P<First, Rest...>, P<Accumulated...>, N> : InsertHelper<T, P<Rest...>, P<Accumulated..., First>, N-1> {};

template <typename, typename, int> struct Insert;

template <typename T, template <typename...> class P, typename... Types, int N>
struct Insert<T, P<Types...>, N> : InsertHelper<T, P<Types...>, P<>, N> {};

现在 ReverseSortIntSequence(使用快速排序):

template <int, typename> struct PrependInt;

template <int N, template <int...> class Z, int... Is>  
struct PrependInt<N, Z<Is...>> {  
    using type = Z<N, Is...>;  
};

template <template<int> class, typename> struct FilterInts;  

template <template<int> class F, template <int...> class Z, int I, int... Is>  
struct FilterInts<F, Z<I, Is...>> {
    using type = typename std::conditional<F<I>::value,
        typename PrependInt<I, typename FilterInts<F, Z<Is...>>::type>::type,
        typename FilterInts<F, Z<Is...>>::type
    >::type;  
};

template <template<int> class F, template <int...> class Z>  
struct FilterInts<F, Z<>> {  
    using type = Z<>;  
};  

template <typename, typename> struct MergeIntSequences;  

template <template <int...> class Z, int... Is, int... Js>  
struct MergeIntSequences<Z<Is...>, Z<Js...>> {  
    using type = Z<Is..., Js...>;
};

template <typename> struct ReverseSortIntSequence;  

template <template <int...> class Z, int N, int... Is>  
struct ReverseSortIntSequence<Z<N, Is...>> {  
    template<int I> struct less_than : std::integral_constant<bool, (I >= N)> {};
    template <int I> struct more_than : std::integral_constant<bool, (I < N)> {};  
    using subsequence_less_than_N = typename FilterInts<less_than, Z<Is...>>::type;
    using subsequence_more_than_N = typename FilterInts<more_than, Z<Is...>>::type; 
    using type = typename MergeIntSequences<typename ReverseSortIntSequence<subsequence_less_than_N>::type,  
        typename PrependInt<N, typename ReverseSortIntSequence<subsequence_more_than_N>::type>::type 
    >::type;
};

template<template <int...> class Z>  
struct ReverseSortIntSequence<Z<>> {  
    using type = Z<>;  
};

现在InsertTypes本身:

template <typename, typename, typename> struct InsertTypesHelper;

template <typename Pack, template <typename...> class P, template <int...> class Z>
struct InsertTypesHelper<Pack, P<>, Z<>> {
    using type = Pack;
};

template <typename Pack, template <typename...> class P, typename First, typename... Rest, template <int...> class Z, int N, int... Ns>
struct InsertTypesHelper<Pack, P<First, Rest...>, Z<N, Ns...>> : InsertTypesHelper<typename Insert<First, Pack, N>::type, P<Rest...>, Z<Ns...>> {};

template <typename, typename, int...> struct InsertTypes;

template <typename Pack, template <typename...> class P, typename... Types, int... Is>
struct InsertTypes<Pack, P<Types...>, Is...> : InsertTypesHelper<Pack, P<Types...>, typename ReverseSortIntSequence<index_sequence<Is...>>::type> {};

现在，我的测试:

int main() {
    std::cout << std::is_same<
        typename ReverseSortIntSequence<index_sequence<5,10,8,4,0,2,1,2,7,8,3>>::type,
        index_sequence<10,8,8,7,5,4,3,2,2,1,0>
    >::value << std::endl;  // true

    std::cout << std::is_same<
        InsertTypesHelper<Pack<int, double, char, long, int>, Pack<float, short, std::string>, index_sequence<4,2,1>>::type,
        Pack<int, std::string, double, short, char, long, float, int>
    >::value << std::endl;  // true (*)

    std::cout << std::is_same<
        typename ReverseSortIntSequence<index_sequence<2,4,1>>::type,
        index_sequence<4,2,1>
    >::value << std::endl;  // true (**)

    std::cout << std::is_same<
        InsertTypes<Pack<int, double, char, long, int>, Pack<short, float, std::string>, 2,4,1>::type,
        Pack<int, std::string, double, short, char, long, float, int>
    >::value << std::endl;  // false (rats!)
}

我得到上面的错误，因为尽管上面的 (*) 和 (**) 为真，我们必须有 Pack<short, float, std::string>以与 2,4,1 相同的方式排列，以便以相反的排序顺序获得它。我可以继续进行此修复，但现在已经过火了。我仍然会继续这样做，但我严重怀疑有更好的方法，可能也很短。

这里有什么好的想法吗？我想提取索引确定的类型对(插入的类型将在对之间)，但如果原始包中有重复类型(并且也因为插入的类型也一样)，这将不起作用。

更新:我完成了上面讨论的排列助手，现在一切正常。但一定有比这一切困惑更好、更短的解决方案。

template <int, typename> struct NthType;

template <int N, template <typename...> class P, typename First, typename... Rest>
struct NthType<N, P<First, Rest...>> : NthType<N-1, P<Rest...>> {};

template <template <typename...> class P, typename First, typename... Rest>
struct NthType<0, P<First, Rest...>> {
    using type = First;
};

template <int, int, typename> struct FindIndexOfIntHelper;

template <int N, int FindMe, template <int...> class Z, int... Rest>
struct FindIndexOfIntHelper<N, FindMe, Z<FindMe, Rest...>> : std::integral_constant<int, N> {};

template <int N, int FindMe, template <int...> class Z>
struct FindIndexOfIntHelper<N, FindMe, Z<>> : std::integral_constant<int, -1> {};  // Not found.

template <int N, int FindMe, template <int...> class Z, int First, int... Rest>
struct FindIndexOfIntHelper<N, FindMe, Z<First, Rest...>> : FindIndexOfIntHelper<N+1, FindMe, Z<Rest...>> {};

template <int FindMe, typename Pack>
using FindIndexOfInt = FindIndexOfIntHelper<0, FindMe, Pack>;

template <typename, typename, typename, typename> struct PermutePackHelper;

template <typename Pack, template <typename...> class P, typename... Accumulated, typename IndicesPack, template <int...> class Z>
struct PermutePackHelper<Pack, P<Accumulated...>, IndicesPack, Z<>> {
    using type = P<Accumulated...>;
};

template <typename Pack, template <typename...> class P, typename... Accumulated, typename IndicesPack, template <int...> class Z, int I, int... Is>
struct PermutePackHelper<Pack, P<Accumulated...>, IndicesPack, Z<I, Is...>> :
    PermutePackHelper<Pack, P<Accumulated..., typename NthType<FindIndexOfInt<I, IndicesPack>::value, Pack>::type>,
        IndicesPack, Z<Is...>> {};

template <typename, typename, typename> struct PermutePack;

template <template <typename...> class P, typename... Types, template <int...> class Z, int... Is, int... Js>
struct PermutePack<P<Types...>, Z<Is...>, Z<Js...>> : PermutePackHelper<P<Types...>, P<>, Z<Is...>, Z<Js...>> {};

Answer 1

有一种使用 boost::mpl 的方法，我认为它更容易理解(？)我添加了很多注释来解释这些步骤，并适当缩进到使代码更清晰一些...可能会有所帮助...

#include <iostream>
#include <type_traits>

#include <boost/mpl/vector_c.hpp>
#include <boost/mpl/sort.hpp>
#include <boost/mpl/comparison.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/mpl/equal.hpp>
#include <boost/mpl/next_prior.hpp>
#include <boost/mpl/insert.hpp>
#include <boost/mpl/deref.hpp>
#include <boost/mpl/advance.hpp>
#include <boost/mpl/pair.hpp>
#include <boost/mpl/size.hpp>
#include <boost/mpl/transform.hpp>

using namespace boost::mpl;

template <typename R, typename It, typename End>
struct type_inserter
{ 
  // index to insert
  typedef typename deref<It>::type::first KType;
  // type to insert
  typedef typename deref<It>::type::second VType;
  // recurse
  typedef typename type_inserter<
    typename insert<
      R,
      // calculate the location based on the index
      typename advance<typename begin<R>::type, KType>::type,
      VType
    >::type,
    typename next<It>::type,
    End
  >::type type;
};

template <typename R, typename End>
struct type_inserter<R, End, End>
{
  typedef R type;
};

template <typename P>
struct index_access
{
  typedef typename P::first type;
};

struct make_pair
{
  template<typename Kv, typename Pv>
  struct apply
  {
    typedef pair<Kv, Pv> type;
  };
};

template <typename P1, typename P2, int ...I>
struct insert_pack
{
  // transform P2 and indexes
  static_assert(sizeof...(I) == size<P2>::value, "indexes/count P2 mismatch");
  // this iterates through both sequences, constructing a pair and inserting into a vector
  typedef typename transform<vector_c<int, I...>, P2, make_pair, back_inserter<vector0<>>>::type entries;
  // sort the sequence by the index..
  typedef typename sort<entries, greater<index_access<_1>, index_access<_2>>>::type reversed;
  // once sorted, insert the sorted range into the main vector using custom inserter
  typedef typename type_inserter<P1, typename begin<reversed>::type, typename end<reversed>::type>::type type;
};

int main()
{
  typedef vector<int, double, char, long, int> pack1;
  typedef vector<short, float, std::string> pack2;
  // this combines the pack
  typedef insert_pack<pack1, pack2, 2, 4, 1>::type combined;
  // this is what we expect
  typedef vector<int, std::string, double, short, char, long, float, int> packs;
  // sanity check
  BOOST_MPL_ASSERT(( equal< packs, combined> ));
}