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

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

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

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

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

一、types的判断和大小计算

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

判断算法非常简单：

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

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

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

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

然后，是容器是否为空的判断：

二、types的元素访问

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

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

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

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

三、types的连接（Link）和分配（Assign）

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

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

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

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

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

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

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

四、types的插入和删除

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

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

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

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

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

看起来好像没问题，但实际上是不行的。这是因为<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个元素删除。
首先，我们还是先写出定义：

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

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

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

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

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

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

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

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

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

接下来，先特化终结条件：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最后，一个特殊且有用的算法是倒序（reverse），即把types中的元素倒过来。实现如下：

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

六、types的排序

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

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

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

同样，先列出特化条件：

然后是它们的实现：

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

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

列出特化条件：

最后是实现：

我们来看看排序的效果：

尾声

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

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

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

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

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