小贝子编程

模板参数的组合排序



要对一组模板整数进行排序，

template <int...> struct sequence;
int main() {
    using Sequence = sequence<3,6,1,0,9,5,4,7,2,8>;
    static_assert(std::is_same<
        sort<int, Sequence, less_than>::type,
        sequence<0,1,2,3,4,5,6,7,8,9>
    >::value, "");
}

我们可以使用以下实现（在GCC 5.3上测试）：

#include <iostream>
#include <type_traits>
namespace meta {
    template <typename T, T, typename> struct prepend;
    template <typename T, T Add, template <T...> class Z, T... Is>  
    struct prepend<T, Add, Z<Is...>> {  
        using type = Z<Add, Is...>;  
    };
    template <typename T, typename Pack1, typename Pack2> struct concat;
    template <typename T, template <T...> class Z, T... Ts, T... Us>
    struct concat<T, Z<Ts...>, Z<Us...>> {
        using type = Z<Ts..., Us...>;
    };
}
template <int I, int J>
struct less_than : std::conditional<(I < J), std::true_type, std::false_type>::type {};
template <typename T, typename Pack, template <T, T> class = less_than> struct sort;  
template <typename T, template <T...> class Z, template <T, T> class Comparator>  
struct sort<T, Z<>, Comparator> {  
    using type = Z<>;
};
template <typename T, typename Pack, template<T> class UnaryPredicate> struct filter;  
template <typename T, template <T...> class Z, template<T> class UnaryPredicate, T I, T... Is>  
struct filter<T, Z<I, Is...>, UnaryPredicate> {
    using type = typename std::conditional<UnaryPredicate<I>::value,
        typename meta::prepend<T, I, typename filter<T, Z<Is...>, UnaryPredicate>::type>::type,
        typename filter<T, Z<Is...>, UnaryPredicate>::type
    >::type;  
};
template <typename T, template <T...> class Z, template<T> class UnaryPredicate>  
struct filter<T, Z<>, UnaryPredicate> {  
    using type = Z<>;  
};  
template <typename T, template <T...> class Z, T N, T... Is, template <T, T> class Comparator>  
struct sort<T, Z<N, Is...>, Comparator> {  // Using the quicksort method.
    template <T I> struct less_than : std::integral_constant<bool, Comparator<I,N>::value> {};
    template <T I> struct more_than : std::integral_constant<bool, !Comparator<I,N>::value> {};  
    using subsequence_less_than_N = typename filter<T, Z<Is...>, less_than>::type;
    using subsequence_more_than_N = typename filter<T, Z<Is...>, more_than>::type; 
    using type = typename meta::concat<T, typename sort<T, subsequence_less_than_N, Comparator>::type,  
        typename meta::prepend<T, N, typename sort<T, subsequence_more_than_N, Comparator>::type>::type 
    >::type;
};
// Testing
template <int...> struct sequence;
int main() {
    using Sequence = sequence<3,6,1,0,9,5,4,7,2,8>;
    static_assert(std::is_same<
        sort<int, Sequence, less_than>::type,
        sequence<0,1,2,3,4,5,6,7,8,9>
    >::value, "");
}

现在假设我们想要组成几个二进制谓词来进行排序。例如：

 25 placed first before anything else.
 16 to be placed after everything else.
 Even numbers placed after all 25's, if any, have been placed (and the even numbers sorted in increasing value among themselves).
 After these order on ascending last digit, except that last digit 7 appears before other last digits.
 If last digits are equal, order by increasing value.

我想使用类似的东西来实现composed_sort

template <typename T, T, T, template <T, T> class...> struct composed_binary_predicates;
template <typename T, T A, T B, template <T, T> class Comparator, template <T, T> class... Rest>
struct composed_binary_predicates<T, A, B, Comparator, Rest...> : std::conditional_t<
    Comparator<A,B>::value,
    std::true_type,
    std::conditional_t<
        Comparator<B,A>::value,
        std::false_type,
        composed_binary_predicates<T, A, B, Rest...>
    >
> {};
template <typename T, T A, T B, template <T, T> class Comparator>
struct composed_binary_predicates<T, A, B, Comparator> : Comparator<A,B> {};

因此，我们使用了一组二进制谓词。如果第一个Comparator有Comparator<A,B>::value == true，那么值为true，如果Comparator<B,A>::value == true，那么值是false，否则检查下一个谓词，依此类推。这种二元谓词的组合将用于执行排序。因此，我尝试将sort本身修改为以下内容：

template <typename T, typename Sequence,
    template <typename U, U, U, template <U,U> class...> class Comparator,
    template <T, T> class... Preds> struct composed_sort;
template <typename T, template <T...> class Z, T N, T... Is, template <typename U, U, U, template <U,U> class...> class Comparator, template <T, T> class... Preds>  
struct composed_sort<T, Z<N, Is...>, Comparator, Preds...> {
    template <T I> struct less_than : std::integral_constant<bool, Comparator<T,I,N, Preds...>::value> {};
    template <T I> struct more_than : std::integral_constant<bool, !Comparator<T,I,N, Preds...>::value> {};  
    using subsequence_less_than_N = typename filter<T, Z<Is...>, less_than>::type;
    using subsequence_more_than_N = typename filter<T, Z<Is...>, more_than>::type; 
    using type = typename meta::concat<T, typename composed_sort<T, subsequence_less_than_N, Comparator, Preds...>::type,  
        typename meta::prepend<T, N, typename composed_sort<T, subsequence_more_than_N, Comparator, Preds...>::type>::type 
    >::type;
};

然后可以用作

composed_sort<int, Sequence, composed_binary_predicates, Predicates...>::type

但是GCC 5.3会出现内部编译器错误，因此无法处理代码。有没有一个变通方法，或者一个更简单的实现来完成这项工作？

template<class T, template<T,T> class C>
struct zComp {
  template<T a, T b>
  using result=C<a,b>;
  using type=T;
};
template<class C0, class...Cs>
struct compose_comparators;
template<class C0>
struct compose_comparators<C0>:C0{};
template<class C0, class C1, class...Cs>
struct compose_comparators<C0, C1, Cs...> {
  using type=typename C0::type;
private:
  template<type a, type b>
  using r0 = typename C0::template result<a,b>;
  template<type a, type b>
  using r1 = typename compose_comparators<C1, Cs...>::template result<a,b>;
public:
  template<type a, type b>
  using result = std::conditional_t<
    (r0<a,b>::value || r0<b,a>::value),
    r0<a,b>,
    r1<a,b>
  >;
};

要使用以上内容，请使用谓词，将它们封装在zComp中。如果您不在乎，请在a,b和b,a上返回false。

将你的原始X<int,int>比较器输入到zComp<int, X>——你可以更改上面的内容以使用模板包，但我在元编程中对类型有偏见，所以我将模板打包到zComps中。

活生生的例子。

哦，还有一个有用的技巧——让sequence {}有一个空的{}体。然后，您可以使用赋值作为更好的调试消息"is_same"测试，因为您被告知lhs和rhs类型是什么，并且它们不兼容。

好的，我用第一个方法解决了编译器的问题，并得到了我想要的语法：composed_sort<T, Sequence, Predicates...>::type。

#include <iostream>
#include <type_traits>
#include <utility>
namespace meta {
    template <typename T, T, typename> struct prepend;
    template <typename T, T Add, template <T...> class Z, T... Is>  
    struct prepend<T, Add, Z<Is...>> {  
        using type = Z<Add, Is...>;  
    };
    template <typename T, typename Pack1, typename Pack2> struct concat;
    template <typename T, template <T...> class Z, T... Ts, T... Us>
    struct concat<T, Z<Ts...>, Z<Us...>> {
        using type = Z<Ts..., Us...>;
    };
}
template <typename T, typename Pack, template <T> class UnaryPredicate> struct filter;  
template <typename T, template <T...> class Z, template <T> class UnaryPredicate, T I, T... Is>  
struct filter<T, Z<I, Is...>, UnaryPredicate> : std::conditional_t<UnaryPredicate<I>::value,
    meta::prepend<T, I, typename filter<T, Z<Is...>, UnaryPredicate>::type>,
    filter<T, Z<Is...>, UnaryPredicate>
> {};
template <typename T, template <T...> class Z, template <T> class UnaryPredicate>  
struct filter<T, Z<>, UnaryPredicate> {  
    using type = Z<>;  
};
template <typename T, T A, T B, template <T, T> class Comparator, template <T, T> class... Rest>
struct composed_binary_predicates : std::conditional_t<
    Comparator<A,B>::value,
    std::true_type,
    std::conditional_t<
        Comparator<B,A>::value,
        std::false_type,
        composed_binary_predicates<T, A, B, Rest...>
    >
> {};
template <typename T, T A, T B, template <T, T> class Comparator>
struct composed_binary_predicates<T, A, B, Comparator> : Comparator<A,B> {};
template <typename T, typename Sequence, template <T, T> class... Preds> struct composed_sort;
template <typename T, template <T...> class Z, T N, T... Is, template <T, T> class... Predicates>  
struct composed_sort<T, Z<N, Is...>, Predicates...> {  // Using the quick sort method.
    template <T I> struct less_than : std::integral_constant<bool, composed_binary_predicates<T,I,N, Predicates...>::value> {};
    template <T I> struct more_than : std::integral_constant<bool, !composed_binary_predicates<T,I,N, Predicates...>::value> {};  
    using subsequence_less_than_N = typename filter<T, Z<Is...>, less_than>::type;
    using subsequence_more_than_N = typename filter<T, Z<Is...>, more_than>::type; 
    using type = typename meta::concat<T, typename composed_sort<T, subsequence_less_than_N, Predicates...>::type,  
        typename meta::prepend<T, N, typename composed_sort<T, subsequence_more_than_N, Predicates...>::type>::type 
    >::type;
};
template <typename T, template <T...> class Z, template <T, T> class... Predicates>  
struct composed_sort<T, Z<>, Predicates...> {  
    using type = Z<>;
};
// Testing
template <int...> struct sequence;
template <int I, int J>  // The standard less than.
struct less_than : std::conditional_t<(I < J), std::true_type, std::false_type> {};
template <int N>
struct N_first {
    template <int I, int J>
    struct result : std::conditional_t<(I == N && J != N), std::true_type, std::false_type> {};
};
template <int I, int J>  // 25 placed first before anything else.
using twentyfive_first = typename N_first<25>::template result<I,J>;
template <int N>
struct N_last {
    template <int I, int J>
    struct result : std::conditional_t<(I != N && J == N), std::true_type, std::false_type> {};
};
template <int I, int J>  // 16 to be placed after everything else.
using sixteen_last = typename N_last<16>::template result<I,J>;
template <int I, int J>  // Even numbers placed after all 25's, if any, have been placed (and the even numbers sorted in increasing value among themselves).
struct even_numbers : std::conditional_t<((I%2 == 0 && J%2 != 0) || (I%2 == 0 && J%2 == 0 && I < J)), std::true_type, std::false_type> {}; 
int main() {
    using Sequence = sequence<16,3,6,16,1,0,9,5,4,16,25,7,2,8,25>;
    static_assert (std::is_same<
        composed_sort<int, Sequence, less_than>::type,
        sequence<0,1,2,3,4,5,6,7,8,9,16,16,16,25,25>
    >::value, "");
    static_assert (std::is_same<
        composed_sort<int, Sequence, twentyfive_first, sixteen_last, even_numbers, less_than>::type,
        sequence<25,25,0,2,4,6,8,1,3,5,7,9,16,16,16>
    >::value, "");
}

这种实现的主要缺点是：忽略了DRY原理，因为现在结构sort和composed_sort基本上是相互重复的。可以说，composed_sort<T, Sequence, Predicates...>::type漂亮的语法并没有真正抵消这种对DRY原则的违反。亚克的方法肯定更好。

相关内容

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium