模板元编程实战--类型列表算法

这篇文章主要说明了我学习的过程，作为一种记事本来记录，它讲述了如何处理一个类型列表的拼接，查找，排序，等算法。

数据结构：

template<typename... Ts>
struct TypeList {

    struct isTypeList{};
    using type = TypeList<Ts...>;
    constexpr static size_t size = sizeof...(Ts);

    // 成员元函数，在列表的尾部添加元素
    template<typename... T>
    using append = TypeList<Ts..., T...>;
    // 成员元函数，在列表的头部添加元素
    template<typename... T>
    using prepend = TypeList<T..., Ts...>;
    // 成员元函数，将该列表转换为其他模板类
    template<template<typename...> typename T>
    using to = T<Ts...>;
};

使用该数据结构来实现各种算法。

为该结构编写一个约定的接口：

template<typename T>
concept TL = requires{
    typename T::isTypeList;
    typename T::type;
};

算法1，根据条件筛选类型：

template<TL in,template<typename> typename P,TL out = TypeList<> >
struct Filter : out {};

template<template<typename> typename P,TL out,typename T,typename... Ts>
struct Filter<TypeList<T,Ts...>,P,out>:std::conditional_t<P<T>::value,Filter<TypeList<Ts...>,P,typename out::template append<T>>,
    Filter<TypeList<Ts...>,P,out> >{};

template<TL in, template<typename> typename P, TL out = TypeList<> >
using Filter_t = Filter<in, P, out>::type;

Filter函数会根据回调函数P来决定哪些类型应该被添加到继承列表，最后将列表给out结束。

算法2，根据条件选择传递类型

template<typename T>
struct Return { using type = T; };

template<TL in,typename Init,template<typename,typename> class P>
struct Fold:Return<Init>{};

template<typename Init,template<typename,typename> class P,typename T,typename... Ts>
struct Fold<TypeList<T,Ts...>,Init,P>:Fold<TypeList<Ts...>,typename P<Init,T>::type,P>{};

template<TL in, typename Init, template<typename, typename> class P>
using Fold_t = Fold<in, Init, P>::type;

Fold函数与Filter差不多，其区别就是Fold函数包含的高阶函数P比Filter更加抽象，Fold不会做分支筛选，而是完全由高阶函数P来决定，这也就加强了他的适用性。

算法3，类型列表的拼接

template<TL... In> struct Concat;

template<TL... In> using Concat_t = typename Concat<In...>::type;

template<> struct Concat<>:TypeList<>{};

template<TL In> struct Concat<In> : TypeList<In>{};

template<TL In,TL In2,TL... Rest> struct Concat<In,In2,Rest...> : Concat_t<Concat_t<In,In2>,Rest...>{};

template<TL In, TL In2> struct Concat<In, In2> :In2::template to<In::template append>{};

将两个列表拼接起来，通过特化具有两个列表的Concat来不断地处理参数包Rest，直到它只有一个参数的时候，终止并返回。

算法4，查找

template<TL In,typename T>
class Elem {
public:
    template<typename T1,typename Y1>
    using Find = std::conditional_t<T1::value, T1, std::is_same<Y1, T> >;
    using type = Fold<In, std::false_type, Find>::type;
public:
    static constexpr bool value = type::value;
};
// 查找算法的另一种实现：
template<TL In,typename T>
struct Elem2;

template<typename... Ts,typename T>
struct Elem2<TypeList<Ts...> , T> : std::bool_constant<(false||...||std::is_same_v<T,Ts>) >{};

查找算法用于检查一个列表内，是否具有指定的元素，如果有返回一个包含该属性的数据结构。通过Fold函数来判定返回的结构应该包含什么样的属性。

算法5，去重（重复）

template<TL in>
struct unqiue {
    template<TL out,typename T>
    using Append = std::conditional_t<Elem<out, T>::value, out,typename out::template append<T> >;
    using type = Fold<in, TypeList<>, Append >::type;
};

如果Append函数发现新列表的参数包中有相同的类型，那么数据将不会加入到新的列表中。

算法6，按条件分割

template<TL in,template<typename> typename P>
struct partition {
    template<typename T>
    using NotP = std::bool_constant<!P<T>::value>;
    struct type {
        using Statisfied = Filter_t<in, P>;
        using Rest = Filter_t<in, NotP>;
    };
};

template<TL in,template<typename> typename P>
using partition_t = partition<in, P>::type;

高阶函数P决定了应该将哪些数据返回给Filter的type，相反，对P取反即可得到相对的类型表。

算法7，排序列表

template<TL in,template<typename,typename> typename Cmp>
struct Sort : TypeList<>{};

template<template<typename,typename> typename Cmp,typename Pivot,typename... Ts>
struct Sort<TypeList<Pivot, Ts...>, Cmp> {
    template<typename E>
    using LT = Cmp<E, Pivot>;

    using  P = partition_t<TypeList<Ts...>, LT>;

    using S = typename Sort<typename P::Statisfied, Cmp>::type;
    using B = typename Sort<typename P::Rest, Cmp>::type;

    using type = Concat_t<typename S::template append<Pivot>, B>;
};

template<TL in,template<typename,typename> typename Cmp>
using Sort_t = Sort<in, Cmp>::type;

通过条件展开列表，然后有Concat重新拼接。

算法只是一种思路，思路不同实现也不同，例如上面的拼接，特化的两个类型拼接为一个，下面是另一种思路。

 template<typename... T, typename... Ts> struct Concat<TypeList<T...>, TypeList<Ts...> > : TypeList<T..., Ts...> {};

目的只为了学习思路，而不是死记硬背。Fold也可以实现Filter的功能，并且也可以出现更多的变种。

一些具体是使用示例：

Sort：

　　　　template<typename T,typename Y>
　　　　using TypeCmp = std::bool_constant<(sizeof(T) < sizeof(Y))>;

　　-----------------------------------------
    using list1 = TypeList<char, double, float, long long, int, int,char>;
    using sq = Sort_t<list1, TypeCmp>::type; // TypeList<char,char,float,int,int,double,long long>

partition:

　　　　template<typename T>
　　　　struct F {
　　　　　　static constexpr bool value = (sizeof(T) > 4);
　　　　};

　　--------------------------------------
　　 using list1 = TypeList<char, double, float, long long, int, int,char>;
    using we = partition<list1, F>::type::Rest::type;      // TypeList<char,float,int,int>
    using wb = partition<list1, F>::type::Statisfied::type;    // TypeList<double,long long>

unique:

　　 using list1 = TypeList<char, double, float, long long, int, int,char>;
    using t = unqiue<list1>::type;    // TypeList<char,double,float,long long,int>

Elem:

using list1 = TypeList<char, double, float, long long, int, int,char>;

constexpr bool s = Elem<list1, char>::value;     //true

Fold:

template<typename T,typename Y>
using TypeSize = std::integral_constant<size_t, T::value + sizeof(Y)>;
-----------------------------
using list1 = TypeList<char, double, float, long long, int, int,char>;
using Type = Fold<list1, std::integral_constant<size_t, 0>, TypeSize>::type;     

template<typename out,typename T>
struct Fun {
    using type = std::conditional_t<std::is_integral_v<T>, typename out::template append<T>, out>;
};
-----------------------------------
using list1 = TypeList<char, double, float, long long, int, int,char>;
using Type2 = Fold<list1, TypeList<>, Fun>::type;

Concat:

using list1 = TypeList<char, double, float, long long, int, int,char>;
using Type3 = Concat<TypeList<int, char>, TypeList<double, float>, TypeList<long long, long> >::type;

Filter:

template<typename T>
using gf = std::bool_constant<(sizeof(T) > 4)>;
-----------------------
 using list1 = TypeList<char, double, float, long long, int, int,char>;
 using g = Filter_t<list1, gf>::type;