递归之美 － Loki库TypeList源码剖析
邓 辉
TypeList概观
提起List，想必大家都不会陌生，它是一个元素的集合，并且提供了一些对该集合进行操作的方法，比如：计算集合中元素的个数、向集合中添加元素、获取给定索引处的元素等。我们所熟知的List中的元素一般都是实例化后的值，相关的操作也都是在运行期间进行的。本文将要剖析的List和上述的List在某种意义上比较相象，不过它所包含的元素都是类型（type），相关的操作是在编译期间进行的。
本文将要讲述的TypeList取自Andrei Alexandrescu的力作《Modern C++ Design》一书相关的Loki库，关于《Modern C++ Design》，C++的爱好者想必不会陌生，在该书中，作者向我们展现了C++设计的全新思维，把C++的表达能力发挥到了极至，而Loki库正是这种思维的具体表现。TypeLsit是Loki库中最为基础、核心的组件，理解了TypeList就具备了观赏这道C++新景观的基础。
下面我们先来看看如何定义一个TypeList，这样可以对于TypeList先有一个感性的认识。
typedef TYPELIST_3(char, int, long) MyTypeList;
定义了一个具有三个元素的TypeLsit，这三个元素分别为：char、int、long。TYPELIST_3为Loki库中提供的用于定义TypeList的工具，我们会在本文的后面进行介绍。
::Loki::Length<MyTypeList>::value;
计算MyTypeList中元素的个数，结果为3。
typedef ::Loki::TypeAt<MyTypeList, 1>::Result MyType;
获取MyTypeList中第1个元素（从0开始），此时MyType就是int。
typedef ::Loki::Append<MyTypeList, float>::Result MyTypeList1;
向MyTypeList中在添加一个元素：float，结果为MyTypeList1。此时::Length<MyTypeList1>::value等于4。
好了，先介绍这么多，下面我们将介绍TypeList实现的一些相关的背景知识，包括：递归的基本概念、模板的特化（tempalte specilization）、模板的偏特化（template partial specilization）以及类型萃取技术（type traits）。
TypeList相关技术
递归概述
对于递归，大家肯定都不陌生，使用递归方法给出的解决方案总是显得非常的优雅、简洁。不过递归方法所适合解决的问题应该符合下面的条件：
一个问题的解决依赖于一个较小规模的同样的问题的解决
必须有一个明确的结束条件
这个结束条件是可达的
如果一个问题符合上述的三个条件，我们就可以使用递归的方法。首先我们定义一套解决问题的规则，接着缩小问题的规模并应用同样的规则直到达到结束条件，然后结果层层返回直到原始问题。著名的汉诺塔问题就是一个典型的递归问题，如果不使用递归方法，解决汉诺塔问题就会显得非常的复杂，晦涩。
我们在使用递归方法设计程序时，这个递归过程的调用总是在运行期间进行的。本文所介绍的TypeList的实现中，递归的执行是在编译期间进行的，那么在编译期间如何定义每次递归的返回结果，如何定义结束条件呢？其中主要使用了下面将要介绍的模板特化、偏特化以及类型萃取技术。
模板特化和偏特化（template specilizaiton、partial specilization）
什么是模板的特化、偏特化呢？大致的意思为：如果一个template拥有一个或者一个以上的template参数，我们可以针对其中一个或者多个参数进行特化处理（如果全部进行特化处理就是全特化，否则就是偏特化，切记：函数模板只能进行全特化，不能进行部分特化）。也就是说，我们可以提供一个特别版本，符合泛化条件，但是其中某些（全部）template参数已经由实际类型或者数值取代。
假设我们有一个class template定义如下：
template<class U, class V, class T>
class C { … };
对于模板的偏特化，刚刚接触可能会存在一些误解：以为模板的偏特化版本一定是对template参数U或者V或者T（或者它们的任意组合）指定某个参数值。其实不是这样的，所谓模板的偏特化是指另外提供一份template的定义，它的具体含义可以和通用的template定义版本无关。在一个偏特化版本中，template 参数的个数并不需要吻合通用的 template 中的个数。然而，出现於于class 名称之后的参数个数必须吻合通用的 template 的参数个数。下面举一个简单的例子进行说明：
template<class T>
class C { … };
这个泛型版本允许T为任意的类型。它的一个偏特化版本如下：
template<class T>
class C<T*> { … };
这个偏特化版本仅适用于T为原生指针类型的情况。
当我们使用C<int>去定义一个变量时，编译器会自动使用泛型版本，如果使用C<int*>去定义一个变量时，编译器就会自动使用偏特化的版本。有了这个利器，我们就可以解决在编译期间定义递归的结束条件的问题。
类型萃取（type traits）
类型萃取技术是泛型程序设计中的一个常用技术，它的思维核心为：把一系列与类型相关的性质包裹于单一的class 之内，这样我们就可以在编译期间获取一些所需要的和该类型相关的东西。其实这个思路就是软件领域一句著名的谚语：“任何事情都可以通过添加额外的中间层次得以解决”的又一次体现。通过把一系列想得到的类型相关的信息封装在另外一个类型定义中，这样就可以以一致的方式来对这些类型进行处理，提供了强大的可复用性和灵活性。
类型萃取技术一般都和模板的特化、偏特化技术结合在一起运用，这样它们就可以互相补充发挥出巨大的威力。下面简单举一个例子来了解一下类型萃取技术。
我们来看看Boost库中一个简单的template<class T> class is_pointer的实现。我们需要一个主版本，用来处理T不为指针的所有情况，以及一个偏特化版本，用来处理T是指针的情况：
template <class T>
struct is_pointer
{ static const bool value = false; };
template <class T>
struct is_pointer<T*>
{ static const bool value = true; };
一个简单的示例如下：
template<class T>
void Func(T param)
{
if (is_pointer<T>::value) {
// do something
}
else {
//do something
}
…
}
通过类型萃取技术，我们就可以在编译期间保留每次递归的结果，供递归返回时使用。
关于这些技术的更多、更深入的介绍，请读者自行参考相关资料，不在此赘述。在下面的源码剖析中，读者将会看到这些技术的实际运用。
TypeList实现剖析
有了上述的背景知识，下面我们就来揭开TypeList的神秘面纱，走进TypeList的源码世界。首先，我们来看一下TypeList的定义。
TypeList定义
为了能够一致的进行TypeList的操作，在Loki库中定义了一个空类型NullType来标记一个TypeList的结束，NullType和TypeList的定义如下：
class NullType { };
template <class T, class U>
struct Typelist
{
typedef T Head;
typedef U Tail;
};
对于规范型TypeList的定义采用了一种尾递归的方法：
NullType是规范的TypeLsit
如果T是规范的TypeList，那么对于任意原子类型U，TypeList<U，T>是规范的TypeList
Loki库中所采用的TypeList均为规范型的TypeList，这样可以在不减少灵活性的前提下简化对于TypeList的操作。本文后面所指的TypeList均为规范型的。
如何定义一个TypeList呢？比如：包含：char、int、long三个元素的TypeLsit。根据上面的定义，可以得到如下的定义形式：
TypeList<char, TypeLsit<int, TypeLsit<long, NullType> > >; // 注意两个>间一定要加一个空格，不
// 然编译器会认为是 “>>” 操作符
这样的定义方法显得比较麻烦、罗嗦，为了简化用户对于TypeList的使用，Loki库中采用了宏定义的方式对于大小在1～50的TypeList进行了预定义：
#define TYPELIST_1(T1) ::Loki::Typelist<T1, ::Loki::NullType>
#define TYPELIST_2(T1, T2) ::Loki::Typelist<T1, TYPELIST_1(T2) >
#define TYPELIST_3(T1, T2, T3) ::Loki::Typelist<T1, TYPELIST_2(T2, T3) >
…
依此类推。
这样用户在使用起来就会比较方便一些。
TypeList典型操作实现
了解了TypeList的定义，这里我们将对于TypeList相关的三个典型操作（Length、TypeAt和Append）的实现进行详细的剖析。掌握了这几个典型的操作，再学习其他的操作就会变得非常的容易。
我们将通过一个实例进行讲解，来看一下编译器实际的运作过程。我们定义了一个包含两个元素：int以及long的TypeList。
typedef TYPELIST_2(int, long) MyTypeList;
此时，编译器会根据TypeList的定义方式产生如下的类型定义结果：
struct TypeList<long, NullType>
{
typedef long H;
typedef NullType T;
};
struct TypeList<int , TypeList<long, NullType > >
{
typedef int H;
typedef TypeList<long, NullType> T;
};
Length的实现 － 获取TypeList中的元素个数：
template <class TList> struct Length; // 仅有声明，没有实现，如果所传入的类型不是TypeLsit
// 的话，会产生一个编译期错误
template <> struct Length<NullType> // 递归调用的结束条件，NullType的大小为0，运用了
{ // 模板特化和类型萃取技
// 术
enum { value = 0 };
};
template <class T, class U> // 递归的规则定义，运用了模板偏特化和类型萃取技术
struct Length< Typelist<T, U> >
{
enum { value = 1 + Length<U>::value };
};
当通过Length<MyTypeList>::value获得MyTypeList中的元素个数时，看看编译器是如何根据我们指定的规则进行递归调用的。首先编译器会生成如下几个版本的Length定以：
struct Length<TypeList<long, NullType> >
{
enum { value = 1 + Length<NullType>::value };
};
struct Length<TypeList<int, TypeList<long, NullType> > >
{
enum { value = 1 + Length<TypeList<long, NullType> >::value };
};
根据Length结束条件的定义可知，Length<NullType>::value等于0，所以Length<TypeList<long, NullType> >::value就等于Length<NullType>::value+1，也就是1。通过递推可知，Length<MyTypeList>::value也就是Length<TypeList<int, TypeList<long, NullType> > >::value等于Length<TypeList<long, NullType> >::value+1，也就是2。在层层的递推过程中，类型萃取技术得到了充分的体现，value就是我们想要得到的TypeList类型相关的信息，在每一层的递归过程中，都是通过它来保留结果的。
TypeAT的实现 － 获取给定位置处的元素
template <class TList, unsigned int index> struct TypeAt; // 仅有声明，没有实现，如果所传入
// 的类型不是TypeLsit
// 的话，会产生一个编译期错误
template <class Head, class Tail>
struct TypeAt<Typelist<Head, Tail>, 0> // 递归调用的结束条件，如果给定位置为0，则
{ // 返回TypeList中的第一个元素
typedef Head Result;
};
template <class Head, class Tail, unsigned int i> //递归规则定义，注意这里的返回结果为类型，
struct TypeAt<Typelist<Head, Tail>, i> // 运用了类型萃取技术。typename关键字的作
{ // 用是告诉编译器其后的实体是类型。
typedef typename TypeAt<Tail, i - 1>::Result Result;
};
下面看看使用TypeAt<MyTypeList, 1>::Result时，编译器都产生了那些动作。首先编译器要根据递归规则生成如下的类型定义：
struct TypeAt<TypeList<long, NullType> , 0>
{
typedef long Result;
};
struct TypeAt<TypeList<int , TypeList<long, NullType> > , 1>
{
typedef TypeAt<TypeList<long, NullType> , 0>::Result Result;
};
很明显typedef TypeAt<TypeList<long, NullType> , 0>::Result Result; 就是typedef long Result；所以，TypeAt<MyTypeList, 1>::Result就是long类型。同样的，在这个实现中充分使用了类型萃取技术，不过，这里我们想要的不是value，而是Result。
Append的实现 － 在TypeList的末尾添加一个元素
template <class TList, class T> struct Append; // 仅有声明，没有实现，如果所传入
// 的类型不是TypeLsit
// 的话，会产生一个编译期错误
template <> struct Append<NullType, NullType> // 递归结束条件定义，模板的偏特化
{
typedef NullType Result;
};
template <class T> struct Append<NullType, T> //递归结束条件定义，模板的偏特化
{
typedef TYPELIST_1(T) Result;
};
template <class Head, class Tail>
struct Append<NullType, Typelist<Head, Tail> > // 递归结束条件定义，模板的偏特化
{
typedef Typelist<Head, Tail> Result;
};
template <class Head, class Tail, class T> // 递归规则定义，注意这里的返回结果为类型，
struct Append<Typelist<Head, Tail>, T> // 运用了类型萃取技术。typename关键字的作
{ // 用是告诉编译器其后的实体是类型。模板的偏特
// 化
typedef Typelist<Head,
typename Append<Tail, T>::Result>
Result;
};
同样的，让我们来看看当使用Append<MyTypeList, float>::Result时，编译器的递归执行动作。首先看看编译器会生成的一些类型定义：
struct Append<NullType, float>
{
typedef TYPELIST_1(float) Result;
};
struct Append<TypeList<long, NullType> , float>
{
typedef TypeList<long, Append<NullType, float>::Result > Result;
};
struct Append<TypeList<int, TypeList<long, NullType> >, float>
{
typedef TypeList<int, Append<TypeList<long, NullType>,float >::Result > Result;
};
经过简单的替换，Append<MyTypeList, float>::Result就等于：
typedef TypeList<int, Append<TypeList<long, NullType>,float >::Result >;
等于：
typedef TypeList<int, TypeList<long, Append<NullType, float>::Result > >;
等于：
typedef TypeList<int, TypeList<long, TypeList<float, NullType> > >;
也就是：
TYPELIST_3(int, long, float) ；等同于在原有TypeList的末尾添加了一个新元素float。不用多说了，这里类型萃取技术同样发挥了巨大的作用。
结束语
本文对于TypeLsit的实现进行了剖析，相信读者朋友对于TypeList含义以及实现手法已经有所掌握。那么TypeLsit到底有什么用处呢？源码面前，了无秘密，掌握了TypeList，就掌握了全面理解Loki库的钥匙。在Loki库中，你将会看到Abstract Factory模式、Visitor模式这些泛型组件是如何在TypeLsit的基础上搭建起来的。背起你的行囊，拿起这把钥匙，赶快踏上你的“寻宝”之路吧（Loki库的源代码可以从www.moderncppdesign.com下载）。
