迭代器
设计思维
设计模式：提供一种方法，使之能够依序巡访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。
迭代器作用：STL的中心思想是将容器和算法分开，彼此独立设计，最后再用胶着剂将它们撮合在一起，迭代器扮演胶着剂
迭代器是一种是智能指针
迭代器行为类似于指针，最重要的作用是内容提领（deference）和成员访问（member access），因此，迭代器最重要的编程工作就是对operator*和operator->进行重载工作，可以参考auto_ptr（过时了）。
为什么每种STL容器有专属迭代器？
迭代器的实现需要容器细节：
要完成一个容器如List的迭代器，需要暴露很多List实现细节，如1.为了制作begin和end两个迭代器，迭代器内部需要链表节点的指针，暴露了链表节点。2.为了打成++，需要暴露next属性。
暴露细节无法避免，干脆让容器设计者开发专属迭代器
迭代器相应型别
概念：迭代器所指之物的型别等
问题：C++只支持sizeof()，不支持typeof()，不能识别迭代器所指之物的型别
解决：
方法1.利用function template的参数推导机制
局限性：
●五种类型不能全推出
●不能用于函数的返回值，template参数推导的只是参数
Traits编程技法——STL源代码门钥
traits大量运用于STL中，利用“内嵌型别”的编程技巧与编译器的template参数推导功能，增强了C++未能提供的关于型别认证方面的能力
方法2.声明内嵌型别
可以返回迭代器所指类型
局限性：并不是所有的迭代器都是类，如原生指针。不是类就无法定义内嵌型别。
方法3.traits（traits意为特性）
偏特化：针对template参数更进一步的条件限制所设计出来的一个特化版本，不一定要指定template部分参数。
//这也是一种偏特化，这个特化版本适用于“T为原生指针”的情况
//“T为原生指针”是对“T为任何型别”的限制，只要限制了就是特化
template<typename T>
class C<T*>{}
traits萃取迭代器特性
//1.如果I(迭代器)定义了自己的value type，那么萃取出的value_type就是I::value_type
template<class I>
struct iterator_traits{
typedef typename I::value_type value_type;
};
//2.原生指针特化版，如int*不是类，没有定义value type，也可以萃取出所指的类型
template<class T>
struct iterator_traits<T*>{
typedef T value_type;
};
//3.原生const指针特化版，我们不需要const特性
template<class T>
struct iterator_traits<const T*>{
typedef T value_type;
};
应用
可以用
typename iterator_traits<I>::value_type
来得到任何迭代器I的value_type
迭代器的五种型别
为了所开发的容器与STL兼容，一定定义五种相应型别
1.value type
概念：迭代器所指对象的型别
具体见上面
2.difference type
概念：两个迭代器之间的距离（元素个数）
traits：
//1.普通版本，针对类内定义了difference_type
template<class I>
struct iterator_traits{
typedef typename I::difference_type difference_type;
};
//2.原生非const指针版本
template<class T>
struct iterator_traits<T*>{
typedef ptrdiff_t difference_type; //ptrdiff_t为两个指针的差，定义于<cstddef>
};
//3.原生const指针 略
template<class T>
struct iterator_traits<const T*>{
typedef ptrdiff_t difference_type; //ptrdiff_t为两个指针的差，定义于<cstddef>
};
应用：STL的计数函数count()，返回值必须使用迭代器的difference type
3.reference type
4.pointer type
区分：reference type和pointer type
Item& operator*() const{return *ptr;} //Item&是reference type
Item* operator->() const{return ptr;} //Item*是pointer type
traits：
//1.普通版本，针对class type
template<class I>
struct iterator_traits{
typedef typename I::pointer pointer;
typedef typename I::reference reference;
};
//2.针对非const原生指针
template<class I>
struct iterator_traits<T*>{
typedef T* pointer;
typedef T& reference;
};
//2.针对非const原生指针
template<class I>
struct iterator_traits<const T*>{
typedef const T* pointer;
typedef const T& reference;
};
5.iterator_category
●五类迭代器：
●关系：
●考虑效率：如果对Random类一个个移动效率太低，所以要根据类别调用不同的函数
方法1：缺乏效率
方法2：函数重载
●traits实现
//这个traits比前面四种难理解一点
//如value type萃取的是iter所指的类型，iterator_categoty萃取的就是属于五类迭代器中的哪一类
//萃取的是迭代器的最强类型
//1.普通版本，类内自行指定
template<class I>
struct iterator_traits{
typedef typename I::iterator_category iterator_category;
};
//2.原生指针版本，原生指针是一种Random
template<class I>
struct iterator_traits<T*>{
typedef random_access_iterator_tag iterator_category;
};
//3.原生const指针版本，原生cosnt指针是一种Random
template<class I>
struct iterator_traits<const T*>{
typedef random_access_iterator_tag iterator_category;
};
std::iterator的保证
iterator源代码完整重列
见p101
注意：
SGI STL的私房菜 __type_traits
萃取什么：型别的特性，即这个型别是否有默认构造，默认析构，默认拷贝构造/操作符
区别：iterator_traits负责萃取迭代器的特性，__type_traits则负责萃取型别的特性。
SGI STL一般化：
偏特化：
应用：和迭代器型别差不多，获取五个属性中的一个，然后true和false临时变量调用不同的重载函数