迭代器
Design Pattern中对迭代器的模式定义：提供一种方法能都依序访问某个聚合物(容器)内所含的各个元素，而又无需暴露该聚合物的内部表述方式。
迭代器是一种类似指针对象，最重要的工作是进行operator*和operator->进行重载，除此之外还有++，==，=这一系列运算符的重载，不可避免地曝光了很多结构的实现细节。所以将迭代器的开发任务交给结构的设计者更加高效。
迭代器关联类型
如何获取“迭代器所指对象”的类型？解决办法是使用模板函数参数推导机制。
//简单举例
template <class I, class T>
void func_impl(I iter,T e) { //T就是迭代器所指之物的类型
。。。
}
template <class I>
void func(I iter) {//对外接口
func_impl(iter,*iter);//实际工作
}
Traits
如果value type要用于函数传回值，使用参数推导就没有作用了，可以通过声明内嵌类型解决。
template <class T>
struct Iter {
typedef T value_type;//内嵌类型
...
};
template <calss I>
typename I:value_type func(I iter) { //typename 关键字告诉编译器 value_type代表一个类型
...
}//返回类型I:value_type
这种方法仅限于定义了内嵌类型的class type成员，对于原生指针类型，无法定义内嵌类型。于是引入template partial sepcilization(模板偏特化)，即如果class template拥有多个template参数，可以针对一部分参数进行特化，相当于在泛化设计中提供一个特化版本。
template <typename T>
class C<T*> {}; //T*为原生指针就是T为任何类型的进一步条件限制。
template <class I>
struct iterator_traits {
typedef typename I::value_type value_type;
};//如果I定义了 自己的value_type，可以萃取出value_type；
多了一层间接性可以拥有特化版本：
template <class T>
struct iterator_traits<T*> {
typedef T value_type;
}//原生指针如int*类型也可以萃取出value_type；
//但是针对指向常数对象的指针，iterator_traits<const int*>::value_type，获取类型是const int，可以使用另一种特化
template <class T>
struct iterator_traits<const T*> {
typedef T value_type;//类型为T，而非const T
};
根据经验，最常用到的五种关联类型:value_type,difference type,pointer,reference,iterator category。
value type：迭代器所指对象的类型；
difference type：两迭代器之间的距离
template <class I,calss T>
typename iterator_traits::difference_type count(I first,I last,const value &value) {
typename iterator_traits::difference_type n = 0;
for(;first !=last;++first)
if(*first == value)
++n;
return n;
}
//针对原生指针，使用内建类型prtdiff_t
template <class T>
struct iterator_traits<T*> {
typedef prtdiff_t difference_type;
};
reference type:迭代器所指对象内容是否允许改变，分为constant iterators和mutable iterators,后者应当返回左值，在C++中使用reference方式返回左值。如果mutable iterator p的value type是T，*p类型是T&。
pointer type：reference type返回左值代表p所指内容，而pointer type返回左值代表p所指之内容的地址。
iterator_category：首先讨论迭代器的分类
- Input Iterator：只读,只支持operator++
- Output Iterator：只写,只支持operator++
- Forward Iterator：允许“写入型”算法，执行读写操作,只支持operator++
- Bidirectional Iterator：双向移动,支持operator++,operator--
- Random Access Iterator：涵盖所有指针运算能力
直线与箭头代表概念与强化关系，如果算法接收一种迭代器，那么就可以接受强化类型的迭代器。设计算法时，尽量针对某种迭代器提供明确定义，针对强化迭代器提供另一种定义，才能提供最大效率。任何迭代器属于其所类型中最强的那个。
为了实现针对不同类型迭代器的重载函数，traits应该能萃取出迭代器的类型，以作为算法的参数之一。
42 struct input_iterator_tag {};
43 struct output_iterator_tag {};
44 struct forward_iterator_tag : public input_iterator_tag {};
45 struct bidirectional_iterator_tag : public forward_iterator_tag {};
46 struct random_access_iterator_tag : public bidirectional_iterator_tag {};
//Input版，模板以算法所能接受的最低阶迭代器类型作为形参
tempalte <class InputIterator,class Distance>
inline void __advance(InputIterator &i,Distance n,input_iterator_tag) {
while(n--) ++i;
}
// Forward版，传递调用Input版
tempalte <class ForwardIterator,class Distance>
inline void __advance(ForwardIterator &i,Distance n,forward_iterator_tag) {
__advance(i,n,input_iterator_tag());
}
//Bidirectional版支持两个方向
tempalte <class BidirectionalIterator,class Distance>
inline void __advance(BidirectionalIterator &i,Distance n,bidirectional_iterator_tag) {
if(n >= 0)
while(n--) ++i;
else
while(n++) --i;
}
//Random Access版
tempalte <class RandomAccessIterator,class Distance>
inline void __advance(RandomAccessIterator &i,Distance n,random_access_iterator_tag) {
i+=n;
}
最后一个参数用于声明类型，激活重载，并不使用该参数。
//提供上层接口，最后一个参数产生临时对象，在编译时决定调用那个__advance
tempalte <class InputIterator,class Distance>
inline void advance(InputIterator &i,Distance n) {
__advance(i,n,iterator_traits<InputIterator>::iterator_category());
}
//定义iterator_category()如下：
template <class I>
inline typename iterator_traits<I>::iterator_category iterator_category(const &i) {
typedef typename iterator_traits<I>::iterator_category category;
reutrn category();
}
//对于原生指针类型的iterator_category()，是一种RandomAccessIterator
template <class T>
struct iterator_traits<T*> {
typedef rendom_access_iterator_tag iterator_category;
}
使用struct继承方式来定义分类标签，有助于消除“单纯传递调用函数”。比如前面的advance()的ForwardIterator版，可以不用写，编译器会调用其父类函数(Input版)。(todo:对OutputIterator定位不明朗，forward_tag并没有继承output_tag)
至此，itarator_traits结构包含以下部分:
tempalte <class I>
struct iterator_traits {
typedef typename I::value_type value_type;
typedef typename I::iterator_category iterator_category;
typedef typename I::differnce_type difference_type;
typedef typename I::pointer pointer;
typedef typename I::reference reference;
};
std::iterator
tempalte <class Catagory,class T,class Distance = ptrdiff_t,class Pointer = T*,class Reference = &T>
struct iterator {
typedef Category iterator_category;
typedef T value_type;
typedef Disatnce difference_type;
typedef Pointer pointer;
typedef Reference reference;
};
//iterator不包含数据，继承时不会有额外开销,一般只需提供前两个参数。
tempalte <class Item>
struct ListIterator:public std::iterator<std::forward_iterator_tag,Item> {
...
}
迭代器的作用是设计适当的关联类型；设计适当的迭代器是容器的责任。而算法则独立于迭代器和容器。
SGI STL中的__type_traits
SGI将itreator_traits扩展到了__type_traits，如此类型是否具备non-trivial default ctor(constructor),n-t copy ctor,n-t assignment operator 等，如果所具有的都是trivial，对这个类型进行 构造，析构，拷贝时可以采取最有效的措施，如直接使用内存操作。
__type_traits<T>::has_trivial_default_constructor
__type_traits<T>::has_trivial_copy_constructor
__type_traits<T>::has_trivial_assignment_operator
__type_traits<T>::has_trivial_destructor
__type_traits<T>::is_POD_type
struct __true_type {};
struct __false_type {};