effective c++ -- 模板与泛型编程

面向对象提供了运行期的多态，而模板则提供了编译期的多态。模板的编译期多态机制使得函数匹配机制相对于非模板的函数匹配发生了一些变化，也影响了继承体系下的一些声明与设计。本章讲解了模板的编译期多态对我们原先所熟悉的没有模板的世界的一些区别，最后介绍了traits class以及template元编程。

Item 41: 了解隐式接口和编译期多态
通常显式接口由函数的签名式（函数名称、参数类型、返回类型）构成。例如Widget class：

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

其public接口由一个构造函数、析构函数、函数size、normalize、swap及其参数类型、返回类型、常量性构成。
隐式接口就完全不一样了。它并不基于函数签名式，而是由有效表达式组成。例如下面的模板函数doProcessing：

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

T的隐式接口看起来好像有这些约束：
（1）它必须提供一个名为size的成员函数，该函数返回一个整数值。
（2）它必须支持一个operator!=函数，用来比较两个T对象，
但其实这两个约束都不需要满足。T必须支持size函数，但是这个函数也可能从base class继承而得；这个成员函数不一定需要返回一个整数值，甚至不需要返回一个数值类型。它唯一需要做的是返回一个类型为X的对象，该对象加上一个int型后可以调用一个operator>。同样道理，T也不需要支持operator!=，只要存在一个operator!=，它接受一个类型为X的对象和一个类型为Y的对象，T可被转换为X而someNastyWidget可被转换为Y。
总结起来，
对class而言，接口是显式的，以函数签名为中心。多态则是通过virtual函数发生于运行期。
对template参数而言，接口是隐式的，基于有效表达式。多态则是通过template具现化和函数重载解析，发生于编译期。

Item 42: 了解typename的双重意义
在C++中，声明template参数时，不论使用关键字class或typename，意义完全相同。
但是在某些情况下，你必须使用typename：
template内出现的名称如果相依于某个template参数，称之为从属名称（dependent names），如果从属名称在class内呈嵌套关，则称之为嵌套从属名称（nested dependent name）。如果解析器在template中遭遇一个嵌套从属名称，它便假设这名称不是个类型，除非你明确告诉它是，做法是在它之前放置关键字typename。typename只能被用来验明嵌套从属类型名称，其他名称不该有它存在。同时，typename不可以出现在base class list内的鞋套从属类型名称之前，也不可在member initialization list中作为base class修饰符。下面是一个例子：

template<typename C>
void print2nd( const C& container ){
  if( container.size() >= 2 ){
    //C::const_iterator即为一个嵌套从属名称，
    //编译器默认假设它不是个类型
    //因此这段代码不合法
    C::const_iterator iter(container.begin());
    ++iter;
    int value = *iter;
    std::cout<<value;
  }
}
//修改一下：
template<typename C>
void print2nd( const C& container ){
  if( container.size() >= 2 ){
    //在C::const_iterator前放置关键字typename
    //明确说明该嵌套从属名称是一种类型。
    typename C::const_iterator iter(container.begin());
    ...
  }
}
//typename不能出现在base class list或member initialization list中
template<typename T>
class Derived: public Base<T>::Nested{
  public:
    explicit Derived( int x ):
      Base<T>::Nested(x){
	typename Base<T>:Nested temp;
	...
      }
};
//如果编译器不知道Base<T>::nested是什么，可以在前面先用typedef
typedef typename Base<T>::Nested Nested;

//然后凡需要Base<T>::Nested的地方则使用Nested。

Item 43: 学习处理模板化基类内的名称
模板都会编译两次，第一次检查语法，第二次具现化。假如模板有不同参数，则会对每个参数都具现一次。如果参数不确定，则不可能具现，也就不知道它的行为。
一个类模板继承于另一个相同模板参数的基类，派生类使用到基类的成员时，编译器往往会报错该成员未定义。因为在第一次编译的语法检查中，即使知道Derived<T>继承自Base<T>，但其中的T是个template参数，不到Derived被具现化无法确切知道它是什么，而如果不知道T是什么，就无法知道Base<T>看起来像什么——于是就不知道它是否有什么成员。有三种方法可以令C++“不进入templatized base class观察”的行为失效：
（1）当需要用到base class的成员时，在该成员前加上this->
（2）使用using声明告诉编译器，使它进入base class作用域内查找
（3）明白指出被调用的函数位于base class内。即Base<T>::member
第三种解法往往是最不让人满意的一种。因为如果被调用的是virtual函数，使用明确指出的方式会关闭virtual绑定行为。
除此之外，这三种解法做的事情都相同：对编译器承诺base class template的任何特化版本都支持其一般版本所提供的接口

Item 44: 将与参数无关的代码抽离templates
template为每一个模板参数生成一份代码，可能会造成代码膨胀。模板参数分为类型参数和非类型参数，通常非类型参数比较容易造成代码膨胀，例如下面一个例子：

template<typename T, std::size_t n>
class SquareMatrix{
  public:
    ...
      void invert();	//求逆矩阵
};
SquareMatrix<double, 5> sm1;
SquareMatrix<double, 10> sm2;
sm1.invert();	//调用SquareMatrix<double, 5>::invert
sm2.invert();	//调用SquareMatrix<double, 10>::invert

非类型参数就是这样轻易地造成了代码膨胀。
不过其实类型参数也会导致代码膨胀。例如在许多平台上，int和long有相同的二进制表述，所以像vector<int>和vector<long>的成员函数有可能完全相同，这正是膨胀的定义。又如，在大多数平台上，所有指针类型都有相同的二进制表述，因此凡template持有指针者（例如list<int*>, list<double*>等）往往应该对每一个成员函数使用唯一一份底层实现。如果你实现某些成员函数而它们操作强类型指针（即T*），应该令它们调用另一个操作无类型指针的函数，由后者完成实际工作。

Item 45: 利用成员函数模板接受所有兼容类型
真实指针做得很好的一件事是，它支持隐式转换，如下：

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

我们希望智能指针也能实现像真实指针这样的自动转换，即我们可以像下面那样转换智能指针：

template<typename T>
class SmartPtr{
  public:
    explicit SmartPtr( T* realPtr );	//以内置指针完成初始化
    ...
};

SmartPtr<Top> pt1 = SmartPtr<Middle>( new Middle );	//将SmartPtr<Middle>转换为SmartPtr<Top>
SmartPtr<Top> pt2 = SmartPtr<Bottom>( new Bottom );	//将SmartPtr<Bottom>转换为SmartPtr<Top>
SmartPtr<const Top> pct2 = pt1;				//将SmartPtr<Top>转换耿SmartPtr<const Top>

为此我们可以为SmartPtr编写构造函数，使其行为能够满足我们的转型需要。可是似乎我们无法写出我们需要的所有构造函数，因为一旦一个继承体系被扩充，相当于我们需要添加一个构造函数。我们必须为它写一个构造模板。这样的模板是所谓member function template（成员函数模板），其作用是为class生成函数：

template<typename T>
class SmartPtr{
  public:
    template<typename U>
      SmartPtr( const SmartPtr<U>& other )
      ...
};

这段代码的意思是，对任何类型T和任何类型U，这里可以根据SmartPtr<U>生成一个SmartPtr<T>。这样的函数我们称之为泛化copy构造函数。
但是，我们并不希望根据一个SmartPtr<Top>生成一个SmartPtr<Middle>，这不符合逻辑。我们可以在“构造模板”实现代码中约束转换行为：

template<typename T>
class SmartPtr{
  public:
    //这样如果两者不兼容，不支持隐式转换，编译会报错。
    template<typename T>
      SmartPtr( const SmartPtr<U>& other )
      : heldPtr(other.get()){	}
    T* get() const{	return heldPtr;	}
  private：
    T* heldPtr;
      ...
};

member function template的效用不限于构造函数，它们常扮演的另一个角色是支持赋值操作。另外，member function template并不改变语言基本规则。如果程序需要一个copy构造函数，而你没有声明它，编译器会为你暗自生成一个。在class内声明泛化copy构造函数并不会阻止编译器生成它们自己的copy构造函数（non-template的）。因此如果你想要控制copy构造函数的方方面面，你必须同时声明泛化构造函数和“正常的”copy构造函数。相同规则也适用于赋值操作。

Item 46: 需要类型转换时请为模板定义非成员函数
我们在前面提到过用将Rational的operator*声明为non-member，从而使2*oneHalf得以成功调用该函数。这是在没有template的情况下。Rational和operator*被模板化后会怎样呢？

template<typename T>
clas Rational{
  public:
    Rational( const T& numerator=0, const T& denumerator=1 );
    const T numerator() const;
    const T denumerator() const;
    ...
};
template<typename T>
const Rational<T> operator* ( const Rational<T>& lhs, const Rational<T>& rhs ){
  ...
}

加上模板后，我们又不能成功调用2*oneHalf了。为什么呢？编译器是根据调用operator*的参数类型的推导来具现化operator*的。template在实参推导过程中从不将隐式类型转换函数纳入考虑。这样的转换在函数调用过程中的确被使用，但在能够调用一个函数之前，首先必须知道那个函数存在。编译器找不到哪个模板可以生成operator*( Rational<int>&, int& )函数，在具现化之前又不考虑int到Rational<int>的隐式转换，因此最终编译器找不到适当的函数来调用2*oneHalf。
解决这个问题的关键在于：template class内的friend声明式可以指涉某个特定函数。class template并不倚赖template实参推导（实参推导只发生在function template上），所以编译器总是能够在class Rational<T>具现化时得知T。因此令Rational<T> class声明适当的operator*为其friend函数：

template<typename T>
class Rational{
  public:
    ...
      //当某一Rational<T>被具现化出来后，对应于Rational<T>的operator*版本
      //也被具现化出来，它明确说明它的第一个参数是Rational<T>
      //第二个参数也是Rational<T>，这时候隐式转换就能发挥作用了
      friend const Rational operator*( const Rational& lhs,
	  				const Rational& rhs );
};
//该函数并非上述声明式operator*函数的定义
template<typename T>
const Rational<T> operator*( const Rational<T>& lhs, const Rational<T> rhs ){
  ...
}

现在，编译器知道该为2*oneHalf调用哪个函数了，可是，我们还没有提供定义式！（注意：下面的模板函数跟上面的friend函数没有半毛钱关系。）我们只是声明了这个函数，去哪里定义它呢？看来唯一可以定义该函数的地方就在class定义体内了。而定义于class内部的函数都暗自成为inline函数，自然的，像operator*这样的函数成为inline函数问题也不大，但是如果函数本体很长呢？让它什么事情都不做，只调用定义于class外部的辅助函数：

template<typename T> class Rational;	//声明Rational template
template<typename T> 
const Rational<T> doMultiply( const Rational<T>& lhs,
				const Rational<T>& rhs ){ ... }
template<typename T>
class Rational{
  public:
    ...
      friend Rational<T> operator*( const Rational<T>& lhs, 
	  				const Rational<T>& rhs ){
	return doMultiply( lhs, rhs ); }
    ...
};

是的，doMultiply依旧不支持混合式运算，但是实参在经过operator*的时候已经隐式转换成了Rational<T>了，所以可以正确调用doMultiply来做真正的事。
总结起来，为了让类型转换可能发生于所有实参身上，我们需要一个non-member函数；为了令这个函数被自动具现化，我们需要将它声明在class内部；而在class内部声明non-member函数的唯一办法就是令它成为一个friend。而且，定义该non-member函数的唯一地点就是class内部。然而，定义在class内部的函数将自动成为inline函数，如果函数本体很长，会造成代码膨胀，可以在class外部定义一个做实事的函数，让friend函数唯一做的一件事就是调用这个函数。

Item 47: 请使用traits class表现类型信息
为了说明traits class的作用，这一节用迭代器做了一个例子。
STL有五种迭代器：
（1）Input迭代器只能向前移动，且一次一步，客户只可读取它们所指的东西，而且只能读一次；这一类代表是istream_iterator。
（2）Output迭代器跟Input相似，但是客户只可涂写它们所指的东西，而且只能写一次;这一类代表是ostream_iterator。
（3）Forward迭代器可以做前述两种分类所能做的每一件事，而且可以读或写其所指物一次以上。
（4）Bidirectional迭代器除了可以向前移动，还可以向后移动，例如list迭代器。
（5）最厉害的是random access迭代器，它可以完成上面各分类迭代器所能做的每一件事情，而且可以向前或向后跳跃任意距离。vector, deque,和string提供的迭代器都属这一类。
对于这五种分类，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{};

假设我们欲实现一个函数advance，用来将某个迭代器移动某个给定距离，那么我们必须先判断该iterator是否为random access的，否则要采用不同的跳跃方法：

template<typename IterT, typename DistT>
void advance( IterT& iter, DistT d ){
  if( iter is a random access iterator )
    iter += d;
  else{
    if( d >= 0 ){ while(d--) ++iter; }
    else{ while( d++ ) --iter; }
  }
}

怎样才能得知iter类型的某些信息呢？traits允许我们在编译期间取得某些类型信息。
traits并不是C++关键字或一个预先定义好的构件：它们是一种技术，也是一个C++程序员共同遵守的协议。这个技术的要求之一是，它对内置类型和用户自定义类型的表现必须一样好，因此类型的traits信息必须位于类型自身之外。标准技术是把它放进一个template及其一个或多个特化版本中。这样的template在标准程序中有若干个，其中针对迭代器者被命名为iterator_traits。

template<typename IterT>
struct iterator_traits;

iterator_traits的动作方式是：针对每一个类型IterT，在struct iterator_traits<IterT>内声明某个typedef名为iterator_category，这个typedef用来确认IterT的迭代器分类。
iterator_traits以两个部分完成这个任务。首先它要求每一个“用户自定义迭代器类型”必须嵌套一个typedef，名为iterator_category，用来确认适当的卷标结构。其次，iterator_traits将鹦鹉学舌般地响应iterator class的嵌套式typedef。如下：

template<...>
class deque{
  public:
    class iterator{
      public:
	typedef random_access_iterator_tag iterator_category;
	...
    }
    ...
};

template<...>
class list{
  public:
    class iterator{
      public:
	typedef bidirectional_iterator_tag iterator_category;
	...
    }
    ...
};
//类型IterT的iterator_category用来表现“IterT说它自己是什么”
template<typename IterT>
struct iterator_traits{
  typedef typename IterT::iterator_category iterator_category;
  ...
};
//为了支持指针迭代器，iterator_traits特别针对指针类型提供一个偏特化版本
template<typename IterT>
struct iterator_traits<IterT*>{
  typename random_access_iterator_tag iterator_category;
  ...
};

现在我们可以用iterator_traits来判定迭代器的类型了：

template<typename IterT, typename DistT>
void advance( IterT& iter, DistT d ){
  if( typeid(typename std::iterator_traits<IterT>::iterator_category)
      == typeid(std::random_access_iterator_tag)){
    iter += d;
  }
  else
    ...
}

这段代码有两个问题，其一是它无法通过编译，其二是，我们知道，IterT类型在编译期间获知，因此iterator_traits<IterT>::iterator_category也可以在编译期间确定，但是if语句却是在运行期才会核定，为什么将可在编译期完成的事延到运行期才做呢？这不仅浪费时间，也造成可执行文件膨胀。
如何让编译器在编译时间就对类型进行核定呢？重载。

template<typename IterT, typename DistT>
void doAdvance( IterT& iter, DistT d, std::random_access_iterator_tag ){
  iter += d;
}
template<typename IterT, typename DistT>
void doAdvance( IterT& iter, DistT d, std::bidirectional_iterator_tag){
  if( d>=0 ) { while (d--) ++iter; }
  else { while( d++ ) --iter; }
}
template<typename IterT, typename DistT>
void doAdvance( IterT& iter, DistT d, std::input_iterator_tag){
  if( d<0 )
    throw std::out_of_range("Nagative Distance");
  while (d--) ++iter;
}

template<typename IterT, typename DistT>
void advance( IterT& iter, DistT d ){
  doAdvance( iter, d,
      std::iterator_traits<IterT>::iterator_category()
      );	//神奇而美妙的代码
}

那么前面那个if...else代码为什么会不能通过编译呢？假设有下面的运行语句：

std::list<int>::iterator iter;
...
advance( iter, 10 );	//iter是bidirectional_iterator

针对这段代码，编译器尝试为它生成一个版本，大概是这样：

void advance( std::list<int>::iterator& iter, int d ){
  if( typeid(std::iterator_traits<std::list<int>::iterator>::iterator_category)
      == typeid( std::random_access_iterator_tag ) )
    iter += d;	//!错误发生在这里
  else
    ...
}

我们知道，iter+=d总是不会被执行到，但是编译器看到了，它要求所有的源码都必须有效，即使是不会执行起来的代码。因此，编译不通过。
traits class，或者应该说，template编程真是一件神奇的事情。

Item 48: 认识template元编程
至于元编程，我想我是真不知道怎么去总结了。只觉得它非常奇妙。就像前面的advance一样，也是元编程的一种。我们已经看到，advance是如何通过元程序将工作由运行期移往编译期的，也由此得以实现早期错误侦测和更高的执行效率。