第七章、模板与泛型编程

条款41:了解隐式接口和编译期多态

有下面代码例子:

class Widget
{
public:Widget();virtual ~Widget();virtual std::size_t size() const;virtual void normalize();void swap(Widget &other);//...
};
void doProcessing(Widget& w)
{if(w.size()>10 && w!=someNastyWidget){Widget temp(w);temp.normalize();temp.swap(w);}
}

对于doProcessing函数:
1、w支持Widget接口。
2、由于Widget的某些成员函数是virtual ,w对于那些函数的调用将表现出运行期多态,也就是说将于运行期根据w的动态类型决定究竟调用哪一个函数。

下面将doProcessing从函数转变成函数模板:

template
void doProcessing(T& w)
{if(w.size()>10 && w!=someNastyWidget){Widget temp(w);temp.normalize();temp.swap(w);}
}

对于上面这个函数模板:
1、w必须支持哪一种接口,系由template中执行于w身上的操作决定的。

2、凡涉及w的任何函数调用,例如operator > 和operator != ,有可能造成template 具现化,使得这些调用得以成功。这样的具现行为发生在编译期。“以不同的template参数具现化 function template”会导致不同的函数,这便是所谓的编译期多态。

显式接口由函数的签名式(也就是函数名称、参数类型、返回类型)构成。例如Widget class:

class Widget
{
public:Widget();virtual ~Widget();virtual std::size_t size() const;virtual void normalize();void swap(Widget &other);//...
};

隐式接口并不基于函数签名式,而是由有效表达式组成。再次看看doProcessing template一开始的条件:

template
void doProcessing(T& w)
{if(w.size()>10 && w!=someNastyWidget){//。。。。}
}

T(w的类型)的隐式接口有这些约束:
1、它必须提供一个名为size的成员函数,该函数返回一个整数值。
2、它必须支持一个operator!= 函数,用来比较两个T对象。

doProcessing要求的其它隐式接口:copy 构造函数、normalize和swap也都必须对T型对象有效。
加诸于template参数身上的隐式接口,就像加诸于class 对象身上的显式接口一样真实,而且两者都在编译期完成检查。

请记住
1、class 和template都支持接口和多态
2、对class而言接口是显式的,以函数签名为中心。多态则是通过virtual 函数发生于运行期。
3、对template 参数而言,接口是隐式的,奠基于有效表达式 。多态则是通过template 具现化和函数重载解析发生于编译期。

条款42:了解typename的双重意义

下面有一个模板函数例子:

template
void print2nd(const C& container)//打印容器内的第二个元素
{//注意这不是有效的C++代码if(container.size()>=2){C::const_container iter(container.begin());//取得第一个元素的迭代器++iter;//将iter 移往第二个元素int value = *iter;//将该元素复制到某个intstd::cout <

template内出现的名称如果相依于某个template参数,称之为从属名称。如果从属名称在class 内呈嵌套状,我们称之为嵌套从属名称。C::const_container 就是这样一个名称。实际上它还是嵌套从属类型名称,也就是个嵌套从属名称并且指涉某类型。

int是个并不依赖任何template参数的名称。这样的名称是谓非从属名称。
嵌套从属名称有可能导致解析困难。举个例子,假设我们令print2nd更愚蠢些,这样起头:

template
void print2nd(const C& container)//打印容器内的第二个元素
{//注意这不是有效的C++代码if(container.size()>=2){C::const_container *x;//...}
}

看起来好像我们声明一个x为local变量,它是个指针,指向一个C::const_container。但它之所以被那么认为,只因为我们“已经知道”C::const_container是个类型。如果C::const_container不是个类型呢?如果C有个static成员变量而碰巧被命名为const_container ,或如果x碰巧是个global 变量名称呢?那样的话上述代码就不再是声明一个local 变量,而是一个相乘动作:C::const_container 乘以 x 。当然啦,这听起来有点疯狂,但却是可能的,而撰写C++ 解析器的人必须操心所有可能的输入,甚至是这么疯狂的输入。

当我们知道C是什么之前,没有任何办法可以知道C::const_container是否为一个类型。
C++有个规则可以解析此一歧义状态:如果解析器在template中遭遇一个嵌套从属名称,它便假设这个名称不是个类型,除非你告诉它是。所以缺省情况下嵌套从属名称不是类型。

template
void print2nd(const C& container)//打印容器内的第二个元素
{//注意这不是有效的C++代码if(container.size()>=2){C::const_container iter(container.begin());//这个名称被假设为非类型。//...}
}

我们告诉C++说C::const_container是个类型。只要紧临它之前放置关键字typename 即可:

template  //这是合法的C++代码
void print2nd(const C& container)//打印容器内的第二个元素
{//注意这不是有效的C++代码if(container.size()>=2){typename  C::const_container iter(container.begin());//这个名称被假设为非类型。//...}
}

一般性规则很简单:任何时候当你想要template中指涉一个嵌套从属类型名称,就必须在紧临它的前一个位置放上关键字typename。

typename只被用来验明嵌套从属类型名称:其它名称不该有它存在。例如下面这个 模板函数,接受一个容器和一个“指向该容器”的迭代器:

template //允许使用typename (或class)
void f(const C& container,//不允许使用typename typename C::container iter);//一定要使用typename 

“typename 必须作为嵌套从属类型名称的前缀词” 这一规则的例外是,typename不可以出现在base class list内的嵌套从属类型名称之前,也不可在 成员初始化列表中作为 base class修饰符。例如:

template
class Derived:public Base::Nested  //base class list中不允许 typename
{
public:explicit Derived(int x):Base::Nested(x)//mem. init. list中//不允许 typename {typename Base::Nested temp;//嵌套从属类型名称,//既不在base class list中也不在mem. init. list中,//作为一个base class修饰符需加上typename//....}//....
};

下面是一个模板函数,接受一个迭代器,而我们打算为该迭代器指涉的对象做一份Local 副本temp。代码如下:

template
void workWithIterator(IterT iter)
{typename std::iterator_traits::value_type temp(*iter);
}

std::iterator_traits::value_type相对于说“类型为IterT之对象所指之物的类型”。这个语句声明了一个local变量(temp),使用IterT对象所指物的相同类型,并将temp初始化为iter所指物。如果IterT是vector::iterator ,temp的类型就是int 。由于 std::iterator_traits::value_type 是个嵌套从属类型名称(value_type 被嵌套于iterator_traits 之内而 IterT是个template参数) ,故在其之前放置typename 。

下面代码等同上面的代码功能。

template
void workWithIterator(IterT iter)
{typedef typename std::iterator_traits::value_type value_type;value_type temp(*iter);
}

请记住
1、声明template参数时,前缀关键字class 和 typename可互换。
2、请使用关键字typename标识嵌套从属类型名称;但不得在base class list(基类列)或
member initialization list( 成员初值列 )内以它作为base class 修饰符。

条款43:学习处理模板化基类内的名称

假设我们想要撰写一个程序,它能够传送信息到若干不同的公司去。信息要不译成密码,要不就是未经加工的文字。使用template ,例子如下:

class CompanyA
{
public://...void sendCleartext(const std::string& msg);void sendEncrypted(const std::string& msg);//...
};
class CompanyB
{
public://...void sendCleartext(const std::string& msg);void sendEncrypted(const std::string& msg);//...
};
//... 针对其它公司设计的class
class MsgInfo//这个class用来保存信息,以备将来产生信息
{//...
};
template
class MsgSender
{
public://... 构造函数 析构函数void sendClear(const MsgInfo& info){std::string msg;//在这儿,根据info产生信息;Company c;c.sendCleartext(msg);}void sendSecret(const MsgInfo& info)//类似sendClear ,唯一不同是//这里调用c.sendEncrypted{//...}
};

上面做法行得通,但假设我们有时候想要在每次送出信息时记录(log)某些信息。derived class 可轻易加上这样的生产力,那似乎是个合情合理的解法:

template
class LoggingMsgSender:public MsgSender
{
public://... 构造函数 析构函数 等等void sendClearMsg(const MsgInfo& info){// 将 “传送前”的信息写至LogsendClear(info);//调用base class函数;这段代码无法通过编译//将 “传送后” 的信息写至此log;}//...};

这样的编译器会抱怨sendClear不存在。我们眼睛可以看到sendClear的确存在base class内,但是编译器却看不到它。为什么?

问题在于,当编译器遭遇class template template LoggingMsgSender定义式时,并不知它继承什么样的class 。当然它继承的是 MsgSender ,但其中的Company 是个template参数,不到后来(当LoggingMsgSender被具现化)无法确却知道它是个什么。而如果不知道Company 是什么,就无法知道class MsgSender 看起来像什么——更明确地说没办法知道它是否有个sendClear 函数。

一般性的MsgSender template 对CompanyZ 并不合适,因为那个template 提供了一个sendSecret函数,而对CompanyZ对象并不合理。因此使用一个特化版的MsgSender:

class CompanyZ//这个class 不提供  sendCleartext函数
{
public://...void sendEncrypted(const std::string& msg);//...};
template<>  //一个全特化
class MsgSender  //MsgSender ;它和一般的template相同,差别只在于它删除了sendClear。
{
public://...void sendSecret(const MsgInfo& info){//。。。}
};

注意class 定义式最前头的 “template<>” 语法象征这既不是template 也不是标准class ,而是特化版的MsgSender template ,在template实参是CompanyZ时被使用。模板全特化:template MsgSender针对类型CompanyZ 特化了,而且其特化是全面性的,也就是说一旦类型参数被定义为CompanyZ ,再没有其它template 参数可供变化了。

现在,MsgSender针对CompanyZ进行了全特化,让我们再次考虑derived class LoggingMsgSender:

template
class LoggingMsgSender:public MsgSender
{
public://... 构造函数 析构函数 等等void sendClearMsg(const MsgInfo& info){// 将 “传送前”的信息写至LogsendClear(info);//如果 Company  == CompanyZ ,这个函数不存在//将 “传送后” 的信息写至此log;}//...};

如注释所言,当base class被指定MsgSender 时这段代码不合法,因为那个class 并未提供sendClear函数。

为了重头来过,我们使用某种办法令C++ “不进入templated base classes 观察” 的行为失效。有三个办法,第一个是base class 函数调用动作之前加上"this->":

template
class LoggingMsgSender:public MsgSender
{
public://... 构造函数 析构函数 等等void sendClearMsg(const MsgInfo& info){// 将 “传送前”的信息写至Logthis->sendClear(info);//成立,假设sendClear 将被继承//将 “传送后” 的信息写至此log;}//...};

第二个使用using声明式。

template
class LoggingMsgSender:public MsgSender
{
public://... 构造函数 析构函数 等等using MsgSender::sendClear;//告诉编译器,请它假设 sendClear位于base class内。void sendClearMsg(const MsgInfo& info){// 将 “传送前”的信息写至LogsendClear(info);//ok 假设sendClear将被继承下来//将 “传送后” 的信息写至此log;}//...};

第三个做法,明白指出被调用的函数位于base class内:

template
class LoggingMsgSender:public MsgSender
{
public://... 构造函数 析构函数 等等void sendClearMsg(const MsgInfo& info){// 将 “传送前”的信息写至LogMsgSender::sendClear(info);//ok 假设sendClear将被继承下来//将 “传送后” 的信息写至此log;}//...};

但这往往是最不让人满意的一个解法,因为如果被调用的是virtual 函数,上述明确资格修饰(explicit qualification)会关闭 “virtual 绑定行为”。

从名称可视的角度出发,上述每一个解法做的事情都相同:对编译器承诺“base class template的任何特化版本都将支持其一般(泛化)版本所提供的接口”。但如果这个承诺最终未被实践出来,往后的编译最终还是会还给事实一个公道。举个例子,如果稍后的源码内含这个:

    LoggingMsgSender zMsgSender;MsgInfo msgData;//...  在msgData内放置信息zMsgSender.sendClearMsg(msgData);//错误,无法通过编译

其中对sendClearMsg的调用动作将无法通过编译,因为在那个点上,编译器知道base class 是个template 特化版本MsgSender ,而且它们知道那个class 不提供sendClear函数,而后者却是sendClearMsg尝试调用的函数。

请记住:
可在 derived class template 内通过“ this- >” 指涉 base class template 内的成员名称,或藉由一个明白写出的 “base class 资格修饰符” 完成。

条款44:将参数无关的代码抽离templates

举个例子,假设你想为固定尺寸的正方形矩阵编写一个template 。该矩阵的性质之一是支持逆矩阵运算。

template//template 支持 n x n矩阵,元素是
//类型为T的object ;见以下关于size_t参数的信息
class SquareMatrix
{
public://...void invert();
};

这个template接受一个类型参数T ,除此之外还接受一个类型为size_t 的参数,那是个非类型参数。这种参数和类型参数比起来较不常见,但它们完全合法,而且就像本例一样,相当自然。

现在考虑这些代码:

    SquareMatrix sm1;//...sm1.invert();//调用SquareMatrix::invertSquareMatrix sm2;sm2.invert();//调用SquareMatrix::invert

这会具现化两份invert 。

下面对SquareMatrix 的第一次修改:

template//与尺寸无关的base class
//用于正方矩阵 
//类型为T的object ;见以下关于size_t参数的信息
class SquareMatrixBase
{protected://...void invert(std::size_t matrixSize);//以给定的尺寸求矩阵
};template
class SquareMatrix:private SquareMatrixBase
{
private:using SquareMatrixBase::invert;//避免遮掩base 版的invert
public://...void invert(){ this->invert(n);}//制造一个inline调用,调用base class版的invert。//稍后说明为什么这儿出现this->
};

使用this->记号,避免:模板基类(SquareMatrixBase)内的函数名称会被 derived class掩盖。也请注意SquareMatrix 和SquareMatrixBase 之间的继承关系是private .这反应一个事实:这里的base class 只是为了帮助derived class实现,而不是为了表现SquareMatrix 和SquareMatrixBase 之间的is-a关系。

另一个办法是令SquareMatrixBase 贮存一个指针,指向矩阵数值所在的内存。而只要它存储了那些东西,也就可能储存矩阵尺寸。成果看起来像这样:

template
class SquareMatrixBase{
protected:SquareMatrixBase(std::size_t n,T *pMem)//储存矩阵大小和一个指针,指向矩阵数值:size(n),pData(pMem){ }void setDataPtr(T* ptr){pData=ptr;//重新赋值给pData}private:std::size_t size;//矩阵的大小T* pData;//指针,指向矩阵内容
};

这允许derived class决定内存分配方式。某些实现版本也许会决定将矩阵数据存储在SquareMatrix对象内部:

template
class SquareMatrix:private SquareMatrixBase{
protected:SquareMatrix():SquareMatrixBase(n,data){}//送出矩阵大小和数据指针给base class//...private:T* pData[n*n];//指针,指向矩阵内容
};

这种类型的对象不需要动态类型分配内存,但对象自身可能非常大。另一种做法是把每一个矩阵的数据放进heap(也就是new分配内存):

template
class SquareMatrix:private SquareMatrixBase{
protected://将base class的数据指针设为null。为矩阵内容分配内存//将指向该内存的指针存储起来,SquareMatrix():SquareMatrixBase(n,0),pData(new T[n*n]){this->setDataPtr(pData.get());//然后将它的一个副本交给base class}//送出矩阵大小和数据指针给base class//...private:boost::scoped_array pData;//boost::scoped_array见条款13
};

从另一个角度看,不同大小的矩阵只拥有单一版本的invert ,可以减少执行文件大小,也就因此降低程序的working set大小 ,并强调执行命令高速缓存区内的引用集中化。这些都可能使得程序执行得更加快速,超越“尺寸专属版”invert的最优效果。

在大多数平台上,所有指针类型都有相同的二进制表述,因此凡template持有指针者(例如list ,list,list*>) 往往应该对每一个成员函数使用唯一一位底层实现。

请记住
1、templates 生成多个classes和多个函数,所以任何template代码都不该与某个造成膨胀的template参数产生相依关系。

2、因非类型模板参数而造成的代码膨胀,往往可以消除,做法是以函数参数或class 成员变量替换template参数。

3、因类型参数而造成的代码膨胀,往往可降低,做法是让带有完全相同二进制表述的具现类型共享实现码。

条款45:运用成员函数模板接受所有兼容类型

下面时可能发生于三层继承体系的一些转换:

class  Top{//...
};class Middle :public Top
{//...  
};class Bottom :public Middle
{//...  
};Top * pt1 = new Middle;//将 Middle 转换为Top*Top * pt2 = new Bottom;//将 Bottom 转换为Top*const Top* pct2 = pt1; //将 Top* 转换为const Top*

但如果想在用户自定的智能指针中模拟上述转换,稍稍有点麻烦。我们希望以下代码通过编译:

template
class SmartPtr{
public://智能指针通常以内置(原始)指针完成初始化explicit SmartPtr(T * realPtr);//...
};SmartPtr pt1= SmartPtr (new Middle);//将SmartPtr 转换为 SmartPtrSmartPtr pt2= SmartPtr (new Bottom);  //将SmartPtr 转换为 SmartPtrSmartPtr pct2 =pt1;//将SmartPtr 转换为 SmartPtr

但是,同一个template的不同具现体之间并不存在什么与生俱来的固有关系。

template 和泛型编程
假设日后添加了:

class BelowBottom : public Bottom {
//。。。
}

我们因此必须令SmartPtr对象得以生成SmartPtr
对象,我们不希望一再修改 SmartPtr template 以满足此类需求。
我们需要的构造函数数量没有止尽,因为一个template 可被无限量具现化,以致生成无限量函数。我们需要为SmartPtr 写一个构造模板,这种模板成为成员函数模板,简称成员模板,其作用是为class 生成函数。

template
class SmartPtr{
public://...templateSmartPtr(const SmartPtr& other);//member template 为了生成copy构造函数
};

以上代码的意思是,对任何类型T和任何类型U ,这里可以根据SmartPtr< U > 生成一个SmartPtr< T > ——因为SmartPtr< T >有个构造函数接受一个SmartPtr< U > 参数。这类构造函数根据对象U 创建对象T(例如根据SmartPtr< U > 创建一个SmartPtr< T > ),而U和T 的类型 是同一个template 的不同 具现体,有时我们称之为泛化copy构造函数。

假设SmartPtr遵循auto_ptr 和tr1::shared_prt所提供的榜样,也提供一个get成员函数,返回智能指针对象所持有的那个原始指针的副本,可以在“构造模板”实现代码中的约束转换行为。

template
class SmartPtr{
public://智能指针通常以内置(原始)指针完成初始化explicit SmartPtr(T * realPtr);//...templateSmartPtr(const SmartPtr& other):heldPtr(other.get()){//以other的heldPtr初始化this的heldPtr//。。。}T* get() const{ return heldPtr;}
private:T* heldPtr;//这个SmartPtr持有的内置(原始)指针
};

以上这种行为只有当“存在某个隐式转换可将一个U* 指针转换为一个T * 指针”时才能通过编译。

下面是TR1规范中关于tr1::shared_ptr ,的一份摘录,其中强烈倾向声明template 参数时采用关键字class而不是 typename。

template
class shared_ptr
{
public:template//构造,来自任何兼容的内置指针explicit shared_ptr(Y* p);//内置指针template shared_ptr(shared_ptr const &r);//或shared_prttemplate explicit shared_ptr(weak_ptr const &r);//或weak_ptr template explicit shared_ptr(auto_ptr const &r);//或auto_ptr      template shared_ptr& operator=(shared_ptr const &r);//赋值,来自任何兼容的shared_prt或auto_ptrtemplate shared_ptr& operator=(auto_ptr &r);//赋值,来自任何兼容的shared_prt或auto_ptr//。。。
};

上述所有构造函数都是explicit, 唯有“泛化copy构造函数”除外。那意味从某个shared_ptr类型隐式转换至另一个shared_ptr 类型是被允许的,但从某个内置指针或从其它智能指针类型进行隐式转换则不被认可(如果是显式转换如cast 强制类型动作倒是可以)。

在class内声明一个copy构造函数(是个member template)并不会阻止编译器生成它们自己的copy构造函数(一个non-template),所以如果你想要控制copy构造的方方面面,你必须同时声明泛化copy 构造函数和 “正常的”copy构造函数。相同规则也适用于赋值操作。下面是tr1::shared_ptr的一份定义摘要,例证上述所言:

template
class shared_ptr
{
public:shared_ptr(shared_ptr const &r);//copy构造函数template//泛化copy构造函数shared_ptr(shared_ptr const& r);shared_ptr &operator=(shared_ptr const &r);//copy assignmenttemplate//泛化 copy assignmentshared_ptr &operator=(shared_ptr const &r);//。。。
};

请记住:
1、请使用成员函数模板生成“可接受所有兼容类型”的函数
2、如果你声明member template用于“泛化copy构造”或“泛化assignment操作”,你还是需要声明正常的copy构造函数和copy assignment 操作符。

条款46:需要类型转换时请为模板定义非成员函数

下面例子

template
class Rational
{
public:Rational(const T& numerator =0,const T & denominator =1);const T numerator() const;const T denominator() const;//...
};
template
const Rational operator *(const Rational& lhs,const Rational& rhs)
{//...
}Rational oneHalf(1,2);
Rational result = oneHalf *2;//错误,无法通过编译

因为在template实参推导过程中从不将隐式类型转换函数纳入考虑。

在template class内的friend 声明式可以指涉某个特定函数。那意味着class Rational 可以声明operator* 是它的一个friend函数。class template 并不依赖template 实参推导,所以编译器总是能够在class Rational具现化时得知T .。因此,令Rational class 声明适当的operator* 为其friend 函数,可以简化整个问题。

template
class Rational
{
public:Rational(const T& numerator =0,const T & denominator =1);const T numerator() const;const T denominator() const;//...friend const Rational operator *(const Rational& lhs,const Rational& rhs);
};
template
const Rational operator *(const Rational& lhs,const Rational& rhs)
{//...
}

现在对operator* 的混合式调用可以通过编译了,因为当对象oneHalf被声明为一个 Rational ,class Rational于是被具现化出来,而作为过程的一部分,friend函数 operator* (接受Rational 参数)也就被自动声明出来。后者作为一个函数而非函数模板,因此编译器可在调用它时使用隐式转换函数,而这便是混合式调用之所以成功的原因。

本例中的operator*被声明为接受并返回Rationals(而非Rationals) .。如果它被声明如下,一样有效:

template
class Rational
{
public:Rational(const T& numerator =0,const T & denominator =1);const T numerator() const;const T denominator() const;//...friend const Rational operator *(const Rational& lhs,const Rational& rhs);
};

最简单的可行方法就是将operator*函数本体合并至声明式内:

template
class Rational
{
public:Rational(const T& numerator =0,const T & denominator =1);const T numerator() const;const T denominator() const;//...friend const Rational operator *(const Rational& lhs,const Rational& rhs){return Rational(lhs.numerator()* rhs.numerator(),lhs.denominator()* rhs.denominator());}
};

为了令类型转换可能发生于所有实参身上,我们需要一个non-member函数;为了令这个函数被自动具现化,我们需要将它声明在class内部;而在class内部声明non-member 函数的唯一办法就是:令它成为一个friend 。

template class Rational;//声明Rational templatetemplate
const Rational doMultiply(const Rational& lhs,  const Rational& rhs);//声明helper templatetemplate
class Rational
{
public:Rational(const T& numerator =0,const T & denominator =1);const T numerator() const;const T denominator() const;//...friend const Rational operator *(const Rational& lhs,const Rational& rhs){return doMultiply(lhs,rhs);}
};
//许多编译器实质上会强迫你把所有template 定义式放进头文件内,所//以你或许需要在头文件内定义doMultiply
template
const Rational doMultiply(const Rational& lhs,  const Rational& rhs)//函数定义
{return Rational(lhs.numerator()* rhs.numerator(),lhs.denominator()* rhs.denominator());
}

请记住:
1、当我们编写一个class template,而它所提供之“ 与此template 相关的” 函数支持“ 所有参数之隐式类型转换 ” 时,请将那些函数定义为 “ class template 内部的friend 函数”。

条款47:请使用traits classes表现类型信息

定义一个template函数,名为advance,用来将某个迭代器移动某个给定距离:

template//将迭代器向前移动单位
void advance(IterT& iter,DistT d);//如果d < 0 则向后移动。 

STL有五类迭代器,分别是input迭代器、output迭代器、forward迭代器、Bidirectional迭代器、random accecc迭代器;C++标准程序库分别提供专属的卷标结构加以确认:

struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag:public input_iterator_tag{};
struct bidirectional_iterator_tag:public forward_iterator_tag{};
struct random_access_iterator_tag:public bidirectional_iterator_tag{};

这些structs之间的继承关系是有效的is-a关系:所有的forward 迭代器都是input迭代器,依此类推。很快我们会看到这个继承关系的效力。

实现advance的策略之一是采用“最低但最普及”的迭代器能力,以循环反复递增或递减迭代器。但是这种做法耗费线性时间。我们知道random access 迭代器支持迭代器算术运算,只耗费常量时间,因此如果面对这种迭代器,我们希望运用其优势。

advance的实现方式如下:

template
void advance(IterT& iter,DistT d)
{if(iter is a random access iterator){iter += d;//针对random access 迭代器使用迭代器算术运算}else {if(d>=0){ while (d--) {++iter;//针对其它迭代器分类}}else {while (d++) {--iter;//反复调用 ++ 或 --}}}}

traits ,它们允许你在编译期间取得某些类型信息。

因此类型的traits信息必须位于类型自身之外。

template//template 用来处理
struct iterator_traits;//迭代器分类的相关信息

如你所见,iterator_traits 是个struct,习惯上traits总是被实现为tructs, 但它们又被称为traits class .。

iterator_traits 的运作方式是,针对每一个类型IterT ,在struct iterator_traits< IterT >内一定声明某个typedef 名为iterator_category 。这个typedef用来确认IterT的迭代器分类。
iterator_traits 以两部分实现上述所言。首先它要求每一个“用户自定义的迭代器类型”必须嵌套一个typedef , 名为iterator_category ,用来确认适当的卷标结构。
例如下面的queue:

template<...>//略而未写template参数
class deque{
public:class iterator{public:typedef random_access_iterator_tag iterator_category;//...};//...
};

list 的实现如下:

template<...>//略而未写template参数
class list{
public:class iterator{public:typedef bidirectional_iterator_tag iterator_category;//...};//...
};

iterator_traits例子如下:

//类型IterT 的iterator_category其实就是用来表现 “IterT说它自己是什么”
//关于 “typedef typename”的运用,见条款42
template
struct iterator_traits
{typedef typename IterT::iterator_category iterator_category; 
};

上面的例子针对指针行不通,下面是iterator_traits为指针指定的迭代器类型

template//template 偏特化
struct iterator_traits //针对内置指针
{typedef random_access_iterator_tag iterator_category;};

如何设计并实现一个traits class:
1、确认若干你希望将来可取得的类型相关信息。例如对迭代器而言,我们希望将来可取得其分类( category)。
2、为该信息选择一个名称(例如 iterator_category)。
3、提供一个template 和一组特化版本(例如稍早说的iterator_traits),内含你希望支持的类型相关信息。
下面实现advance 的伪代码:

template
void advance(IterT& iter,DistT d)
{if(typeid (typename std::iterator_traits::iterator_category)==\typeid (std::random_access_iterator_tag))//..
}

但是,以上代码“if(typeid (typename std::iterator_traits::iterator_category)==
typeid (std::random_access_iterator_tag))”会导致编译问题。
下面doAdvance函数替换其功能:

template
void advance(IterT& iter,DistT d)
{if(typeid (typename std::iterator_traits::iterator_category)==\typeid (std::random_access_iterator_tag))//..
}
template//这份实现用于random access 迭代器
void doAdvance(IterT& iter,DistT d,std::random_access_iterator_tag)
{iter +=d;    
}template//这份实现用于bidirectional 迭代器
void doAdvance(IterT& iter,DistT d,std::bidirectional_iterator_tag)
{if(d >= 0){while (d--) {++iter;}}else {while (d++) {--iter;}}}
template//这份实现用于input 迭代器
void doAdvance(IterT& iter,DistT d,std::input_iterator_tag)
{if(d<0){throw std::out_of_range("Negative distance");}while (d--) {++iter;}}

有了这些重载doAdvance版本,advance需要做的只是调用它们并额外传递一个对象,后者必须带有适当的迭代器分类。

于是编译器运用重载解析机制调用适用的实现代码:

template
void advance(IterT& iter,DistT d)
{doAdvance(iter,d,typename std::iterator_traits::iterator_category());//调用的doAdvance版本,对iter之迭代器分类而言必须是适当的。
}

现在我们可以总结如何使用一个traits class了:
1、建立一组重载函数(身份像劳工)或函数模板(例如doAdvance),彼此间的差异只在于各自的traits参数。令每个函数实现码与其接受之traits信息相应和。

2、建立一个控制函数(身份像工头)或函数模板(例如advance),它调用上述那些“劳工函数”并传递traits class所提供的信息。

请记住:
1、Traits classes使得“类型相关信息”在编译期可用,它们以template和“templates 特化”完成实现。
2、整合重载技术后,traits classes 有可能在编译期对类型执行if…else测试。

条款48:认识template元编程

模板元编程(TMP)有两个伟大的效力。第一,它让某些事情更容易。第二,由于TMP执行于C++ 编译期,因此可将工作从运行期转移到编译期。这导致的一个结果是,某些错误原本通常在运行期才能侦测到,现在可在编译期找出来。另一个结果是,使用TMP的C++程序可能在每一个方面都更高效:较小的可执行文件、较短的运行期、较少的内存需求。然而将工作从运行期转移至编译期的另一个结果是,编译时间变长了。

这是STL advance的伪代码:

template
void advance(IterT& iter,DistT d)
{if(iter is a random access iterator){iter += d;//针对random access 迭代器使用迭代器算术运算}else {if(d>=0){ while (d--) {++iter;//针对其它迭代器分类}}else {while (d++) {--iter;//反复调用 ++ 或 --}}}}

我们使用typeid让其中的伪代码成为真实的代码,取得C++对此问题的一个“正常”解决方案——所有工作都在运行期进行:


template
void advance(IterT& iter,DistT d)
{if(typeid (typename std::iterator_traits::iterator_category)==\typeid (std::random_access_iterator_tag)){iter += d;//针对random access 迭代器使用迭代器算术运算}else {if(d>=0){ while (d--) {++iter;//针对其它迭代器分类}}else {while (d++) {--iter;//反复调用 ++ 或 --}}}}

条款47指出。这个typeid—based解法的效率比traits解法低,因为在此方案中(1)类型测试发生于运行期而非编译期,(2)“运行期类型测试”代码会出现在(或者说被连接于)可执行文件中。实际上这个例子展示了TMP如何能够比 “正常的”C++程序效率更高效,因为traits解法就是TMP。

advance的typeid—based实现方式可能导致编译期问题,下面就是个例子:

 std::list::iterator_traits iter;//..advance(iter ,10);//移动iter向前走10个元素;上述实现无法通过编译。

下面这一版advance便是针对上述调用而产生的。将template参数IterT 和DistT 分别替换为iter和10的类型之后,我们得到这些:

void advance( std::list::iterator_traits & iter,int d)
{if(typeid (typename std::iterator_traits::iterator_category)==\typeid (std::random_access_iterator_tag)){iter += d;//错误}else {if(d>=0){ while (d--) {++iter;//针对其它迭代器分类}}else {while (d++) {--iter;//反复调用 ++ 或 --}}}}

list::iterator_traits 是bidirectional迭代器,并不支持+= ,只有random access迭代器才支持+=;

TMP的起手程序是在编译期计算阶乘。TMP的阶乘运算示范如何通过“递归模板具现化”实现循环,以及如何在TMP中创建和使用变量,例如下面代码:

template//一般情况Factorial的值是 n乘以Factorial的值
struct Factorial{enum{value =n*Factorial::value;};
};
template<>
struct Factorial<0>//特殊情况:Factorial<0> 的值是1
{enum{ value=1};
};int main()
{std::cout<::value;//输出120std::cout<::value;//输出3628800return 0;
}

TMP可以达成以下三个目标:
1、确保量度单位正确。
2、优化矩阵计算。
3、可以生成客户定制之设计模式实现品。

请记住:
1、模板元编程可将工作由运行期移往编译期,因而得以实现早期错误侦测和更高的执行效率。
2、模板元编程可以被用来生成“基于政策选择组合”的客户定制代码,也可以用来避免生成对某些特殊类型并不适合的代码。