iterator模式定义如下：
提供一种方法，使之能够依序巡访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表达方式。
stl的中心思想在于：将数据容器和算法分开，彼此独立设计，最后再以一贴胶着剂将他们撮合在一起。容器和算法的范型化，从技术角度来看并不困难，c++的class templates和function templates可分别达成目标。如何设计出两者之间的良好胶着剂，才是大难题。
迭代器是一种行为类似指针的对象（实际上是结构体模板），而指针的各种行为中最常见也最重要的便是内容提领（dereference）和成员访问（member access），因此，迭代器最重要的编程工作就是对operator*和operator->进行重载（overloading）工作。
… …
把迭代器的开发工作交给容器的设计者，如此一来，所有实现细节反而得以封装起来不被使用者看到。这正是为什么每一种stl容器都提供专属迭代器的缘故。
什么是相应型别？迭代器所指之物的型别便是其一。c++只支持sizeof()，并未支持typeof()。即便动用RTTI性质中的typeid()，获得的也只是型别名称，不能拿来做变量声明之用。
解决办法是：利用function template的参数（argument deducation）推导机制。
参数型别推导技巧虽然可用于value type，却非全面可用：万一value type必须用于函数的传回值，就束手无策了，毕竟函数的“（法1）template 参数推导机制”推而导之的只是参数，无法推导函数的返回值类别。“（法2）声明内嵌型别”似乎是个好主意，就这样：
如果不是class type，就无法为它定义内嵌型别。
“（法3）template partial specialization偏特化”针对任何template参数更进一步的条件限制所设计出来的一个特化版本。
有了这项利器，我们便可以解决前述“内嵌型别”未能解决的问题。
class template专门用来“萃取”迭代器的特性，而value type正是迭代器的特性之一：
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()可以改写成这样：
针对原生指针而设计的偏特化版
如果迭代器是个pointer-to-const，设法令其value type为一个non-const型别。没问题，只要另一个特化版本，就能解决这个问题：
针对原生的pointer-to-const而设计的偏特化版
说明了traits所扮演的“特性萃取机”角色，萃取各个迭代器的特性。这里所谓的迭代器特性，指的是迭代器的相应型别（assiociated types）。当然，若要这个“特性萃取机”traits能够有效运作，每一个迭代器必须遵循约定，自行以内嵌型别定义（nested typedef）的方式定义出相应型别（associated types）。这是一个约定，谁不遵守这个约定，谁就不能兼容与
stl这个大家庭。
根据经验，最常用到的迭代器相应型别有五种：value_type,different type,pointer,refernece,iterator categoly。如果你希望你所开发的容器能与stl水乳交融，一定要为你的容器的迭代器定义这五种相应型别。“特性萃取机”traits会很忠实地将原汁原味榨取出来：
template <class I>
struct iterator_traits
{
typedef typename I::iterator_category iterator_category;
typedef typename I::value_type value_type;
typedef typename I::different_type different_type;
typedef typename I::pointer pointer;
typedef typename I::reference reference;
};
所谓value type，是指迭代器所指对象的型别。任何一个打算与stl算法有完美搭配的class，都应该定义自己的value type内嵌型别。
different type用来表示两个迭代器之间的距离，因此它也可以用来表示一个容器的最大容量，因为对于连续空间的容器而言，头尾之间的距离就是其最大容量。如果一个范型算法提供计数功能，例如stl的count()，其传回值就必须使用迭代器的different type：
template <class I,class T>
typename iterator_traits<I>::difference_type
count(I first,I last,const T& value)
{
typename iterator_traits<I>::difference_type n = 0;
for(;first != last;++first)
if(*first == value)
++n;
return n;
}
针对相应型别difference type，traits的如下两个（针对原生指针而写的）特化版本，以c++内建的ptrdiff_t作为原生指针的difference type：
template <class I>
struct iterator_traits
{
...
typedef typename I::difference_type difference_type;
};
// 针对原生指针而设计的“偏特化（partial specialization）”版
template <class T>
struct iterator_traits<T*>
{
...
typedef ptrdiff_t difference_type;
}
// 针对原生的pointer-to-const而设计的“偏特化（partial specialization）”版
template <class T>
struct iterator_traits<const T*>
{
...
typedef ptrdiff_t difference_type;
}
从“迭代器所指之物的内容是否允许改变”的角度观之，迭代器分为两种：不允许改变“所指对象之内容”者，称为constant iterastors，例如const int* pic；允许改变“所指对象之内容”者，称为mutable iterators，例如int* pi。当我们对一个mutable iterators进行提领操作时，获得的不应该是一个右值（rvalue），应该是一个左值（lvalue），因为右值不允许赋值操作（assignment）左值才允许。
在c++中，函数如果要传回左值，都是以by reference的方式进行，所以当p是个mutable iterators时，如果其value type是T，那么p的型别不应是T，应该是T&。将此道理扩充，如果p是一个constant iterastors，其value type是T，那么p的型别不是const T，而应该const T&。这里所讨论的*p的型别，即所谓的reference type。
pointers和references在c++中有非常密切的关联。如果“传回一个左值，令它代表p所指之物”是可能的，那么“传回一个左值，令他代表p所指之物的地址”也一定可以。也就是说，我们能够传回一个pointer，指向迭代器所指之物。现在我们把reference type和pointer type这两个相应型别加入traits内：
template <class I>
struct iterator_traits
{
...
typedef typename I::pointer pointer;
typedef typename I::reference reference;
};
// 针对原生指针而设计的“偏特化（partial specialization）”版
template <class T>
struct iterator_traits<T*>
{
...
typedef T* pointer;
typedef T& reference;
}
// 针对原生的pointer-to-const而设计的“偏特化（partial specialization）”版
template <class T>
struct iterator_traits<const T*>
{
...
typedef const T* pointer;
typedef const T& reference;
}
迭代器的分类：
·Input Iterator：只读（read only）。
·Output Iterator：只写（write only）。
·Forward Iterator：允许“写入型”算法（例如replace()）在此种迭代器所形成的区间上进行读写操作。
·Bidirectional Iterator：可双向移动。
·Ramdom Access Iterator：前四种迭代器都只供应一部分指针算数能力（前三种支持operator++，第四种再加上operator–），第五种则涵盖所有指针算数能力，包括p+n，p-n，p[n]，p1-p2，p1<p2。
concept（概念）与refinement（强化）的关系
设计算法时，如果可能，我们尽量针对图中的某种迭代器提供一个明确定义，并针对更强化的某种迭代器提供另一种定义，这样才能在不同情况下提供最大效率。
为了符合规范，任何迭代器都应该提供五个内嵌相应型别，以利于traits萃取，否则便是自别于整个stl架构，可能无法与其他stl组件顺利搭配。然而写代码难免挂一漏万，谁也不能保证不会有粗心大意的时候。如果能够将事情简化，就好多了。stl提供了一个iterator class如下，如果每个新设计的迭代器都继承自它，就可保证符合stl所需之规范：
template <class Category,
class T,
class Distance = ptrdiff,
class Pointer = T*,
class Reference = T&>
struct iterator
{
typedef Category iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
};
iterator class不含任何成员，纯粹只是型别定义，所以继承它并不会招致任何额外负担。由于后三个参数皆有默认值，故新的迭代器提供前两个参数即可。
template <class Item>
struct ListIter:public std::iterator<std::forward_iterator_tag,Item>
{ ... }
总结：
设计适当的相应型别（associated types）,是迭代器的责任。设计适当的迭代器，则是容器的责任。唯容器本身，才知道该怎样设计出怎样的迭代器来遍历自己，并执行迭代器该有的各种行为（前进、后退、取值、取用成员…）。至于算法，完全可以独立于容器和迭代器之外自行发展，只要设计时以迭代器为对外接口就行。
traits编程技法大量运用于stl实现品中。它利用“内嵌型别”的编程技巧与编译器的template参数推导功能，增强c++未能提供的关于型别认证方面的能力，弥补c++不为强型别（strong typed）语言的遗憾。
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 {};
// 为避免写代码时挂一漏万，自行开发的迭代器最好继承自下面这个std::iterator
template <class Category,
class T,
class Distance = ptrdiff_t,
class Pointer = T*,
class Reference = T&>
struct iterator
{
typedef Category iterator_category;
typedef T value_type;
typedef Distance differece_type;
typedef Pointer pointer;
typedef Reference reference;
};
// “榨汁机”traits
template <class Iterator>
struct Iterator_traits
{
typedef typename Iterator::iterator_category iterator_category;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::differece_type differece_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
};
// 针对原生指针（native pointer）而设计的traits偏特化版
template <class T>
struct Iterator_traits<T*>
{
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t differece_type;
typedef T* pointer;
typedef T& reference;
};
// 针对原生之pointer-to-const而设计的traits偏特化版
template <class T>
struct Iterator_traits<const T*>
{
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t differece_type;
typedef T* pointer;
typedef T& reference;
};
... ...