Templates and Generic Programming

C++ template 机制自身是一部完整的图灵机C Turing-complete) ：它可以被用来计算任何可计算的值。于是导出了模板元编程(template metaprogramming) ，创造出“在C++编译器内执行并于编译完成时停止执行”的程序。

[toc]

41. Understand implicit interfaces and compile-time polymorphism.

面向对象编程世界总是以显式接口(explicit interfaces) 和运行期多态(runtime polymorphism)解决问题。

模板反倒是反倒是隐式接口(implicit interfaces)和编译期多态(compile-time polymorphism)移到前头了。

来看以下例子：

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

  ...
};

以及这个（同样没有什么意义的）function（函数），

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

由于w 的类型被声明为Widget, 所以w 必须支持Widget 接口。我们可以在源码中找出这个接口（例如在Wodget 的.h 文件中），看看它是什么样子，所以我称此为一个显式接口(explicit interface)，也就是它在源码中明确可见。
由于widget的某些成员函数是virtual, w 对那些函数的调用将表现出运行期多态(runtime polymorphism)，也就是说将于运行期根据w 的动态类型（见条款37)决定究竟调用哪一个函数。

当我们将doProcessing 从函数转变成函数模板(function template) 时发生什么事：

现在我们怎么说doProcessing 内的w 呢？

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

w 必须支持哪一种接口，系由template 中执行千w 身上的操作来决定。本例看来w 的类型T 好像必须支持size,norrnalize 和swap 成员函数、copy 构造函数（用以建立temp) 、不等比较(inequality comparison, 用来比较someNasty-Widget) 。我们很快会看到这并非完全正确，但对目前而言足够真实。重要的是，这一组表达式（对此template 而言必须有效编译）便是T 必须支持的一组隐式接口(implicit interface)。
凡涉及w 的任何函数调用，例如operator> 和operator!= ，有可能造成template具现化，使这些调用得以成功。这样的具现行为发生在编译期。“以不同的template 参数具现化function templates“ 会导致调用不同的函数，这便是所谓的编译期多态(compile-time polymorphism) 。

显示接口于隐式接口的区别：

显式接口由函数的签名式（也就是函数名称、参数类型、返回类型）构成。
隐式接口就完全不同了。它并不基于函数签名式，而是由有效表达式(valid expressions) 组成。即参数能通过隐式转换执行。

请记住

classes 和templates 都支持接口(interfaces) 和多态(polymorphism) 。
对classes 而言接口是显式的(explicit) ，以函数签名为中心。多态则是通过virtual函数发生于运行期。
对template 参数而言，接口是隐式的(implicit) ，奠基于有效表达式。多态则是通过template 具现化和函数重载解析(function overloading resolution) 发生于编译期。

42. Understand the two meanings of typename.

在现代 C++ 编程中，typename 和 class 在模板参数声明中可以互换使用，但 typename 更准确地表达了模板参数是一个类型的意图。
从属名称是指在模板定义中依赖于模板参数的名称。这些名称只有在模板实例化时，即模板参数的具体类型被确定后，才能被解析。
嵌套从属名称是指在一个模板定义中，依赖于模板参数的名称嵌套在其他依赖于模板参数的名称之中。
任何时候当你想要在template 中指涉一个嵌套从属类型名称，就必须在紧临它的前一个位置放上关键字typename 。

//TODO

请记住

声明template 参数时，前缀关键字class 和typename 可互换。
请使用关键字typename 标识嵌套从属类型名称；但不得在base class lists （基类列）或member initialization list （成员初值列）内以它作为base class 修饰符。

43. Know how to access names in templatized base classes.

前面的看一下书，意思就是派生类想调用模板父类的函数，只能在该父类被实例化后才能确定调用。因为父类可能针对特定情况进行了偏特化，而该特化没有此函数。

我们有三种做法解决这一问题：

通过this->


template<typename Company>
class LoggingMsgSender: public MsgSender<Company> {
public:


  void sendClearMsg(const MsgInfo& info)
  {
    write "before sending" info to the log;

    this->sendClear(info);                //假设sendClear会被继承

    write "after sending" info to the log;
  }

通过using声明式

template<typename Company>
class LoggingMsgSender: public MsgSender<Company> {
public:
  using MsgSender<Company>::sendClear;   //告诉编译器假设SendClear位于base clas
  void sendClearMsg(const MsgInfo& info)
    sendClear(info);                     //假设sendClear会被继承
  }
};

通过指出被调用的函数位于base class

template<typename Company>
class LoggingMsgSender: public MsgSender<Company> {
public:
  
  void sendClearMsg(const MsgInfo& info)
  {
    MsgSender<Company>::sendClear(info);     //假设sendClear会被继承
  }                                          

  ...
};

注意如果是virtual函数，上述将关闭virtual绑定行为。

请记住

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

44. Factor parameter-independent code out of templates.

使用template可能会导致代码膨胀。

我们可以使用一个听起来十分nb的方法共性与变性分析(commonality and variability analysis)，但其十分平民化。

例如我们会把类中相同（共性）的部分整合为父类，在子类中使用继承和复合来存放不同(变性)的部分。

现在，我们考虑一个矩阵：

template<typename T,           // 用于表示类型为 T 的对象的 n x n 矩阵的模板；请参阅下面有关 size_t 参数的信息
         std::size_t n>        // size_t 参数的大小，用于确定矩阵的大小
class SquareMatrix {           // 方阵类定义
public:
  ...
  void invert();               // 将矩阵原地求逆
};

考虑如下代码

SquareMatrix<double, 5> sm1;
...
sm1.invert();                  // 调用 SquareMatrix<double, 5>::invert

SquareMatrix<double, 10> sm2;
...
sm2.invert();                  // 调用 SquareMatrix<double, 10>::invert

我们肯定想优化他们，那么我们可以更改为带一个表示矩阵大小参数的函数。

template<typename T>                   // 用于表示方阵的大小无关的基类模板
class SquareMatrixBase {               // 方阵的基类
protected:
  ...
  void invert(std::size_t matrixSize); // 对给定大小的矩阵进行求逆操作
  ...
};

template<typename T, std::size_t n>
class SquareMatrix: private SquareMatrixBase<T> {
private:
  using SquareMatrixBase<T>::invert;   // 避免隐藏基类版本的 invert；参见 Item 33
public:
  ...
  void invert() { this->invert(n); }    
};                                    // 使用 "this->",参见上一条

但是我们是不是忘了什么，对呀！我们的数据在哪？

我们令SquareMartixBase贮存一个指向矩阵的指针。

template<typename T>
class SquareMatrixBase {
protected:
  SquareMatrixBase(std::size_t n, T *pMem)     // 存储矩阵的大小和指向矩阵值的指针
  : size(n), pData(pMem) {}                    // 构造函数，初始化 size 和 pData

  void setDataPtr(T *ptr) { pData = ptr; }     // 重新分配 pData 的指针
  ...

private:
  std::size_t size;                            // 矩阵的大小
  T *pData;                                    // 指向矩阵值的指针
};

这样就是让 derived classes（派生类）决定如何分配内存。某些实现可能决定直接在 SquareMatrix object 内部存储矩阵数据：

template<typename T, std::size_t n>
class SquareMatrix: private SquareMatrixBase<T> {
public:
  SquareMatrix()                               // 将矩阵大小和数据指针发送给基类
  : SquareMatrixBase<T>(n, data) {}            // 构造函数，将矩阵大小和数据指针发送给基类
  ...

private:
  T data[n*n];                                 // 存储矩阵值的数组
};

我们也可以将矩阵数据放入heap。

 boost::scoped_arraytemplate<typename T, std::size_t n>
class SquareMatrix: private SquareMatrixBase<T> {
public:
  SquareMatrix()                               // 将基类数据指针设置为 null，
  : SquareMatrixBase<T>(n, 0),                 // 为矩阵值分配内存，
    pData(new T[n*n])                          // 保存一个指向内存的指针，
  { this->setDataPtr(pData.get()); }           // 并将其副本传递给基类

private:
  boost::scoped_array<T> pData;                // 用于存储矩阵值的数组
};  // 有关scoped_array的信息，请参见条款13

但是，我们为了减少代码膨胀这样写会有什么效果呢？

在尺寸专属版中，尺寸是个编译期常量，因此可以由常量的广传达到最优化，包括把它们折进被生成指令中成为直接操作数。这在“与尺寸无关”的版本中是无法办到的。
从另一个角度看，不同大小的矩阵只拥有单一版本的invert, 可减少执行文件大小，也就因此降低程序的working set（内存页）大小，并强化指令高速缓存区内的引用集中化(locality of reference) 。这些都可能使程序执行得更快速，超越“尺寸专属版”invert 的最优化效果。
哪一个影响占主要地位？欲知答案，唯一的办法是两者都尝试并观察你的平台的行为以及面对代表性数据组时的行为。

请记住

Templates 生成多个classes 和多个函数，所以任何template 代码都不该与某个造成膨胀的template 参数产生相依关系。
因非类型模板参数(non-type template parameters) 而造成的代码膨胀，往往可消除，做法是以函数参数或class 成员变最替换template 参数。
因类型参数(type parameters) 而造成的代码膨胀，往往可降低，做法是让带有完全相同二进制表述(binary representations) 的具现类型(instantiation types)共享实现码。

45. Use member function templates to accept “all compatible types”

我们知道，普通指针可以轻易进行隐式转换。

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*

我们想在智能指针也实现此类操作。

// 智能指针通常是通过内置指针初始化的
class SmartPtr {
public:
  // 智能指针通过内置指针初始化
  explicit SmartPtr(T *realPtr);
  // ... 省略了其他成员函数和成员变量
};

SmartPtr<Top> pt1 =                 // 将 SmartPtr<Middle> 转换为 SmartPtr<Top>
SmartPtr<Middle>(new Middle);       // 创建一个新的 SmartPtr<Top>

SmartPtr<Top> pt2 =                 // 将 SmartPtr<Bottom> 转换为 SmartPtr<Top>
SmartPtr<Bottom>(new Bottom);       // 创建一个新的 SmartPtr<Top>

SmartPtr<const Top> pct2 = pt1;     // 将 SmartPtr<Top> 转换为 SmartPtr<const Top>
                                    // 把 pt1 作为 SmartPtr<const Top> 类型的智能指针

我们需要让template知道转换的两个类型，因此我们需要的不是为SmartPtr写－个构造函数，而是为它写一个构造模板。这样的模板(templates) 是所谓member function templates （常简称为member templates) ，其作用是为class 生成函数：

template<typename T>
class SmartPtr {
public:
  template<typename U>                       // 成员模板
  SmartPtr(const SmartPtr<U>& other);        // 用于实现“泛化的拷贝构造函数”
  ...                                        // 其他成员
};

这一类构造函数根据对象u 创建对象t （例如根据SmartPtr 创建一个SmartPtr) ，而u 和v 的类型是同一个template 的不同具现体，有时我们称之为泛化(generalized) copy 构造函数。

接下来是使用成员初始化列表，只有当类型能被转换时才通过编译。

template<typename T>
class SmartPtr {
public:
  template<typename U>
  SmartPtr(const SmartPtr<U>& other)         // 使用其他智能指针的指针来初始化当前智能指针
  : heldPtr(other.get()) { ... }             // 使用其他智能指针持有的指针来初始化当前智能指针持有的指针

  T* get() const { return heldPtr; }         // 获取当前智能指针持有的指针
  ...

private:                                     // 当前智能指针所持有的内置指针
  T *heldPtr;                                // 由 SmartPtr 所持有的内置指针
};

最终的效果就是 SmartPtr 现在有一个 generalized copy constructor（泛型化拷贝构造函数），它只有在传入一个 compatible type（兼容类型）的参数时才能编译。

//TODO

请记住

请使用member function templates （成员函数模板）生成“可接受所有兼容类型”的函数。
如果你声明member templates 用千“泛化copy 构造”或“泛化assignment 操作“,你还是需要声明正常的copy 构造函数和copy assignment 操作符。

46. Define non-member functions inside templates when type conversions are desired.

本条款将条款24的Rational 和operator* 模板化了：

template<typename T>
class Rational {
public:
  Rational(const T& numerator = 0,     // 参见 Item 20，参数现在通过引用传递
           const T& denominator = 1);  // 参见 Item 20，参数现在通过引用传递

  const T numerator() const;           // 参见 Item 28，返回值仍然通过值传递
  const T denominator() const;         // 参见 Item 28，返回值仍然通过值传递
  ...                                  // 参见 Item 3，返回值为 const
};

template<typename T>
const Rational<T> operator*(const Rational<T>& lhs,
                            const Rational<T>& rhs)
{ ... }
Rational<int> oneHalf(1, 2);          
Rational<int> result = oneHalf * 2;

但是我们知道参数推导是个大问题，int类型2不会被推导为Rational，因为template在实参推导的过程中不将隐式类型转换函数考虑在内。

我们可以使用友元函数解决

template class 内的friend 声明式可以指涉某个特定函数。那意味class Rational可以声明operator 是它的一个friend 函数。Class templates 并不倚赖template 实参推导（后者只施行于function templates 身上），所以编译器总是能够在class Rational 具现化时得知T 。因此，令Rational class 声明适当的operator 为其friend 函数，可简化整个问题：



template<typename T> class Rational;                 // 声明 Rational 模板

template<typename T>                                    // 声明辅助模板
const Rational<T> doMultiply(const Rational<T>& lhs,    // 辅助函数模板
                             const Rational<T>& rhs);   
{
  return Rational<T>(lhs.numerator() * rhs.numerator(),   // 返回两个有理数的乘积
                     lhs.denominator() * rhs.denominator());
}



template<typename T>
class Rational {
public:
  ...

friend
  const Rational<T> operator*(const Rational<T>& lhs,    // 声明友元函数
                              const Rational<T>& rhs)   
  { return doMultiply(lhs, rhs); }                      // 调用辅助函数
  ...
};

请记住

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

47.Use traits classes for information about types.

在 C++ 标准模板库（STL）中，迭代器（iterators）用于遍历容器中的元素。迭代器是 STL 的核心组件，它们根据不同的特性被分为多个类别。以下是一些主要的迭代器类别：

输入迭代器（Input Iterators）：
- 只能向前遍历。
- 只能读取元素的值。
- 只能读取元素的值一次。
- 不能修改元素。
- 不能跳过元素。
输出迭代器（Output Iterators）：
- 只能向前遍历。
- 只能写入元素的值。
- 只能写入元素的值一次。
- 不能读取元素。
- 不能跳过元素。
前向迭代器（Forward Iterators）：
- 具有输入迭代器和输出迭代器的功能。
- 可以向前遍历。
- 可以读取元素的值。
- 可以修改元素的值。
- 不能跳过元素。
双向迭代器（Bidirectional Iterators）：
- 具有前向迭代器的功能。
- 可以向前和向后遍历。
- 可以读取元素的值。
- 可以修改元素的值。
- 可以跳过元素。
随机访问迭代器（Random Access Iterators）：
- 具有双向迭代器的功能。
- 可以进行任意顺序的访问。
- 可以读取元素的值。
- 可以修改元素的值。
- 可以跳过元素。
- 可以进行算术运算（加减乘除）。

我们想实现advance：将迭代器移动某个给定距离。

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 是否为random access 迭代器，也就是说需要知道类型IterT 是否为random access 迭代器分类。

如果我们想对每个类型进行运行前判断，使用前面的方法需要进行多次判断,且类型判断发生在运行期而不是编译期。

我们可以通过traits class将此改为只进行一次判断并将类型判断转为编译期。

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("Negative distance");    // 抛出异常
  }
  while (d--) ++iter;                                 // 正向移动
}


template<typename IterT, typename DistT>
void advance(IterT& iter, DistT d)
{
  doAdvance(                                              
    iter, d,                                              
    typename                                            
      std::iterator_traits<IterT>::iterator_category()    
  );        //调用不同版本的iterator                                              
}

现在我们可以总结如何使用一个traits class了：

建立一组重载函数（身份像劳工）或函数模板（例如doAdvance) ，彼此间的差异只在于各自的traits 参数。令每个函数实现码与其接受之traits 信息相应和。
建立一个控制函数（身份像工头）或函数模板（例如advance) ，它调用上述那些“劳工函数”并传递traits class 所提供的信息。

请记住

Traits classes 使得“类型相关信息”在编译期可用。它们以templates 和“templates特化”完成实现。
整合重载技术(overloading) 后， traits classes 有可能在编译期对类型执行if… else 测试。

48. Be aware of template metaprogramming.

Template metaprogramming （TMP, 模板元编程）是编写template-based C+＋程序并执行于编译期的过程。花一分钟想想这个：所谓template metaprogram （模板元程序）是以C+＋写成、执行于C+＋编译器内的程序。一旦TMP 程序结束执行，其输出，也就是从templates 具现出来的若干C+＋源码，便会一如往常地被编译。

//TODO

请记住

Template metaprogramming (TMP, 模板元编程）可将工作由运行期移往编译期，因而得以实现早期错误侦测和更高的执行效率。
TMP 可被用来生成“基于政策选择组合” (based on combinations of policy choices) 的客户定制代码，也可用来避免生成对某些特殊类型并不适合的代码。