关于模板偏特化，模板递归，及Loki之Typelist和一些感悟

一直以来，在大多数情况下，递归被看做是低效率的表现，从学习编程开始，就一直被教导，不用或至少少用递归。但在模板编程中，递归和模板偏特化联合，起了相当大的作用。可以说，没有递归，在很大程度上，模板编程便无从谈起。给我感觉是，在模板编程中，递归是唯一有效的手段……

一个很简单的例子如下：

template <unsigned long N>struct binary{ static unsigned const value = binary<N/10>::value*2 + N%10;};template < >struct binary<0>{ static unsigned const value = 0;};

该例子在编译期将无符号的十进制数字转换为等价的二进制数字。第一个template是递归主体，第二个template是递归的边界条件。从模板技术的角度来看，第二个是对一个模板的特化。在任一次迭代中，两个模板并不会同时被进行，编译器会根据当前条件选择最合适的一个模板。对编译器来说，这里并不存在什么递归之类，编译器所看到的只是：一个模板需要被实例化，而实例化之后，编译器又看到一个模板需要被实例化……于是有了递归。

可以想象一下，其实我们所需要的不过是最后的那一串二进制数字，但为了在“编译期”得到这数字，编译器额外的产生了很多以后永远不会用到的模板实例。从某一角度讲，我很质疑递归在模板编程的大量使用是否得当……

话题远了些。

 

最近看Loki库，和《C++设计新思维》。Loki中，对模板的运用有点让人晕眩的感觉。Loki中大量使用了模板偏特化，模板递归。这在Typelist中表现尤为突出。

Typelist本身只是一个关于型别的List而已，虽然自身的用处并没有我想象中的大，但Typelist几乎构成了整个Loki的基础。对Type的使用能到这个程度，我觉得完全登峰造极了。

 

Loki中，对Typelist的定义如下：

/* define keyword */#define typelisttypename/* NullType */struct NullType;/* decal of Typelist */template < typename _fir_type, typename _snd_type >struct Typelist{typedef_fir_typeHead;typedef_snd_typeTail;};/* define a serial of typelist */#defineTYPELIST_1(type1)Typelist< type1, NullType >#defineTYPELIST_2(type1,type2)Typelist< type1, TYPELIST_1(type2) >#defineTYPELIST_3(type1,type2,type3)Typelist< type1, TYPELIST_2(type2,type3) >#defineTYPELIST_4(type1,type2,type3,type4)Typelist< type1, TYPELIST_3(type2,type3,type4) >// ....../* example : define of concrete typelist */typedef TYPELIST_3( char, signed char, unsigned char )CharList;typedef TYPELIST_4( signed char, short int, int, long int )SignedIntegrals;/* there can be more */

说得更确切点，这是我自己的定义。在Loki中，并没有：

#define typelisttypename

而我个人觉得，如果一个template的形参中全是typename T，或者class T，不免有点让人混乱。但如果定义一个typelist关键字，用以在某些适当的地方取代typename 或者class，那样的话会更醒目。

例如：

/* search in typelist */// search _type in _listtemplate < typelist _list, typename _type >struct IndexOf;

IndexOf，在typelist中搜索某type，其第一个参数是一个typelist，第二个参数是一个type，用所定义的关键字typelist取代typename ，来更清晰的表达IndexOf的语义。

不过使用#define来定义typelist，其实不太好的，没有想到更好的办法。typename并不是一个type，不能使用typedef。

 

这让我想到不久前，我看到C#中有这样的代码：（原谅我还没来得及学习C#……）

（http://blog.zhaojie.me/2010/06/more-why-java-sucks-and-csharp-rocks-1-reddit-and-property.html）

// C#users.Sort(u => u.Age);

该代码表示：“有一个User数组，我们要根据它的年龄进行排序”……无疑这样的表达更体现出了程序员的用意，即是体现了what而不是how。而在C++中，我们应该怎么写？我们可以写个方法，可以重载一个操作符，可以……而所有这些（至少是我所能想到的），都没有C#的这一句更能表达程序员的意图。

于是我想，是不是可以在C++自己创建一个运算符，比如=>来与C#类似的完成任务。答案是否定的，C++中不能新建运算符，其实好像缩语的语言都不能，但还是感到有些遗憾。比如也许我能将>>符号重载写出：users>>u.Age这样的代码，但怎么都觉得很奇怪……

语言都有语言的缺陷。C++总让我觉得是一门超大巨炮，什么都可以搞定。但在使用这门巨炮之前，得为这门巨炮铺一公里的代码……其实我本想完成的事情不过是排个序或者复制个数据罢了……

但用惯C++后，用其他什么都觉得很奇怪。比如我学python时，发现没有指针，没有typedef，我觉得相当不可思议……

 

说远了。再回来。

关于所#define 的TYPELIST_1，在Loki中一直写到了TYPELIST_50。用户在外部可以使用TYPELIST_50（...）来定义自己的一个有50个型别的typelist，但这样似乎暴露了我们内部的实现……（但在模板中，什么不是暴露的呢……），是不是有办法给出一个统一的接口，用户定义自己的typelist时可以不用写出TYPELIST_50这样神奇的代码，而只用给出他要typelist的型别即可。

Loki中有MakeTypelist，如下：

 

////////////////////////////////////////////////////////////////////////////////// class template MakeTypelist// Takes a number of arguments equal to its numeric suffix// The arguments are type names.// MakeTypelist<T1, T2, ...>::Result// returns a typelist that is of T1, T2, ...//////////////////////////////////////////////////////////////////////////////// template < typename T1 = NullType, typename T2 = NullType, typename T3 = NullType, typename T4 = NullType, typename T5 = NullType, typename T6 = NullType, typename T7 = NullType, typename T8 = NullType, typename T9 = NullType, typename T10 = NullType, typename T11 = NullType, typename T12 = NullType, typename T13 = NullType, typename T14 = NullType, typename T15 = NullType, typename T16 = NullType, typename T17 = NullType, typename T18 = NullType > struct MakeTypelist { private: typedef typename MakeTypelist < T2 , T3 , T4 , T5 , T6 , T7 , T8 , T9 , T10, T11, T12, T13, T14, T15, T16, T17, T18 > ::Result TailResult; public: typedef Typelist<T1, TailResult> Result; }; template<> struct MakeTypelist < NullType, NullType, NullType, NullType, NullType, NullType, NullType, NullType, NullType, NullType, NullType, NullType, NullType, NullType, NullType, NullType, NullType, NullType >{ typedef NullType Result; };

 

用户定义用：MakeTypelist<T1, T2, ...>::Result。看起来很复杂，其实是：递归+偏特化。第一个template在递归，而第二个是以偏特化的形式作为递归的终结条件的。最终当18个type都是NullType时，停止递归，也就完成了定义Typelist的任务。

不太明白的是，为什么只有18个Type?难道作者只允许定义18个？

在网上有看到另一种形式的MakeTypelist，是定义了一个50个Type的list，并使用即将介绍到的EraseAll来删除除最后一个NullType之外的其他NullType。不过觉得在Typelist这个递归+偏特化的场所显得不太合事宜……

 

接下来就是一系列的只在编译期进行call的模板函数。几乎全是递归+偏特化的机制：

 

/* Length of typelist */template < typelist _list >struct Length;template < > struct Length< NullType >{enum { value = 0 };};template < typename _fir, typename _snd >struct Length < Typelist< _fir, _snd > >{enum { value = 1 + Length< _snd >::value };};/* Index of Typelist */// must be declared as thistemplate < typelist _list, unsigned int index >struct TypeAt;template < typename Head, typename Tail >struct TypeAt< Typelist< Head, Tail >, 0 >{typedef HeadResult;};template < typename Head, typename Tail, unsigned int index >struct TypeAt< Typelist< Head, Tail >, index >{typedef typename TypeAt< Tail, index-1 >::ResultResult;};/* search in typelist */// search _type in _listtemplate < typelist _list, typename _type >struct IndexOf;// if the list is NullType, then the index is -1// that means there is no _type in the _listtemplate < typename _type >struct IndexOf< NullType, _type >{enum { index = -1 };};// if the head of _list is _type(what we are search for)// then the index is 0// that means we found _type just heretemplate < typename Tail, typename _type >struct IndexOf< Typelist< _type, Tail >, _type >{enum { index = 0 };};// the main processtemplate < typename Head, typename Tail, typename _type >struct IndexOf< Typelist< Head, Tail >, _type >{private:enum { temp = IndexOf< Tail, _type >::index };public:enum { index = (temp == -1)? (-1) : (temp+1) };};/* append: */// _type may be a typelist or typenametemplate < typelist _list, typename _type >struct Append;// when typelist and _type are both nulltemplate < >structAppend < NullType, NullType >{typedef NullTypeResultList;};// when the typelist is null but _type is non nulltemplate < typename _type >structAppend < NullType, _type >{typedef TYPELIST_1(_type)ResultList;};// if the _type is a typelist and the typelist is nulltemplate < typename Head, typename Tail >structAppend < NullType, Typelist< Head, Tail > >{typedef Typelist< Head, Tail >ResultList;};// elsetemplate < typename Head, typename Tail, typename _type >structAppend < Typelist< Head, Tail >, _type >{typedef Typelist< Head, Append< Tail, _type > >ResultList;};/* remove *//// remove the first of _typetemplate < typelist _list, typename _type >struct Erase;// when they are nulltemplate < typename _type >structErase < NullType, _type >{typedef NullTypeResultList;};// when _type is the headtemplate < typename Tail, typename _type >structErase < Typelist<_type, Tail>, _type >{typedef TailResultList;};// elsetemplate < typename Head, typename Tail, typename _type >structErase < Typelist<Head, Tail>, _type >{typedef Typelist< Head, typelist Erase<Tail, _type>::ResultList >ResultList;};/// remove all _type in typelisttemplate < typelist _list, typename _type >struct EraseAll;template < typename _type >structEraseAll < NullType, _type >{typedef NullTypeResultList;};template < typename Tail, typename _type >structEraseAll < Typelist<_type, Tail>, _type >{typedef typelist Erase<Tail, _type>::ResultListResultList;};template < typename Head, typename Tail, typename _type >structEraseAll < Typelist<Head, Tail>, _type >{typedef Typelist< Head, typelist EraseAll<Tail, _type>::ResultList >ResultList;};/* remove the duplicates */template < typelist _list >struct DoDuplicates;// nulltemplate < >struct DoDuplicates < NullType >{typedef NullTypeResultList;};// main process// this is a very interesting functemplate < typename Head, typename Tail >struct DoDuplicates < Typelist<Head,Tail> >{private:typedef typelist DoDuplicates< Tail >::ResultList_list_1;// in the tail(maybe a list), erase head(must be a _type anytime)typedef typelist Erase< _list_1, Head >::ResultList_list_2;public:typedef Typelist< Head, _list_2 >ResultList;};/* replace *//// replace signedtemplate < typelist _list, typename _replaced_type, typename _replace_type >structReplace;// nulltemplate < typename _replaced_type, typename _replace_type >structReplace < NullType, _replaced_type, _replace_type >{typedef NullTypeResultList;};template < typename Tail, typename _replaced_type, typename _replace_type >structReplace < Typelist< _replaced_type,Tail >, _replaced_type, _replace_type >{typedef Typelist< _replace_type, Tail >ResultList;};template < typename Head,typename Tail,typename _replaced_type,typename _replace_type >structReplace < Typelist< Head, Tail >, _replaced_type, _replace_type >{typedefTypelist< Head, typelist Replace< Tail, _replaced_type, _replace_type >::ResultList >ResultList;};/// replace alltemplate < typelist _list, typename _replaced_type, typename _replace_type >structReplaceAll;// nulltemplate < typename _replaced_type, typename _replace_type >structReplaceAll < NullType, _replaced_type, _replace_type >{typedef NullTypeResultList;};template < typename Tail, typename _replaced_type, typename _replace_type >structReplaceAll < Typelist< _replaced_type,Tail >, _replaced_type, _replace_type >{// typedef Typelist< _replace_type, Tail >ResultList;typedef Typelist< _replace_type, typelist ReplaceAll< Tail, _replaced_type, _replace_type >::ResultList >ResultList;};template < typename Head,typename Tail,typename _replaced_type,typename _replace_type >structReplaceAll < Typelist< Head, Tail >, _replaced_type, _replace_type >{typedefTypelist< Head, typelist ReplaceAll< Tail, _replaced_type, _replace_type >::ResultList >ResultList;};

本没有什么话说的。但在实际的Coding中，出了不少问题。template<...>中是参数，在其下的struct或函数中出现的参数必须出现在template的参数列表中。

 

想说一下的是模板片特化；我的理解是，模板偏特化即是显式地给出模板的参数，使之仅对某种情况适用。例如：

/* remove *//// remove the first of _typetemplate < typelist _list, typename _type >struct Erase;// when they are nulltemplate < typename _type >structErase < NullType, _type >{typedef NullTypeResultList;};

其中，struct Erase < NullType, _type >即是显式得给出typelist _list为NullType，从而实现偏特化。当编译器在进行模板实例化时，就会从所有的目标中（包括泛化和偏特化版本），选取最合适的那一个进行实例化。

泛化版本和偏特化版本在模板实例化中扮演的角色可以看做是：泛化是递归体，偏特化是边界条件（即是非递归体，一个确定体）

 

所有这上边的，都是对型别进行操作。所作的基本是基础性的工作。下面要说的是，用所有这上边的，来做点实际能有点作用的，实际可以在运行期留下足迹的东西。

 

进行class的模板级Create操作：

/*------------------------------------*//*------------- To Create Class-------*//*------------------------------------*/// must be template <class>template< typelist _list, template <typename> class Unit >classGenScatterHierarchy;// do nothing for null typetemplate < template <typename> class Unit >classGenScatterHierarchy < NullType, Unit >{};// atomic typetemplate < typename AtomicType, template <typename> class Unit >classGenScatterHierarchy : public Unit< AtomicType >{};// typelist to unit// _type_1,_type_2 mustn't be type, maybe typelisttemplate < typename _type_1, typename _type_2, template< typename > class Unit >classGenScatterHierarchy < Typelist <_type_1, _type_2>, Unit >: publicGenScatterHierarchy< _type_1, Unit >, publicGenScatterHierarchy< _type_2, Unit >{};

 

Class产生在编译期，可能被运行期使用。产生的方式是通过继承，和对继承的实例化。这实际上也是一个模板递归的过程。在这里，atomic type是边界。

既然产生出了class，那么剩下的事就是从这么一堆class中选择正确的class了。由于涉及到，可能在typelist中存在重复的type，因此Loki中作出了一个Helper。如下：

 

/*-------------------------------------*//*------ To get the right Class--------*//*-------------------------------------*/// Field helper -- to index the typetemplate < typelist _list, template <class> class Unit >Unit <typename _list::Head>&FieldHelper ( GenScatterHierarchy < _list, Unit >& obj, Int2Type< 0 > ){GenScatterHierarchy < typename _list::Head, Unit >&leftBase = obj;return leftBase;}template < int anyInt, typelist _list, template <class> class Unit >Unit <typename TypeAt<_list, anyInt>::Result>&FieldHelper( GenScatterHierarchy < _list, Unit >& obj, Int2Type < anyInt > ){GenScatterHierarchy < typename _list::Tail, Unit >&rightBase = obj;returnFieldHelper( rightBase, Int2Type <anyInt-1>() );}// Fieldtemplate < typelist _list, int anyInt, template <class> class Unit >Unit <typename TypeAt<_list, anyInt>::Result>&Field ( GenScatterHierarchy < _list, Unit >& obj ){return FieldHelper( obj, Int2Type < anyInt >() );}

 

在这里使用了Int2Type，通过Int2Type来构成另一个参数，Int2Type< 0 >是边界条件。

 

Typelist让我想起了《数据结构》中的广义表。二者太像了。都是分为头尾，都是递归的广泛使用。

 

最后是我的测试用例。其中使用了Typeinfo的外覆类。

#include <iostream>#include "TypeList.h"#include "TestTypeList.h"#include "TypeInfo.h"using namespace TL;using namespace std;int main(){// int idx = 1;typedefTYPELIST_4( int, int, string, char )mytype;typedefGenScatterHierarchy < mytype, Holder >WidgetInfo;WidgetInfo obj;// type_infotypeinfo;// cann't be used as thisField<mytype,1>(obj).value = 8;int x = Field<mytype,1>(obj).value;// TEST1: use std::type_info// typeinfo = typeid ( Field< mytype, 1 > (obj) );// cout<<typeid ( Field< mytype, 1 > (obj) ).name()<<endl;// TEST2: use type_info wrapperTypeInfotypeinfo( typeid(Field<mytype,2>(obj)) );cout<<typeinfo.name()<<endl;}