7 模板与泛型编程

• 条款41：了解隐式接口和编译期多态
• 条款42：了解typename的双重意义
• 条款43：学习处理模板化基类内的名称
• 条款44：将与参数无关的代码抽离templates
• 条款45：运用成员函数模板接受所有兼容类型
• 条款46：需要类型转换时请为模板定义非成员函数
• 条款47：请使用traits classes表现类型信息
• 条款48：认适template元编程

C++
templates的最初发展动机很直接：让我们得以建立type-sfae的容器（vector、list、map等）。后来发现templates有能力完成愈多可能的变化。泛型编程（generic
programming）——写出的代码和其所处理的对象类型彼此独立（for_each、find、merge等）。最终人们发现C++
template机制自身是完整的图灵机（Turing-complete）。于是导出模板元编程（template
metaprogramming），创造出在C++编译器内执行并于编译完成时停止执行的程序。

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

1. 面向对象编程世界总是以显示接口（explicit interfaces）和运行期多态（runtime polymorphism）解决问题。

   class Widget 
   {
   public:
       Widget();
       virtual ~Widget();
       virutal 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);
       }
   }

   template及泛型编程的世界，显式接口和运行期多态仍然存在，但重要性降低。反倒是隐式接口（implicit interfaces）和编译期多态（compile-time polymorphism）移到前头。

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

   这组表达式便是T必须支持的一组隐式接口（implicit interface）。凡涉及w相关的函数调用，如operator>和operator!=，有可能造成template具体化（instantiated），使这些调用成功，这样的具现行为发生在编译期，这就是所谓的编译期多态（compile-time polymorphism）。
2. 对classes而言接口是显式的（explicit），以函数签名为中心。多态则是通过virtual函数发生于运行期。对template参数而言，接口是隐式的（implicit），奠基于有效表达式。多态则是通过template具现化和函数重载解析（function overloading resolution）发生于编译期。

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

1. template内出现的名称如果相依于某个template参数，称之为从属名称（dependent names）。如果从属名称在class内呈嵌套状，称之为嵌套从属名称（nested dependent name），也就是嵌套从属名称并且指涉某类型；否则一个并不依赖任何template参数的名称。这样的名称是非从属名称（non-dependent names）。
2. 任何当你想要在template中指涉一个嵌套嵌套类型名称，必须在它的前一个位置放上关键字typename。这一规则的例外是，typename不可以出现在base classes list内的嵌套从属类型名称之前，也不可在member initialization list中作为base class修饰符。例如：

   // base class list中不允许typename
   template<typename T>
   class Derived : public Base<T>::Nested 
   {
   public:
       // mem init list中不允许typename
       expliit Derived(int x) : Base<T>::Nested(x) //
       {
           // 既不在base class list中也不在mem init list中，需要加上typename
           typename Base<T>::Nested temp;
           ...
       }
       ...
   };
   
   template<typename IterT>
   void workWithIterator(IterT iter)
   {
       // traits class相当于类型为IterT对象所指对象的类型，如果IterT是list<string>::iterator, temp的类型就是string
       typename std::iterator_traits<IterT>::value_type temp(*iter);
       ...
   }

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

1. 以下代码编译时出错：

   template<typename T>
   class base
   {
   public:
       void printBase() { std::cout << "base" << std::endl; }
   };
   template<typename T>
   class derived : public base<T>
   {
   public:
       void printDerived() 
       {
           std::cout << "derived" << std::endl;
           printBase();
       }
   };

   问题在于当编译器遭遇class template derived定义式时，并不知道它继承什么样的class，它不知道T是个template参数，不到后来具现化无法确切知道它是什么。而不知道T是什么，也就不知道class base看起来像什么。
2. 针对某个类产生一个特化版，需要在class定义式最前头加上“template<>”。这就是所谓的模板全特化（total template specialization）。对于某个被特化的base class templates，那个特化版本可能不提供和一般性template相同的接口，因此它往往拒绝在templatized base classes（模板化基类）内寻找继承而来的名称。就某种意义上来说，从Object Oriented C++跨进Template C++就不是畅通无阻了。

   // example
   template<> 
   class A<int>
   {
   public:
       printBase() 
       {
           std::cout << "A::int special" << std::endl;
       }
   };

3. 为了进入templatized base classes，有三个办法：
   • 第一是在调用base class函数动作之前加上“this->”

     this->printBase();

   • 第二是使用using声明式。

     using A<T>::printBase();

   • 第三种是明白指出调用的函数位于base class内。

     A<T>::printBase();

     这是最不让人满意的揭发，如果被调用的是virtual函数，上述的明确资格修饰（explicit qualification）会关闭“virtual绑定行为”。

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

1. 举个例子，用固定尺寸的正方矩阵编写一个template：

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

   这个template接受一个类型参数T，还接受一个size_t的参数，这是非类型参数（non-type parameter）。这些函数并非完全相同，除了常量5和10的区别外完全相同，这就是template引出代码膨胀的经典例子。改进方式：

   template<typename T>
   class SquareMatrixBase
   {
   protected:
       SquareMatrixBase(std::size_t n, T *pMem) : size(n), pData(pMem) {}
       void setDataPtr(T *ptr) { pData = ptr; }
       ...
   private:
       std::size_t size;
       T *pData;
   }
   
   template<typename T, std::size_t n>
   class SquareMatrix : private SquareMatrixBase<T>
   {
   public:
       SquareMatrix() : SquareMatrixBase<T>(n, data) {}
       ...
   private:
       T data[n * n];
   }
   
   // 动态分配办法
   template<typename T, std::size_t n>
   class SquareMatrix : private SquareMatrixBase<T>
   {
   public:
       SquareMatrix() : SquareMatrixBase<T>(n, 0), pData(new T[n * n])
       { this->setDataPtr(pData.get()); }
       ...
   private:
       boost::scoped_array<T> pData; // std::array??
   }

2. 这个条款讨论的是non-type template parameters（非类型模板参数）带来的膨胀，其实type parameters（类型参数）也会导致膨胀。因此凡templates持有指针者应该对每个成员函数使用唯一一份底层实现。这意味着实现某些成员函数操作强型指针（strongly typed pointers，即T*），令它们调用无类型指针（untyped pointers，即void*）的函数。
3. 因非类型模板参数而造成的代码膨胀，往往可消除，做法是以函数参数或class成员变量替换template参数。因类型参数而造成的代码膨胀，往往可降低，做法是让带有完全相同二进制表述（binary representations）的具体类型（instantiation types）共享实现码。

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

1. 智能指针（Smart pointers）是“行为像指针“的对象，提供指针没有的机能。真实的指针支持隐式转换（inplicit conversions）。而用户自定义的智能指针模拟转换有点麻烦：

   class Top { ... };
   class Middle : public Top { ... };
   class Bottom : public Middle { ... };
   
   template<typename T>
   class SmartPtr
   {
   public:
       // 以other的heldPtr初始化this的heldPtr
       tempalte<typename U>
       SmartPtr(const SmartPtr<U> &oher) : heldPtr(other.get()) { ... }
       T* get() const { return heldPtr; }
       ...
   private:
       T* heldPtr;
   };

   根据对象u创建对象t，根据SmartPtr<U>创建SmartPtr，同一个template不同具现体称为泛化（generalized）copy构造函数。以上使用member initialization list来初始化SmartPtr<t>内类型为T的成员变量，并以类型为U的指针为初值。
2. 成员函数模板作用不限于构造函数。TR1的shared_ptr支持所有兼容它的内置指针、shared_ptrs、auto_ptrs、week_ptrs的构造行为以及赋值作用：

   template<class T>
   class shared_ptr
   {
   public:
       // copy构造函数
       shared_ptr(shared_ptr const &r);
       // copy assignment
       shared_ptr& operator=(shared_ptr const &r);
       
       // 任何兼容的内置指针
       template<class Y>
       explicit shared_ptr(Y *p);
       
       // shared_ptr
       template<class Y>
       shared_ptr(shared_ptr<Y> const &r);
       
       // week_ptr
       template<class Y>
       explicit shared_ptr(week_ptr<Y> const &r);
       
       // auto_ptr
       template<classs Y>
       explcit shared_ptr(auto_ptr<Y> &r);
       
       // 赋值
       template<class Y>
       shared_ptr& operator=(shared_ptr<Y> const &r);
       template<class Y>
       shared_ptr& operator=(auto_ptr<Y> &r);
       ...
   }

   在class内声明泛型copy构造函数（member template）并不会阻止编译期生成它们自己的copy构造函数（一个non-template）。

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

1. 参考条款24：

   template<typename T>
   class Rational
   {
   public:
       Rational(const T &numerator = 0, const T &denominator = 1);
       const T numerator() const;
       const T denominator() const;
       ...
   };
   template<typename T>
   const Rational<T> operator*(const Rational<T> &lhs, const Rational<T> &rhs)
   { ... }
   
   Rational<int> oneHalf(1, 2);        // 这个例子来自条款24
   Rational<int> result = oneHalf * 2; // 错误，无法通过编译。

   它给我们的启示是，模板化的Rational内的某些东西似乎和其non-template版本不同。编译期不知道它要调用哪个函数。operator*的第一个参数被声明为Rational<T>，而传递给operator*的的第一个实参的类型是Rational<int>，所以T是int。operator*的第二参数被声明为Rational，但传递给operator*的第二实参的类型是int。你期望编译器使用Rational<int>的non-explicit构造函数将2转换为Rational<int>，但它不这么做。template实参推导过程中并不考虑采纳”通过构造函数而发生的“隐式类型转换。
2. 只要利用一个事实，可以缓和编译器在template实参推导方面受到的挑战：template class内的friend声明式可以指涉某个特定函数。class templates并不依赖template实参推导（后者只施行于function templates身上），所以编译器总是能够在class Rational具现化时得知T。令Rational class声明适当的operator*为其friend函数，可简化整个问题：

   template<typename T>
   class Rational
   {
   public:
       ...
       // 为了让这个函数自动具现化，在class内声明non-member函数的唯一方法是让它称为一个friend
       friend const Rational operator*(const Rational &lhs, const Rational &rhs)
       {
           return Rational(lhs.numerator() * rhs.numerator(), lhs.denominator() * rhs.denominaotr());
       }
   };
   
   // 为了让类型转换可能发生于所有实参身上，其实这个函数可以当作friend函数的辅助函数
   template<typename T>
   const Rational<T> operator*(const Rational<T> &lhs, const Rational<T> &rhs)
   { ... }

   现在对operator*的混合式调用可以通过编译了，因为当对象oneHalf被声明为一个Rational<int>，class Rationao<int>就被具化出来，friend函数也就被自动声明出来（这里的Rational<T>可以省略）。后者身为一个函数而非函数模板，因而编译器在调用它时使用隐式转换函数。

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

1. STL迭代器有5种分类，每类迭代器之间都是继承关系：

   // input迭代器只能向前移动，一次一步，只可读取，只能读一次。如istream_iterator
   struct input_iterator_tag {};
   // output迭代器一切只为输出，它向前移动，一次一步，只能涂写一次。如ostream_iterator
   struct output_iterator_tag {};
   // 这两类只能向前移动，而且只能读或写一些，它们只适合”一次性操作算法“（one-pass algorithms）。
   
   // forward迭代器可以读或写多次，可施行于多次行操作算法（multi-pass algorithms）。
   struct forward_iterator_tag : public input _iterator_tag {};
   
   // bidirectional迭代器除了可以向前移动，还可向后移动（set、multiset、map和multimap
   struct bidirectional_iterator_tag : public forward_iterator_tag {};
   
   // random access迭代器除了可以向前向后，还可随机访问
   struct random_access_iterator_tag : public bdirectional_iterator_tag {};

2. STL中有个工具性template，叫advance，用来将某个迭代器移动若干给定距离：

   // 所有工作都运行期，这这个typeid-based解法比traits解法效率低
   // 48条款
   templaet<typename IterT, typename DistT>
   void advance(IterT &iter, DistT d)
   {
       if (iter i a random access iterator) {
           iter += d;
       } else {
           if (d >= 0) { while (d--) ++iter; }
           else { while (d++) --iter; }
       }
   }

   为了处理迭代器分类的相关信息，我们需要traits来在编译期间取得某些类型信息，而traits技术必须对内置（built-in）类型和用户自定义（user-defined）类型一样有效运行。这样的template在STL中有若干个，其中针对迭代器的有iterator_traits。
   它的运作方式是，它首先要求每个用户自定义的迭代器类型嵌套一个typedef，名为iterator_category，用来确认适当的卷标结构（tag struct）。
   例如，针对deque和双向list：

   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;
           ...
       };
       ...
   };
   
   // iterator_traits只是鹦鹉学舌
   template<typename IterT>
   struct iterator_traits
   {
       typedef typename IterT::iterator_category iterator_category;
       ..
   };

   这对用户自定义类型行得通，对指针（也是一种迭代器）行不通。为了支持指针迭代器，iterator_traits针对指针类型提供了一个偏特化版本（partial template specialization）：

   // iterator_traits的偏特化版本
   template<typename IterT>
   struct iterator_traits<IterT*>
   {
       typedef random_access_iterator_tag iterator_category;
       ...
   };

   有了std::iterator_traits后，可以对advance践行之前的伪码了，而为了接受不同类型的iterator_category对象，则需要重载（overloading）：

   // random access迭代器
   template<typename IterT, typenmae DistT>
   void doAdvance(IterT &iter, DistT d, std::random_access_iterator_tag)
   {
       iter += d;
   }
   
   // bidirectional迭代器
   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; }
   }
   
   // input迭代器
   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;
   }
   
   /* 有了doAdvance重载版本，advance做的只是调用它们并传递对象
   */
   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))
       */
       doAdvance(iter, d, typename std::iterator_traits<IterT>::iterator_category());
   }

3. STL中除了Iterator_traits供应iterator_category还供应另外四种迭代器：value_type、char_traits、numeric_limits等。STL中还有很多其他新的traits classes用以提供类型信息，如is_fundamental<T>（判断T是否为内置类型），is_array<T>（判断T是否为数组类型）以及is_base_of<T1, T2>（T1和T2相同，或T1是T2的base class）。

条款48：认适template元编程

1. Template metaprogramming(TMP，模板元编程)是编写template-based C++程序并执行于编译器的过程。
2. 47条款中的伪码部分：

   // 面对某些自定义类型，会编译失败
   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 {
           if (d >= 0) { while (d--) ++iter; }
           else { while (d++) --iter; }
       }
   }

3. TMP已被证明是”图灵完全“（Turing-complete）机器，针对TMP而涉及的程序库提供了更高级的语法。TMP并没有真正的循环结构，所有的循环效果都是由递归（recursion）完成。TMP主要是个函数时语言（functional language），而递归在这类语言是无法分割的，TMP循环并不涉及递归函数调用，而是涉及”递归模板具现化“（recursive template instantiation）。以下是示例源码：

   // 一般情况下
   template<unsigned n>
   struct Factorial {
       enum { value = n * Factorial<n - 1>::value };
   };
   // 特殊情况下，当到0时
   template<>
   struct Factorial<0> {
       enum { value = 1 };
   };

4. TMP能够达到什么目标呢：
   1. 确保度量单位正确。在科学和工程应用程序中，可以用TMP确保在编译期时确保所有度量单位组合正确，防范于未然。
   2. 优化矩阵运算。
   3. 生成用户定制之设计模式（custom design pattern）实现品。这项技术已被用来让若干templates实现出智能指针的行为策略（behavioral policies），用来在编译期间生成数以百计不同的智能指针类型。这项技术超越编程工艺如设计模式和智能指针，更广义成为generative programming（殖生式编程）的一个基础。