递归之美 - Loki库TypeList源码剖析

类别:编程语言 点击:0 评论:0 推荐:
 

递归之美 - 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下载)。

本文地址:http://com.8s8s.com/it/it29584.htm