学习STL就不得不学习iterator，我们知道STL的中心思想——将数据容器和算法分开，彼此独立设计，再以一贴胶着剂将它们撮合在一起。
对容器和算法的泛化我们可以使用class template和function template。那么，谁来充当这个“胶着剂”呢？对咯，就是iterator。
一，迭代器是一种smart pointer
（1）迭代器是一种行为类似指针的对象，而指针的各种行为中最常见也最重要的便是内容提领(dereference)和成员访问(member access)。
（2）因此，迭代器最重要的编程工作就是对operator*和operator->进行重载(overloading)工作。
（3）根据移动特性与实施操作，迭代器被分为五类(iterator_category)：
Input Iterator：只读。
Output Iterator：只写。
Forward Iterator：允许“写入型”算法（如replace()）在此种迭代器所形成的区间上进行读写操作。
Bidirectional Iterator：可双向移动，某些算法需要逆向走访某个迭代器区间。
Random Access Iterator：前四种迭代器只供应一部分指针算术能力（前三中支持operator ++, 第四种支持operator–），第五种则涵盖所有指针算术能力，包括p+n, p-n, p[n], p1-p2, p1<p2。
二，迭代器相应的类型（associated types）
（1）参数推导机制
我们知道，在算法中使用迭代器时，很可能会用到迭代器相应的类型（即迭代器所指对象的类型）。假设某个算法中需要声明一个变量，以迭代器所指对象的类型为类型，那该怎么办呢？毕竟C++只支持sizeof()，并未支持typeof()。
这里需要注意一点:上述的变量类型指的是迭代器所指对象类型，而不是迭代器类型。明白这一点，接着往下看该如何取出这个对象的类型呢？
解决办法是：利用function template的参数推导机制。我看如下示例：
（1）我们以func()为对外接口，把实际操作全部置于func_impl()之中。
（2）由于func_impl()是一个function template，一旦被调用，编译器会自动进行template参数推导。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
template <class I, class T> void func_impl(I iter, T t) { T tmp; //这里解决了问题，T就是迭代器所指之物的类型,本例为int //...这里做原本func()应该做的全部工作 }; template <class I> inline void func(I iter) { func_impl(iter, *iter); //func的工作全部移往func_impl } int main() { int i; func(&i); } |
三， Traits编程技法——STL源代码的门钥
（1）声明内嵌类型
迭代器所指对象的类型称为该迭代器的value type。上述的参数推导技巧虽然可用于value type，却非全面可用：万一value type必须用于函数的传回值，就束手无策了。毕竟template参数推导机制推而导之的只是参数，无法推导函数的返回类型。所以我们需要其他办法，申明内嵌类型可以吗？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
template <class T> struct MyIter { typedef T value_type; //内嵌类型声明 T* ptr; MyIter(T* p=0) : ptr(p) { } T& operator*() const { return *ptr; } //... }; template <class I> typename I::value_type //这一整行是func的返回类型 func(I iter) {return *ite;} //... MyIter<int> ite(new int (8)); cout << func(ite); //输出8 |
（a）func()的返回类型必须加上关键字typename，因为T是一个template参数，在编译器具体实现之前并不知道MyIter<T>::value_type代表的是类型或是member function还是data member。
（b）关键字typename的作用就是告诉编译器这是一个类型，才能顺利通过编译。
以为这就完了吗？NO, 图样图森破！
现在问题又来了，并不是所有的迭代器都是class type，原生指针就不是哦。所以，不是class type就无法定义它的内嵌类型。
但是STL必须能接受原生指针作为一种迭代器，所以上面这样还不够，我们继续往下谈（蓝色香菇）…
（2）Partial Specialization(偏特化)
什么是Partial Specialization？
Partial Specialization的大致意义是：如果class template拥有一个以上的template参数，我们可以针对其中某个（或数个，但非全部）template参数进行特化工作。换句话说，我们可以在泛化设计中提供一个特化版本（也就是将泛化版本中的某些template参数赋予明确的指定）。
比如，我们现在有如下的class template:
|
1 2 |
template <typename T> class C {...}; //这个泛化版本允许（接受）T为任何类型 |
我们便很容易的接受它的一个形式如下的partial specialization:
|
1 2 3 |
template <typename T> class C<T*> {...}; //这个特化版本仅适用于“T为原生指针”的情况 //“T为原生指针”便是“T为任何类型”的一个更进一步的条件限制 |
ok，有了这么一个东西之后，我们就能解决前面“内嵌类型”未能解决的问题了。我们现在可以针对“迭代器的template参数为指针”的情况，设计特化版的迭代器了。
（3）iterator_traits来萃取value_type
下面这个class template专门用来萃取迭代器特性，而value type正是迭代器的特性之一：
|
1 2 3 4 |
template <class I> struct iterator_traits { typedef typename I::value_type value_type; ; |
这个所谓的traits，其意义是，如果I定义有自己的value type，那么通过这个traits的作用，萃取出来的value_type就是I::value_type。换句话说，如果I定义有自己的value type，先前那个func()可以改写成这样：
|
1 2 3 |
template <class I> typename iterator_traits<I>::value_type //函数返回类型 func(I ite) { return *ite; } |
与之前的版本对比，仅仅只是加了iterator_traits这一中间层而已？其实不然，有了这一层中间层后，我们就可以在这个中间层做一些手脚了。
比如，iterator_traits可以拥有特化版本：
|
1 2 3 4 |
template <class T> struct iterator_traits<T*> { //partial specialization版本——迭代器是个原生指针 typedef T value_type; }; |
于是，原生指针int*虽然不是一种class type，也可通过traits取出其value_type。解决了前一个问题。
以为这就完了吗？NO, 图样图森破！
（4）原生指针是指向常数对象的指针（pointer-to-const）
如果指针是指向常数对象的指针，即使萃取出来之后，也无法对其进行赋值等操作也是枉然。例如：
iterator_traits <const int*>::value_type
这该怎么处理呢？
简单，我们在设计一个特化版本，直接在iterator_traits中间层将其const属性丢掉即可，具体如下：
|
1 2 3 4 |
template <class T> struct iterator_traits<const T*> { //偏特化版——当迭代器是一个pointer-to-const时 typedef T value_type; //萃取出来的类型应该是T而非const T }; |
终于大功告成，现在不管面对的是迭代器MyIter，或是原生指针int*或是const int*，都可以通过traits取出正确的value_type。
小结：参数推导机制–>声明内嵌类型–>Partial Specialization–>iterator_traits萃取出int*–>萃取const int*
最后附上traits工作机制的图，辅助理解traits的工作原理：
掌握了iterator_traits之后，我们便可以愉快的学习iterator了。
常用的迭代器类型有上图所示的五种，类似于value_type的提取，其他四种如下：
|
1 2 3 4 5 6 7 8 |
template <class T> struct iterator_traits { typedef typename I::iterator_category iterator_category; typedef typename I::value_type value_type; typedef typename I::difference_type difference_type; typedef typename I::pointer pointer; typedef typename I::reference reference; }; |
总结：traits编程技法大量运用于STL实现品中，它利用“内嵌类型”的编程技巧与编译器的template参数推导功能，增强C++未能提供的关于类型认证方面的能力，弥补C++不为强类型语言的遗憾。
四，SGI STL的私房菜：__type_traits
了解了traits编程技法之后，我们再来介绍最后一个知识点——__type_traits。这是SGI把这种编程技术进一步扩大到了迭代器以外的世界。
这里有一点说明：单底线前缀指的是STL内部使用的；双底线前缀指的是SGI内部所用的东西。
（1）iterator_traits负责萃取迭代器的特性，__type_traits则负责萃取类型的特性。
（2）此处我们关注的特性是指：这个类型是否具备non-trivial default ctor?是否具备non-trivial copy ctor？是否具备non-trivial assignment operator？是否具备non-trivial dtor?
（3）如果答案是否定的，我们在对这个类型进行构造、析构、拷贝、赋值等操作时，就可以采用最有效的措施（例如根本不调用那些construct，destructor)，而采用内存直接处理操作如malloc(), memcpy()等等，获得最高效率。
（还记得在配置器析构函数的处理机制吗？先利用value_type()获得迭代器所指对象类型，再利用__type_traits<T>判断该类型的析构函数是否是无关痛痒的）
配置器中关于destroy()函数运用__type_traits机制的部分内容转到：http://dulishu.top/allocator-of-stl-2/
完…