旭穹の陋室

本文是阅读《Effective C++ 改善程序与设计的55个具体做法（第三版）》的心得笔记第六部分，文章也会按照原书的顺序依次记录各个条款。

第一部分的阅读笔记参见effective C++ 读书笔记01。

第二部分的阅读笔记参见effective C++ 读书笔记02。

第三部分的阅读笔记参见effective C++ 读书笔记03。

第四部分的阅读笔记参见effective C++ 读书笔记04。

第四部分的阅读笔记参见effective C++ 读书笔记05。

模板与泛型编程

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

classes和templates都支持接口（interfaces）和多态（polymorphism）。

对于classes而言，接口是显式的，多态是通过virtual函数实现的运行期多态：

• 显式接口由函数签名式（函数名称、参数类型、返回类型）构成，在源码中是明确可见的；
• 运行期多态基于virtual函数实现，具体调用哪一个virtual函数的重写，将在运行期根据对象的动态类型决定；

对于Templates而言，接口时隐式的，多态则是通过template具现化和函数重载解析（function overloading resolution）实现的编译期多态：

• 隐式接口由有效表达式构成，模板类型不定，且考虑上运算符重载等特性，隐式接口的自由度很大；
• 编译期多态，在调用template函数是传入不同的类型T，会得到不同的函数，这被称为template具现化，发生在编译期；

一个例子如下：

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

表面上看，上述隐式接口对类型T有如下约束：

1. 必须提供一个size方法，该方法返回一个整数值；
2. 必须支持一个operator!=操作符，用来比较两个T对象。这里假设someNastyWidget的类型为T。

但实际上，隐式接口的灵活度要更大，比如：

1. T提供的size成员方法可以从基类继承而得；
2. size方法返回的值类型不必是整数，甚至不必是数值类型。而可以是一个对operator>做了操作符重载（可以与整型比较）的类型X，甚至是可以隐式转换为类型X的类型Y；
3. 同理，T并不需要支持operator!=，可以是这样：operator!=接受一个类型为X的对象和一个类型为Y的对象，而T可以转换为X，someNastyWidget可以转换为Y。

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

• 在声明模板参数时，前缀关键字class和typename没有区别，如下：

template <class T> class A;
template <typename T> class A;	// 没有区别

• 使用typename标识嵌套从属类型名称。

首先明确一下如下几个概念：

1. 从属名称（dependent names）：template内出现的名称, 相依于某个模板参数, 如T t;；

2. 嵌套从属名称（nested dependent names）：从属名称在嵌套在模板参数所代表的类内，如T::const_iterator ci;；

3. 嵌套从属类型名称（nested dependent type names）：嵌套从属名称指涉的为某类型；

4. 非从属名称（non-dependent names）：template中不依赖于任何模板参数的名称，如int a;；

嵌套从属名称的解析可能存在歧义，如下例所示：

template <typename T>
void doSomething(const T& container) {
    T::const_iterator* x;		// 不合法！！！
    ...
}

即便我已提前知道T::const_iterator是一个类型，而x为该类型的指针变量，但这样的表示并不合法。因为在确定T究竟为何种类型之前，编译器无法断定T::const_iterator是一个类型，它还可能是T中的一个static成员变量，而x是某个全局变量，那上述表达式就构成了一个乘法操作。

C++解决这一歧义状态的规定是：缺省状态下，嵌套从属名称不是类型，除非你用typename作为前缀进行标识。

template <typename T>
void doSomething(const T& container) {
    typename T::const_iterator* x;		// 合法
    ...
}

typename只能用来标识嵌套从属名称，而不能用于其他名称。使用范围除了函数内部，还可以用于函数入参。

template <typename T>
void f(const T& container,				// 不允许使用typename
      typename T::iterator iter);		// 一定要使用typename

上述的规定存在一个例外情况，在继承的基类列表和成员初始化列表中的嵌套从属类型名称不需要typename作为前缀修饰符。因为这时，嵌套从属名称默认就是一种类型（不存在歧义）。

template <typename T>
class Derived: public Base<T>::Nested {		// 基类列表，不用typename
public:
    explicit Derived(int x)
        : Base<T>::Nested(x) {				// 初始化列表，不用typename
            typename Base<T>::Nested temp;	// 嵌套从属类型名称，要用typename
        	...
        }
    ...
};

此外，当typename修饰的类型名称过长时，可以结合typedef一起使用。

#include <vector>
template <typename IterT>
void workWithIterator(IterT iter) {
    //typename std::iterator_traits<IterT>::value_type temp(*iter);
    typedef typename std::iterator_traits<IterT>::value_type value_type;
    value_type temp(*iter);

std::cout << temp << std::endl;
}

int main() {
    std::vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);

workWithIterator(vec.begin());
    workWithIterator(vec.end() - 1);

return 0;
}

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

所谓模板化基类，即定义某模板类时，继承于另一模板类Base<T>，这个Base<T>就是模板化基类。看如下这个例子：

class CompanyA {								// 公司A
public:
    ...
	void sendClearText(const std::string& msg);	// 发送明文消息
    void sendEncrypted(const std::string& msg);	// 发送加密消息
    ...
};
class CompanyB {								// 公司B
public:
    ...
	void sendClearText(const std::string& msg);	// 发送明文消息
    void sendEncrypted(const std::string& msg);	// 发送加密消息
    ...
};
...												// 其他公司
class MsgInfo { ... };							// 保存信息，用于产生发送消息

template <typename Company>						// 模板化基类
class MsgSender {
    ...											// 构造函数，析构函数等
	void sendClear(const MsgInfo& info) {
        std::string msg;
        ...										// 根据info生成消息
		Company c;
        c.sendClearText(msg);
    }
    void sendSecret(const MsgInfo& info) {
        ...										// 与上类似，但调用c.sendEncrypted
    }
};

template <typename Company>
class LoggingMsgSender: public MsgSender<Company> {
public:
    ...											// 构造函数，析构函数等
	void sendClearMsg(const MsgInfo& info) {
        ...										// 消息发送前的log
		sendClear(info);						// 编译报错！！！
        ...										// 消息发送后的log
    }
    ...
};

上述例子中，编译器拒绝在编译时在模板化基类中主动寻找继承而来的名称。因此模板化基类可能会被特化，在特化版本中可能无法提供与一般化的模板类相同的接口。如下：

class CompanyZ {								// 该公司不支持明文发送消息
public:
    ...
	void sendEncrypted(const std::string& msg);	// 发送加密消息
	...
};

template <>
class MsgSender<CompanyZ> {						// 针对Z公司的全特化，移除了sendClear
public:
    ...
	void sendSecret(const MsgInfo& info) { ... }
};

如上例所示，当基类被指定为MsgSender<CompanyZ>时，因为其未提供sendClear函数，上述调用代码就是非法的，故C++拒绝在编译时在模板化基类中主动寻找继承而来的名称，而是直接报错。

若你能够承诺模板化基类的任何特化版本都将支持其泛化版本所提供的接口，有三种方法可以让编译器不再拒绝模板化基类中继承而来的名称：

• 使用this->调用，将转化为运行时问题，推荐；

template <typename Company>
class LoggingMsgSender: public MsgSender<Company> {
public:
    ...											// 构造函数，析构函数等
	void sendClearMsg(const MsgInfo& info) {
        ...										// 消息发送前的log
		this->sendClear(info);					// OK
        ...										// 消息发送后的log
    }
    ...
};

• 使用using声明式，告诉编译器所调用函数在模板化基类中；

template <typename Company>
class LoggingMsgSender: public MsgSender<Company> {
public:
    using MsgSender<Company>::sendClear;		// 明确告诉编译器sendClear的位置
    ...											// 构造函数，析构函数等
	void sendClearMsg(const MsgInfo& info) {
        ...										// 消息发送前的log
		sendClear(info);						
        ...										// 消息发送后的log
    }
    ...
};

• 显式调用，但会破坏virtual函数的动态绑定行为，不推荐；

template <typename Company>
class LoggingMsgSender: public MsgSender<Company> {
public:
    ...											// 构造函数，析构函数等
	void sendClearMsg(const MsgInfo& info) {
        ...										// 消息发送前的log
		MsgSender<Company>::sendClear(info);	// OK
        ...										// 消息发送后的log
    }
    ...
};

但如果你的承诺未能兑现，特化版本与泛化版本不同，即便你做了上述处理，在最终的编译阶段还是会报错：

LoggingMsgSender<CompanyZ> zMsgSender;
MsgInfo msgData;
...
zMsgSender.sendClearMsg(msgData);				// 编译报错！！！

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

对于非模板代码中，我们一般很容易就能区分两个函数或者类中的重复部分，并将它们提取出来；但是在模板代码中，重复是隐晦的，一些不恰当的设计，会导致模板在多次被具现化的时候产生代码重复，而这不是那么容易能够感知的。考虑如下这个例子：

template <typename T, 			// 正方矩阵元素类型为T
			std::size_t n>		// 正方矩阵尺寸为n x n
class SquareMatrix {
public:
    ...
	void transpose();			// 支持转置操作
};

在上述例子中，模板类SquareMatrix接受一个类型参数T（常见）和一个非类型参数n（不常见，但合法）。我们可能会有如下的调用代码：

SquareMatrix<double, 5> sm1;
...
sm1.transpose();

SquareMatrix<double, 10> sm2;
...
sm2.transpose();

模板类被具现化成两个类，同时其成员函数transpose也被具现化成两份，虽然这两份函数实现不完全相同，却也只有矩阵尺寸n的差异，还是存在代码重复。想要规避这无谓的代码膨胀，和非模板代码中的考虑类似，我要将与参数无关的代码抽离。一个实现如下：

template <typename T>
class SquareMatrixBase {
protected:
    SquareMatrixBase(std::size_t n, T* dataPtr) : n_(n), dataPtr_(dataPtr) {
    }
    void baseTranspose();
    void setDataPtr(T* dataPtr) {
        dataPtr_ = dataPtr;
    }
    void basePrint() {
        for (int i = 0; i < n_; ++i) {
            for (int j = 0; j < n_; ++j) {
                std::cout << dataPtr_[i * n_ + j] << ",";
            }
            std::cout << std::endl;
        }
    }

private:
    std::size_t n_;
    T* dataPtr_;
};

template <typename T>
void SquareMatrixBase<T>::baseTranspose() {
    std::cout << "do transpose: pData = " << dataPtr_ << " , size = " << n_ << std::endl;
    for (int i = 0; i < n_; ++i) {
        for (int j = 0; j < i; ++j) {
            std::swap(dataPtr_[i * n_ + j], dataPtr_[j * n_ + i]);
        }
    }
}

template <typename T, std::size_t n>
class SquareMatrix : private SquareMatrixBase<T> {
public:
    SquareMatrix() 
        : SquareMatrixBase<T>(n, nullptr), 
    	  pData_(std::shared_ptr<T>(new T[n * n])) {
        this->setDataPtr(pData_.get());
    }
    void transpose() {
        this->baseTranspose();
    }
    void setData(T* data) {
        memcpy(pData_.get(), data, n * n * sizeof(T));
    }
    void print() {
        this->basePrint();
    }

private:
    std::shared_ptr<T> pData_ = nullptr;
};

int main() {
    SquareMatrix<int, 3> sm1;
    int mat[3 * 3] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    sm1.setData(mat);
    sm1.print();
    sm1.transpose();
    sm1.print();

return 0;
}

在上述例子中，实现了一个与尺寸无关的模板化基类，其只对矩阵元素类型参数化，不对矩阵尺寸参数化，所以对于同一元素类型的所有尺寸的具现化矩阵类，都共享同一个成员函数baseTranspose，因此避免了代码重复。此外上述例子还有几个需要注意的点：

• SquareMatrix类是private继承SquareMatrixBase类，这表明两者只是实现意义上的复合关系，而不是is-a关系，基类中希望被派生类继承（又不希望被外部访问）的接口被声明为protected；
• SquareMatrixBase类持有两个操作数据时用到的成员变量：矩阵数据指针dataPtr_和矩阵尺寸n_，由派生类负责对它们进行初始化，且基类本身并不负责管理资源的申请和销毁，只是有访问权限；
• SquareMatrix类中对基类方法的调用采用隐式inline调用（参见条款30），从而调用的额外成本为0；
• 对模板化基类中的成员函数名称，需要使用this->进行调用（参见条款43）；
• 如此实现有利有弊，好处在于代码空间变小，其占用的虚拟内存的分页大小也减少，还会减少指令Cache的Cache Miss的概率，这些都可能提高程序执行的效率；但另一方面，基类中的baseTranspose函数的尺寸不定，编译器优化（效率）的程度可能不如尺寸确定的具现化版本。至于两者的影响谁占主导？只能实测确定。

上面例子只讨论了有非类型参数带来的代码膨胀，其实类型参数也可能会导致代码膨胀。比如在许多平台上，int和long有相同的二进制表述，所以vector<int>和vector<long>的成员函数有可能完全相同，某些链接器可能会合并完全相同的实现码，但有些不会；再比如，在大多数平台上，所有指针类型都有相同的二进制表述，因此若模板持有指针的（如list<int*>，list<SquareMatrix<long, 3>*>等）往往应该对每一个成员函数使用唯一一份底层实现。一个常用的方法就是：若你的某些成员函数操作强数据类型指针T*，那就应该令它们调用另一个操作无类型指针void*的函数，由后者完成实际工作。

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

众所周知，裸指针是支持隐式转换的，例如派生类指针可以隐式转换为基类指针，指向non-const对象的指针可以转换为指向const对象的指针。一个继承体系的示例如下：

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类对基类和派生类的具现化本身并不带有继承关系。所谓额外的配置就是实现成员（构造）函数模板，接受所有兼容类型的泛化copy构造和泛化copy赋值（之所以使用函数模板，是因为继承体系未来有可能扩充，我们不可能对每一对继承关系都实现出一组构造函数）。一个例子如下：

#include <typeinfo>

class Top {};
class Middle : public Top {};
class Bottom : public Middle {};

template <typename T>
class SmartPtr {
public:
    explicit SmartPtr(T* rawPtr) : rawPtr_(rawPtr) {  	// 普通构造，以裸指针初始化
        std::cout << "constructor: " << typeid(rawPtr).name() << std::endl;
    }

SmartPtr(const SmartPtr& sp) : rawPtr_(sp.get()) {  // 普通copy构造，简单演示，浅拷贝
        std::cout << "copy constructor: " << typeid(sp).name() << " to " << typeid(*this).name() << std::endl;
    }

SmartPtr& operator=(const SmartPtr& sp) {  	// 普通copy赋值操作符，简单演示，浅拷贝
        std::cout << "copy assignment operator: " << typeid(sp).name() << " to " << typeid(*this).name() << std::endl;
        rawPtr_ = sp.get();
        return *this;
    }

template <typename U>  						// 泛化copy构造，简单演示，浅拷贝
    SmartPtr(const SmartPtr<U>& other) : rawPtr_(other.get()) {
        std::cout << "generic copy constructor: " << typeid(other).name() << " to " << typeid(*this).name() << std::endl;
    }

template <typename U>  						// 泛化赋值操作符，简单演示，浅拷贝
    SmartPtr& operator=(const SmartPtr<U>& other) {
        std::cout << "generic copy assignment operator: " << typeid(other).name() << " to " << typeid(*this).name() << std::endl;
        rawPtr_ = other.get();
        return *this;
    }

T* get() const {
        return rawPtr_;
    }
    ~SmartPtr() {
    }

private:
    T* rawPtr_ = nullptr;
};

int main() {
    // 1. 
    // structor: class Middle * __ptr64
    // generic copy constructor: class SmartPtr<class Middle> to class SmartPtr<class Top>
    SmartPtr<Top> pt1 = SmartPtr<Middle>(new Middle); 

// 2. 
    // structor: class Bottom * __ptr64
	// eric copy constructor: class SmartPtr<class Bottom> to class SmartPtr<class Top>
    SmartPtr<Top> pt2 = SmartPtr<Bottom>(new Bottom);

// 3. 
    // generic copy constructor: class SmartPtr<class Top> to class SmartPtr<class Top const >
    SmartPtr<const Top> cpt3 = pt1;

// 4. 
    // 编译不通过
    // SmartPtr<Middle> pt4 = SmartPtr<Top>(new Top); 

// 5. 
    // constructor: class Top * __ptr64
    SmartPtr<Top> pt4(new Top);
    // copy constructor: class SmartPtr<class Top> to class SmartPtr<class Top>
    SmartPtr<Top> pt5(pt4);

delete pt1.get();	// 浅拷贝未约定所有权是否转移，由外部管理释放
    delete pt2.get();
    delete pt5.get();

return 0;
}

在上述例子中，有如下几点需要注意：

• 泛化拷贝构造函数和泛化拷贝赋值操作符并没有被声明为explicit。这是有意为之，因为裸指针之间是可以进行隐式转换的，所以让智能指针也效仿这种行为是无可厚非的；
• 上述转换操作并非对任意类型转换都兼容，我们其实通过成员初始化列表rawPtr_(other.get())或赋值操作rawPtr_ = other.get();对可以进行智能指针转换的类型做了约束，即只有当存在某种隐式转换可以将一个U*指针（other.get()）转换为T*指针（rawPtr_）时，代码才能通过编译。例如，我们无法将一个Top指针隐式转换为Middle指针，故上述智能指针的泛化构造也不支持该转换（上述case4）；
• 成员函数模板并没有改变语言规则，即泛化拷贝构造函数不能代替普通的拷贝构造函数。如果程序需要一个普通的拷贝构造函数（如上例case5），而你没有显式提供，则编译器也会生成一个缺省的版本。对拷贝赋值操作符也是如此。

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

在条款24中提到，使用non-member函数来为所有实参提供隐式类型转换的能力，并以Rationnal类的operator*函数为例进行了讨论。在本条款中，我们将Rational类和operator*进行模板化，看看原来的解决方案是否还适用：

// 有理数类模板
template <typename T>
class Rational {
public:
    Rational(const T& numerator = 0, const T& denominator = 1) : numerator_(numerator), denominator_(denominator) {
    }

const T numerator() const {
        return numerator_;
    }
    const T denominator() const {
        return denominator_;
    }

private:
    T numerator_ = 0;
    T denominator_ = 1;
};

template <typename T>
const Rational<T> operator*(const Rational<T>& lhs, const Rational<T>& rhs) {
    return Rational<T>(lhs.numerator() * rhs.numerator(), lhs.denominator() * rhs.denominator());
}

int main() {
    Rational<int> oneHalf(1, 2);
    Rational<int> oneEighth(1, 8);
    Rational<int> res1 = oneHalf * oneEighth;	// OK
    Rational<int> res2 = oneHalf * 2;			// NG，编译错误
}

混合运算时，类的non-member函数似乎并没有提供实参隐式转换的能力。这是由于函数模板在具现化时需要做实参推导，以确定T究竟是什么。而在该推导过程中，是不会考虑通过构造函数而发生的隐式类型转换的（这样的隐式类型转换在函数调用过程中确实会被使用，但在调用该函数之前，得首先知道该函数是否存在，否则就是无限套娃）。在上例中，虽然2可以通过non-explicit构造函数隐式转换成Rational<int>，但在实参推导时，我们不能这么做。

这时，我们如果把operator*函数模板声明为Rational类的友元，则可以通过编译（但链接不成功）：

// 有理数类模板
template <typename T>
class Rational {
public:
    Rational(const T& numerator = 0, const T& denominator = 1) : numerator_(numerator), denominator_(denominator) {
    }

const T numerator() const {
        return numerator_;
    }
    const T denominator() const {
        return denominator_;
    }

// friend const Rational<T> operator*(const Rational<T>& lhs, const Rational<T>& rhs);
    friend const Rational operator*(const Rational& lhs, const Rational& rhs);

private:
    T numerator_ = 0;
    T denominator_ = 1;
};

template <typename T>
const Rational<T> operator*(const Rational<T>& lhs, const Rational<T>& rhs) {
    return Rational<T>(lhs.numerator() * rhs.numerator(), lhs.denominator() * rhs.denominator());
}

int main() {
    Rational<int> oneHalf(1, 2);
    Rational<int> oneEighth(1, 8);
    Rational<int> res1 = oneHalf * oneEighth;
    Rational<int> res2 = oneHalf * 2;			// NG，链接错误

return 0;
}

之所以能通过编译，是利用了类模板的具现化并不需要实参推导，故编译器总是能在class Rational<T>具现化的时候确定T。具体到上例，在oneHalf被声明为Rational<int>时，class Rational<int>就被具现化出来，从而作为类的一部分，friend函数operator*（接受Rational<int>参数）也会被自动声明。

之所以不能通过链接，是因为类在具现化时，需要找到该friend函数的定义实现，若在类外定义，该函数模板还未具现化，即找不到具体的实现。解决方法也很简单，将函数实现以inline方式合并到声明式中：

// 有理数类模板
template <typename T>
class Rational {
public:
    Rational(const T& numerator = 0, const T& denominator = 1) : numerator_(numerator), denominator_(denominator) {
    }

const T numerator() const {
        return numerator_;
    }
    const T denominator() const {
        return denominator_;
    }

// friend const Rational<T> operator*(const Rational<T>& lhs, const Rational<T>& rhs);
    friend const Rational operator*(const Rational& lhs, const Rational& rhs) {
        return Rational<T>(lhs.numerator() * rhs.numerator(), lhs.denominator() * rhs.denominator());
    }

private:
    T numerator_ = 0;
    T denominator_ = 1;
};

int main() {
    Rational<int> oneHalf(1, 2);
    Rational<int> oneEighth(1, 8);
    Rational<int> res1 = oneHalf * oneEighth;
    Rational<int> res2 = oneHalf * 2;			// OK
    Rational<int> res3 = 2 * oneHalf;			// OK

return 0;
}

这个解决方法的有趣点在于，虽然使用了friend，但却与friend的传统用途访问class的non-public部分毫不相干。而是基于如下逻辑：为了能让隐式类型转换发生在所有实参上，我们需要一个non-member函数（模板）；为了让这个函数（模板）能被自动具现化，我们需要将其声明在class内部；而在class内部声明non-member函数的唯一办法就是让它成为一个友元。

其中关于类中的operator*的声明式和定义式的语法，template名称写成Rational和Rational<T>均可，因为template名称可以被作为template及其参数的简略表达形式。

假如friend函数的实现更为复杂，此时希望inline声明带来的冲击最小化，以及代码可读性的提升，可以将具体实现封成一个辅助函数，如下：

// 有理数类模板
template <typename T>
class Rational {
public:
    Rational(const T& numerator = 0, const T& denominator = 1) : numerator_(numerator), denominator_(denominator) {
    }

const T numerator() const {
        return numerator_;
    }
    const T denominator() const {
        return denominator_;
    }

// friend const Rational<T> operator*(const Rational<T>& lhs, const Rational<T>& rhs);
    friend const Rational operator*(const Rational& lhs, const Rational& rhs) {
        return doMultiply(lhs, rhs);
    }

private:
    T numerator_ = 0;
    T denominator_ = 1;
};

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());
}

int main() {
    Rational<int> oneHalf(1, 2);
    Rational<int> oneEighth(1, 8);
    Rational<int> res1 = oneHalf * oneEighth;
    Rational<int> res2 = oneHalf * 2;
    Rational<int> res3 = 2 * oneHalf;

return 0;
}

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

C++ 中通常把 Traits 称为类型萃取技术，即：在 template 编程中，获取模板参数的类型信息，并在编译阶段针对不同的类型响应不同的处理。

本条款以C++ STL 库中的一个工具模板函数std::advance作为切入点进行讨论，其函数原型为：

template <typename IterT, typename DistT>
void advance(IterT& iter, DistT d);

该模板函数的作用是将某个IterT类型的迭代器iter移动某个给定距离d。在进一步讨论该函数的实现之前，我们先明确一下STL中的迭代器类型：

0. 确定若干你希望将来可取得的类型相关信息

对于这5种迭代器类型，C++ STL 库分别提供了专属的**卷标结构（tag struct）**来加以区分，卷标结构可以理解为编译期的枚举，其定义如下：

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函数的讨论，我们希望实现的效果是，函数可以基于迭代器的类型IterT不同，实现不同的移动操作，比如random access迭代器可以直接+=d，而其他迭代器只能循环++或--。这便需要用到Traits技术以在编译器获取类型信息。同时，我们还希望，Traits技术对内置类型也能有同样好的表现，比如指针也可以看作是一种迭代器，所以基于Traits技术实现的advance函数也应当兼容指针类型。

有了上述铺垫，让我们看看Traits究竟如何实现：

1. 为卷标结构（迭代器类型）选一个统一名称（iterator_category），并在使用它的类（各种容器）中嵌套typedef以指定具体的类型

例如，deque的迭代器是random access 迭代器，则deque的实现：

template < ... >		// 省略模板参数
class deque {
public:
    class iterator {
	public:
        typedef random_access_iterator_tag iterator_category;
    	...
    };
    ...
};

而list的迭代器是bidirectional 迭代器，则list的实现：

template < ... >		// 省略模板参数
class list {
public:
    class iterator {
	public:
        typedef bidirectional_iterator_tag iterator_category;
    	...
    };
    ...
};

2. 提供Traits classes（iterator_traits）和其特化版本（支持指针类型）

Traits往往被实现成struct，但是往往被称为Traits classes。iterator_traits的实现如下：

template <typename IterT>
struct iterator_traits {
	typedef typename IterT::iterator_category iterator_category;	// 参见条款42
    ...
};

iterator_traits做的事情也很简单，就是响应迭代器IterT中的嵌套typedef，即IterT自己认为iterator_category是什么，iterator_traits就认为iterator_category是什么。但是上述实现并不能支持指针类型，因为内置类型无法嵌套typedef，所以iterator_traits针对指针类型提供一个偏特化版本：

template <typename IterT>
struct iterator_traits<IterT*> {	// 偏特化，确定模板参数的一部分
    typedef random_access_iterator_tag iterator_category;	// 指针行为接近random access
};

至此，iterator_traits 完成了基本实现（C++ STL 库已提供std::iterator_traits），即 iterator_traits<IterT>::iterator_category 可以在编译期确定，接下来看看advance 函数如何使用它。

3. 利用函数重载完成编译期的类型条件判断

对iterator_traits<IterT>::iterator_category的使用的简单方法的如下：

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;
        }
    }
}

上述方法看似可行，但是实际隐含着编译问题：即便对于非random access的迭代器，iter += d;永远不可能执行到，但在编译器并不知道，它只能默认iter是支持+=的，但非random access的迭代器并不支持。所以当具体调用时具现化的IterT为非random access迭代器类型，就会出现编译错误。

除了编译问题外，if-else语句的条件判断是运行期判断，而我们所期望的是在编译阶段针对不同的类型响应不同的处理。这时我们就可以利用重载在编译阶段对不同类型进行条件判断：

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_category类型 对象
}

总结一下，对traits class 的使用方法如下：

• 建立一组重载函数或重载函数模板（身份像劳工，doAdvance），将卷标结构对象作为一个参数用于区别不同的重载函数，并令每个函数的实现码与接受的卷标结构对象相适应；
• 建立一个控制函数或函数模板（身份像工头，advance），调用上述的”劳工函数“，并传递由traits获取的类型对象；

4. others

Traits在 STL 库中有着广泛的应用：

• iterator_traits ，不止有 iterator_category，还有 difference_type， value_type， pointer， reference 4个成员，详细可参考 cpp参考手册：iterator_traits 。

• C++ STL 库中类似 iterator_traits 应用了 Traits 技术的模板还有很多，例如numeric_limits，需要包含头文件#include<limits>，可以获取数值类型的极值。

条款48：认识 template 元编程

模板元编程（TMP，template metaprogramming），是编写 template-based C++ 程序并执行于编译期的过程。TMP 过程结束后，若干 C++ 源码会被 templates 具现化出来，便会一如往常地被编译。

TMP有两大优势：

• 可以完成非 TMP 的常规编程做不到的事情，比如代码生成，类型适配等；
• 可以将某些工作从运行期转移到编译期，可以将运行期的错误提前暴露在编译期，可以获得更小的可执行文件，更快地运行，更少地内存需求，缺点是明显增加编译时间。

TMP 已被证明是个“图灵完备”的机器，意思是它强大到可以计算任何事物。使用 TMP 可以声明变量、执行循环、编写及调用函数等。但是TMP实现上述功能的方式不同于常规的C++程序，在条款47中，我们利用了重载实现编译期的 if…else 条件分支，接下来将通过编译期计算阶乘的实现，展示TMP通过递归模板具现化来是实现循环逻辑：

template <unsigned n>
struct Factorial {  // 递归的形式体现: f(n) = n * f(n -1)
    enum { value = n * Factorial<n - 1>::value };
};
template <>
struct Factorial<0> {  // 模板全特化: 实际是初始化 f(0) = 1
    enum { value = 1 };
};

int main() {
    std::cout << Factorial<5>::value << std::endl; 		// 5! = 120
    std::cout << Factorial<10>::value << std::endl;		// 10! = 3628800
}