使用模板元编程操作类型集合(C++11下的TypeList)

群里有个朋友要实现这么一个功能:如何在编译期把一个函数类型的参数减少一个。
简单来说,就是实现下面这个模板:

remove_func_par<2, void(int, long, short)>::type; // type = void(int, long)

根据输入的编译期整数,把函数参数表里对应的参数干掉一个。
为了实现这种功能,我们需要操作变参模板的参数包。比如像这样:

// make function's parameters from the types
 
template <typename R, typename TypesT>
struct make_func_par;
 
template <typename R, typename... P>
struct make_func_par<R, types<P...>>
{
    typedef R type(P...);
};
 
// remove function's parameter
 
template <size_t N, typename F>
struct remove_func_par;
 
template <size_t N, typename R, typename... P>
struct remove_func_par<N, R(P...)>
{
    using erase_pars_t = typename types_erase<types<P...>, N>::type;
    using type = typename make_func_par<R, erase_pars_t>::type type;
};

上面这段代码的思想很简单,把模板参数包的第N个参数删掉,然后再将它重新展开成函数的参数表。而types的定义可以非常简单:

template <typename...>
struct types {};

如果定义了一组对types类型做操作的算法,那么我们就可以把参数包放入types中,然后对它做这样那样的事情。。

看到这里,不知道有没有朋友想起来很久很久以前,Loki库里的TypeList。现代的C++当然不需要再像当年那样用外敷类和繁琐的宏来实现这个,使用变参模板加模板元就好了。

一、types的判断和大小计算

有了上面types的定义之后,下面需要实现一些算法来操作它。首先,在不涉及到容器的查找修改时,最基本的算法简单来说有下面几个:判断容器类型(因为容器是编译期的一个类型)、计算容器大小、判断容器是否是空的。下面我们来依次实现它们。

判断算法非常简单:

/*
    Is types
*/
 
template <typename TypesT>
struct is_types
     : std::false_type
{};
 
template <typename... T>
struct is_types<types<T...>>
     : std::true_type
{};

有了判断的算法之后,对于后面的运算就可以在编译时判断出传入的类型是否符合要求。我们可以定义一个专门用来判断类型合法性的模板:

// Check is types or not
 
template <typename TypesT>
struct check_is_types
{
    static_assert(is_types<TypesT>::value, "The template parameter is not a types-list!");
};

在需要的时候,继承check_is_types就好了。
接下来,是计算types的大小。在有了变参模板,以及针对模板参数包的sizeof运算符以后,这个工作也是非常简单的:

/*
    Return size
*/
 
template <typename TypesT>
struct types_size : std::integral_constant<int, 0>
                  , check_is_types<TypesT>
{};
 
template <typename... T>
struct types_size<types<T...>>
     : std::integral_constant<int, sizeof...(T)>
{};

通过继承check_is_types,types_size在传入参数不是一个types的时候,会在编译时报出错误提示。
有了计算types大小的工具,我们可以为后面的算法再准备两个编译时合法性判断的辅助类:

// Check is index valid or not
 
template <typename TypesT, int IndexN>
struct check_is_index_valid
{
    static_assert(IndexN >= 0,                        "Index is out of range!");
    static_assert(IndexN < types_size<TypesT>::value, "Index is out of range!");
};
 
// Check is count valid or not
 
template <typename TypesT, int CountN>
struct check_is_count_valid
{
    static_assert(CountN > 0,                          "Count is too small!");
    static_assert(CountN <= types_size<TypesT>::value, "Count is too large!");
};

check_is_index_valid用来判断传入的索引是否超出了指定types的范围;
check_is_count_valid用来判断传入的大小是否超出了指定types的大小。
和check_is_types一样,在需要的时候继承这两个类模板就可以了。

然后,是容器是否为空的判断:

/*
    Test whether types is empty
*/
 
template <typename TypesT>
struct types_empty : std::true_type
                   , check_is_types<TypesT>
{};
 
template <typename... T>
struct types_empty<types<T...>>
     : std::false_type
{};
 
template <>
struct types_empty<types<>>
     : std::true_type
{};

二、types的元素访问

types的访问算法就是根据传入的索引(index)定位类型。我们可以先写下types_at的定义:

template <typename TypesT, int IndexN>
struct types_at : check_is_index_valid<TypesT, IndexN>
{
    using type = TypesT;
};

接下来,是思考如何通过模板元的递归定位元素了。在数学里,最基本的定位方法就是数个数(是的,你没听错,就是数数)。模板元在递归的时候,每次可以去掉参数包中开头的第一个参数,同时我们让传入的index减1。当index为0的时候,对应的参数类型就是我们需要的类型了。算法实现可以像这样:

template <typename T1, typename... T, int N>
struct types_at<types<T1, T...>, N>
     : types_at<types<T...>, N - 1>
{};
 
template <typename T1, typename... T>
struct types_at<types<T1, T...>, 0>
{
    using type = T1;
};

上面的第一个types_at特化负责把参数包和index同时减1,并传入下一层;最后模板的递归会在第二个types_at特化处终结。
我们看到,这里并不需要一个types<>的特化。因为当传入的模板参数是types<>的时候,它不会匹配到任何一个特化,因此最初的types_at定义就可以搞定这种情况了。

有了types_at之后,我们可以很方便的实现front和back的定位算法:

/*
    Access first element
*/
 
template <typename TypesT>
struct types_front
{
    using type = types_at_t<TypesT, 0>;
};
 
/*
    Access last element
*/
 
template <typename TypesT>
struct types_back
{
    using type = types_at_t<TypesT, types_size<TypesT>::value - 1>;
};

三、types的连接(Link)和分配(Assign)

这两个算法都是用来把类型打包成types的。

首先我们来考虑类型的连接。需求很简单,传入两个类型,把它们连接成一个types。
当参数是普通类型时的算法很简单:

template <typename T, typename U>
struct types_link
{
    using type = types<T, U>;
};

当两个类型都是普通类型时,算法是显然的。那么当其中一个类型是一个types时,另一个类型应该被追加到那个types的尾部或头部:

template <typename... T, typename U>
struct types_link<types<T...>, U>
{
    using type = types<T..., U>;
};
 
template <typename T, typename... U>
struct types_link<T, types<U...>>
{
    using type = types<T, U...>;
};

假如两个类型都是types类型,那么需要把它们连接成一个types:

template <typename... T, typename... U>
struct types_link<types<T...>, types<U...>>
{
    using type = types<T..., U...>;
};

我们注意到,上面的link算法里考虑了当参数是types的情况。因此在做后面的其它算法时,通过使用这里的link,会把types内部的types展开。

下面是types的Assign算法。需求是,传入一个数字N和类型T,types_assign将构造一个由N个T组成的types。
有了上面的types_link以后,我们可以在模板递归中一次连接一个T,直到N减少到0为止。算法如下:

template <int N, typename T>
struct types_assign
{
    static_assert(N >= 0, "N cannot be less than 0!");
private:
    using tail = typename types_assign<N - 1, T>::type;
public:
    using type = typename types_link<T, tail>::type;
};
 
template <typename T>
struct types_assign<0, T>
{
    using type = types<>;
};

由于使用了types_link连接types,当我们这样写时:types_assign<2, types<int, long>>::type,将会得到:types<int, long, int, long>。

四、types的插入和删除

插入算法的需求如下:
给定一个types,传入索引index和类型T,需要把T插入到types的index处。根据这个需求,我们可以先写出types_insert的定义:

template <typename TypesT, int IndexN, typename T>
struct types_insert : check_is_types<TypesT>
                    , check_is_index_valid<TypesT, IndexN>
{
    using type = TypesT;
};

接下来考虑算法。插入算法其实只比数数多了一个步骤,那就是在数到需要的位置后,把T插到那个位置。那么我们可以先写上数数的算法:

template <typename T1, typename... T, int N, typename U>
struct types_insert<types<T1, T...>, N, U>
{
private:
    using tail = typename types_insert<types<T...>, N - 1, U>::type;
public:
    using type = typename types_link<T1, tail>::type;
};

每次递归,都将数出一个参数,并把剩下的继续向下传递。当所有的递归完成后,下一层的types_insert将返回一个已插入完毕的types,那么把这个types当做结尾,和T1连接在一起就好了。
关键的插入将在递归终结的时候完成:

template <typename T1, typename... T, typename U>
struct types_insert<types<T1, T...>, 0, U>
{
    using type = typename types_link<U, types<T1, T...>>::type;
};

待插入的类型U,被插入到types的索引0处,也就是最开始的位置。
这里需要特殊考虑一下types<>:

template <typename U>
struct types_insert<types<>, 0, U>
{
    using type = typename types_link<U, types<>>::type;
};


因为若不添加这个特化的话,types<>会被匹配到types_insert的定义上去,那么types<>将无法插入任何类型了。
可能有童鞋看到这里,觉得我们没必要把types<T1, T...>和types<>的特化分开写,直接这样就好了:

template <typename... T, typename U>
struct types_insert<types<T...>, 0, U>
{
    using type = typename types_link<U, types<T...>>::type;
};

看起来好像没问题,但实际上是不行的。这是因为<types<T...>, 0, U>和<types<T1, T...>, N, U>之间存在二义性。当模板递归到最后一层时,N将为0,此时若types大小大于1,这两个特化都可以被匹配到。
而<types<T1, T...>, 0, U>和<types<T1, T...>, N, U>之间则没有二义性。因为前面的特化版本是后面一个的特殊情况。

这里也说明了模板元编程时书写的一个原则:应该从最普遍的特化版本开始,逐一特殊化各种条件,直到最后的递归终结。
这种书写方法可以保证不会出现模板特化的二义性,只是和数学归纳法的思考方向相反。如果习惯于用数学归纳法之类的方式思考模板元递归算法的童鞋,可以先正着写出算法,再倒着看每个条件是否是逐步特殊化的。

下面我们思考删除算法。需求:
给定一个types,传入索引index和数量count,需要把types中从索引index处开始的count个元素删除。
首先,我们还是先写出定义:

template <typename TypesT, int IndexN, int CountN = 1>
struct types_erase : check_is_types<TypesT>
                   , check_is_index_valid<TypesT, IndexN>
{
    using type = TypesT;
};

同样的,删除算法也是在数到指定索引位置之后,将后面的元素删除掉。我们可以把count的需求放在一遍,先定位到需要删除的位置:

template <typename T1, typename... T, int N, int C>
struct types_erase<types<T1, T...>, N, C>
{
private:
    using tail = typename types_erase<types<T...>, N - 1, C>::type;
public:
    using type = typename types_link<T1, tail>::type;
};

和上面的插入一样,types_erase在递归后将返回一个处理完毕的types,之后把它和T1连起来就好了。
那么,当找到需要删除的索引时,我们自然是删掉它了。为了思考的简单,我们可以先考虑删除一个元素的算法:

template <typename T1, typename... T>
struct types_erase<types<T1, T...>, 0, 1>
{
    using type = types<T...>;
};

当数到需要删除的位置时,N一定是等于0的。这个时候若count为1,那么只需要去掉开头的T1就可以了。那么连续删除count个元素就可以这样写:

template <typename T1, typename... T, int C>
struct types_erase<types<T1, T...>, 0, C>
     : check_is_count_valid<types<T1, T...>, C>
{
    using type = typename types_erase<types<T...>, 0, C - 1>::type;
};

当count不为1时,删除开头的T1,将count减1后继续向下递归。当count为1后,将匹配到前一个模板。由于这里的count可能超出types的界限,因此需要用check_is_count_valid来检查count的有效性。
现在,我们回过头来检查一下,模板的特化条件是否是逐渐收窄的:

<types<T1, T...>, N, C>
<types<T1, T...>, 0, C>
<types<T1, T...>, 0, 1>

那么是否所有的情况都考虑到了呢?通过枚举出所有的特化条件,我们发现只有types<>没有考虑。对于types_erase来说,types<>没有删除的意义,因此直接让它匹配到types_erase的定义就可以了。当然,这会引起一个编译期的static_assert,因为任何的index都将超出types<>的范围。

五、types的查找,以及其它算法

查找算法的需求如下:
给定一个types和类型T,需要在types中找到T所在的第一个索引位置。
首先,我们先写出定义:

template <typename TypesT, typename T>
struct types_find : std::integral_constant<int, -1>
                  , check_is_types<TypesT>
{};

接着,我们用数学归纳法的方式来思考:
当types中的第一个元素为T时,索引位置为0;(终结条件)
当types中的第N个元素为T时,索引位置为上一个元素的索引加1。

那么我们可以先列出需要特化的版本:

<types<T1, T...>, T1>
<types<T1, T...>, U>

接下来,先特化终结条件:

template <typename T1, typename... T>
struct types_find<types<T1, T...>, T1>
     : std::integral_constant<int, 0>
{};

然后思考一般情况:索引位置为上一个元素的索引加1,说明我们需要做一个加法。而find的结果有两种:找到了,和没找到。当没找到的时候,模板最终会匹配到types_find的定义上去。而我们在定义里给出的value是-1。因此在做加法运算时,需要把-1的情况忽略掉:

template <typename T1, typename... T, typename U>
struct types_find<types<T1, T...>, U>
     : std::integral_constant<int, 
                             (types_find<types<T...>, U>::value == -1 ? -1 :
                              types_find<types<T...>, U>::value + 1)>
{};

有了查找算法以后,判断types中是否存在某个类型就非常简单了:

template <typename TypesT, typename T>
struct types_exist
     : std::integral_constant<bool, (types_find<TypesT, T>::value != -1)>
{};

接下来,让我们思考一个一般化的算法:
逐个遍历给定types中的元素,当该元素满足某个条件时,对这个元素做某件事情。
我们可以把定义写成下面这样:

template <typename TypesT,
template <typename, typename> class If_, typename V,
template <bool, typename, typename> class Do_, typename U>
struct types_do_if : check_is_types<TypesT>
{
    using type = TypesT;
};

If_用来把types中的某个类型T1,和给定的V做判断;Do_将接受If_的判断结果,对T1和U一起做某件事(比如置换)。
上面这句话说出来可能有点绕口,实际上写成代码并不复杂:

using done = typename Do_<If_<T1, V>::value, U, T1>::type;

我们从这里可以得到处理后的结果类型done。那么一般化的算法就是把done和剩下的(T1以外的)元素连起来。需要注意的是,处理是递归的,因此最后写出来应该是这个样子:

template <typename T1, typename... T,
template <typename, typename> class If_, typename V,
template <bool, typename, typename> class Do_, typename U>
struct types_do_if<types<T1, T...>, If_, V, Do_, U>
{
private:
    using tail = typename types_do_if<types<T...>, If_, V, Do_, U>::type;
    using done = typename Do_<If_<T1, V>::value, U, T1>::type;
public:
    using type = typename types_link<done, tail>::type;
};

费这么大劲写这个一般化的算法有什么用呢?下面我们来看看它的威力。

首先,是types的置换算法:
给定一个types,以及类型T,U;要求把所有types中的T都换成U。
有了上面的types_do_if,实现这个算法非常轻松:

template <typename TypesT, typename T, typename U>
struct types_replace
     : types_do_if<TypesT, std::is_same, T, std::conditional, U>
{};

当在types中找到类型T的时候,就把它变成U。代码和语言描述基本是一致的。

接下来,考虑一个移除的算法:
给定一个types,和类型T,要求从types中移除所有的T。
通过types_do_if实现如下:

template <typename TypesT, typename T>
struct types_remove
     : types_do_if<TypesT, std::is_same, T, std::conditional, types<>>
{};

我们可以看到,上面std::conditional后面的类型是types<>。原因是types_do_if里使用types_link连接结果。那么直接给定一个空的types,它和类型U连接后的结果仍然是U。
看到这里,我们其实可以写得更简单点:

template <typename TypesT, typename T>
struct types_remove
     : types_replace<TypesT, T, types<>>
{};

使用types<>置换掉types里的T,结果和移除是一样的。
这里再思考一步:如果需要移除的类型T本身,也是一个types列表,那么我们可以批量移除掉多个类型。实现算法其实很简单:

template <typename TypesT, typename U1, typename... U>
struct types_remove<TypesT, types<U1, U...>>
{
private:
    using rm_t = typename types_remove<TypesT, U1>::type;
public:
    using type = typename types_remove<rm_t, types<U...>>::type;
};

从types<U1, U...>中取出一个元素做types_remove,把结果和剩下的types<U...>放到递归里就可以了。

通过types_do_if还可以实现很多特殊操作,在这里就不再展开了。
接下来,我们实现types的“压缩”算法。当types里有多个重复元素的时候,如何把重复的内容剔除掉,只保留一个呢?
同样的,我们先写出定义:

template <typename TypesT>
struct types_compact : check_is_types<TypesT>
{
    using type = TypesT;
};

如何判断内容有重复?其实很简单,当我们从types中取出一个元素T1,那么剩下的内容里,所有的T1都将是重复的,删掉就可以了。
算法写出来就是这样:

template <typename T1, typename... T>
struct types_compact<types<T1, T...>>
{
private:
    using rm_t = typename types_remove<types<T...>, T1>::type;
    using tail = typename types_compact<rm_t>::type;
public:
    using type = typename types_link<T1, tail>::type;
};

最后,一个特殊且有用的算法是倒序(reverse),即把types中的元素倒过来。实现如下:

template <class TypesT>
struct types_reverse : check_is_types<TypesT>
{
    using type = TypesT;
};
 
template <typename T1, typename... T>
struct types_reverse<types<T1, T...>>
{
private:
    using head = typename types_reverse<types<T...>>::type;
public:
    using type = typename types_link<head, T1>::type;
};

每次取出第一个元素,然后把它放到最后面即可。

六、types的排序

在编译期排序和运行期其实并没什么不同,只是算法的选择上需要考虑一下。假设是从大到小排列,那么最直观的想法是每次递归都从types中找到最大的元素,然后把它放到头上去。这样递归完毕后整个types就是有序的了。
这种想法其实就是选择排序(Selection sort)。
当然,我们也可以实现插入,或者快排。如果读者感兴趣的话,可以自己实现一下。

使用选择排序,首先需要能从types中找到放在最前面的那个元素。在这里我们不使用现成的比较算法,而写成可以让外部指定比较算法。那么select的算法定义如下:

template <typename TypesT,
template <typename, typename> class If_>
struct types_select_if : check_is_types<TypesT>
{
    using type = TypesT;
};

我们先用数学归纳法思考下算法:
当types中只有1个元素T1时,直接返回T1;(终结条件)
当types中有1个元素以上时,先得到T1以外的其它元素的select结果(S),然后将T1和S一起放入If_中。若If_为true,那么选择T1,否则选择S。

同样,先列出特化条件:

<types<T1>, If_>
<types<T1, T...>, If_>

然后是它们的实现:

template <typename T1,
template <typename, typename> class If_>
struct types_select_if<types<T1>, If_>
{
    using type = T1;
};
 
template <typename T1, typename... T,
template <typename, typename> class If_>
struct types_select_if<types<T1, T...>, If_>
{
private:
    using select_t = typename types_select_if<types<T...>, If_>::type;
public:
    using type = typename std::conditional<If_<T1, select_t>::value, T1, select_t>::type;
};

可以看到,代码和前面归纳法的描述是一致的。
接下来,是排序的实现。首先是定义:

template <class TypesT,
template <typename, typename> class If_>
struct types_sort_if : check_is_types<TypesT>
{
    using type = TypesT;
};

和上面一样,先用数学归纳法思考下:
当types中只有1个元素T1时,直接返回types<T1>;(终结条件)
当types中有1个元素以上时,先得到types的select结果(S),之后从types中删除S,然后对结果递归运算,最后把S连接到头部。

列出特化条件:

<types<T1>, If_>
<types<T1, T...>, If_>

最后是实现:

template <typename T1,
template <typename, typename> class If_>
struct types_sort_if<types<T1>, If_>
{
    using type = types<T1>;
};
 
template <typename T1, typename... T,
template <typename, typename> class If_>
struct types_sort_if<types<T1, T...>, If_>
{
private:
    using types_t = types<T1, T...>;
    using sl_t = typename types_select_if<types_t, If_>::type;
    using er_t = typename types_erase<types_t, types_find<types_t, sl_t>::value>::type;
    using tail = typename types_sort_if<er_t, If_>::type;
public:
    using type = typename types_link<sl_t, tail>::type;
};

我们来看看排序的效果:

using types_t = types<short, int, unsigned char, long long, float&, const double, long*>;
 
template <typename T, typename U>
struct is_large
     : std::integral_constant<bool, (sizeof(T) > sizeof(U))>
{};
 
using sort_t = types_sort_if<types_t, is_large>::type;
// sort_t = types<double const, long long, long*, float&, int, short, unsigned char>

尾声

实际项目中,我们往往不会像这样写这么多模板元的代码。如果有类似需求,可能会考虑直接使用Boost.MPL,或者在Loki.TypeList的基础上加一层变参模板的外敷。

自己完整的实现一次模板元的容器操作算法的意义,在于可以大大加深对模板元编程,以及对变参模板的理解。
有了这些经验之后,在不方便使用第三方库时,能够快速自撸一些简单且可靠的模板元算法,来完成一些编译期计算的需求;同时也可以帮助我们更清晰的理解和分析一些C++模板库(STL、Boost之类)里的泛型算法。

另外,目前的std::tuple的实现方式其实是类似上面的types的。比如gnuc的libstdc++里的定义:

// Forward declarations.
template<typename...>
class tuple;

而目前stl里对std::tuple的编译期操作很简单,只有std::tuple_size和std::tuple_element两种。如果想增加std::tuple的编译期运算功能,也可以自行采用上面类似的算法做拓展。


完整代码及测试下载请点击:types

使用模板元编程操作类型集合(C++11下的TypeList),布布扣,bubuko.com

使用模板元编程操作类型集合(C++11下的TypeList)

上一篇:Effective c++(笔记) 之 类与函数的设计声明中常遇到的问题


下一篇:ztree使用系列三(ztree与springmvc+spring+mybatis整合实现增删改查)