看了候哥的《STL源码剖析》的迭代器那一章，在这里将思路稍微疏理一下
迭代器
迭代器模式的定义：提供一种方法，在不需要暴露某个容器的内部表现形式情况下，使之能依次访问该容器中的各个元素。
迭代器在STL中得到了广泛的应用，通过迭代器，容器和算法可以有机的粘合在一起，只要对算法给予不同的迭代器，就可以对不同容器进行相同的操作。也就是说，数据容器和算法是分开的。
独立的迭代器并不能满足我们的要求，在实现独立的迭代器时无可避免的会暴露出容器中的很多内容，所以STL将迭代器的实现交给了容器，每种容器都会以嵌套的方式在内部定义专属的迭代器。各种迭代器的接口相同，内部实现却不相同，这也直接体现了泛型编程的概念。
迭代器依附于具体的容器，即不同的容器有不同的迭代器实现。
对于泛型算法find，只要给它传入不同的迭代器，就可以对不同的容器进行查找操作。迭代器起穿针引线的作用，有效地实现了算法对不同容器的访问。
/*STL 中的 find 方法的实现*/
template<class InputIterator, class T>
InputIterator Find(InputIterator first, InputIterator last, const T& value)
{
while (first != last && *first != value)
++first;
return first;
} /*迭代器作为粘合剂的例子*/
void IteratorTest()
{
const int arr[] = { , , , , , , , , , }; vector<int> Vector(arr, arr + ); //vector 的初始化
list<int> List(arr, arr + ); //list 的初始化
deque<int> Deque(arr, arr + ); //deque 的初始化 vector<int>::iterator it1 = Find(Vector.begin(), Vector.end(), );
cout << *it1 << endl; list<int>::iterator it2 = Find(List.begin(), List.end(), );
cout << *it2 << endl; deque<int>::iterator it3 = Find(Deque.begin(), Deque.end(), );
if (it3 == Deque.end())
cout << "Node Found : Data!" << endl;
}
迭代器是一种smart pointer
迭代器是一种智能指针，是一种行为类似指针的对象，它内部封装了一个原始指针，并重载了operator*() 和operator->()等操作。
链表的迭代器
template<typename T>
class ListIter
{
public:
ListIter(T *p = ) : m_ptr(p){} //解引用，即dereference
T& operator*() const { return *m_ptr;} //成员访问，即member access
T* operator->() const { return m_ptr;} //前置++操作
ListIter& operator++()
{
m_ptr = m_ptr->next(); //暴露了ListItem的东西
return *this;
} //后置++操作
ListIter operator++(int)
{
ListIter temp = *this;
++*this;
return temp;
} //判断两个ListIter是否指向相同的地址
bool opeartor==(const ListIter &arg) const { return arg.m_ptr == m_ptr;} //判断两个ListIter是否指向不同的地址
bool operator!=(const ListIter &arg) const { return arg.m_ptr != m_ptr;} private:
T *m_ptr;
};
链表的实现
//List节点的结构
template<typename T>
class ListItem
{
public:
ListItem() { m_pNext = ;}
ListItem(T v, ListItem *p = ) { m_value = v; m_pNext = p;}
T value() const { return m_value;}
ListItem* next() const { return m_pNext;} private:
T m_value; //存储的数据
ListItem* m_pNext; //指向下一个ListItem的指针
}; //List表的结构
template<typename T>
class List
{
public:
//从链表尾部插入元素
void Push(T value)
{
m_pTail = new ListItem<T>(value);
m_pTail = m_pTail->next();
} //返回链表头部指针
ListItem<T>* begin() const { return m_pHead;} //返回链表尾部指针
ListItem<T>* end() const { return m_pTail;} //其它成员函数 private：
ListItem<T> *m_pHead; //指向链表头部的指针
ListItem<T> *m_pTail; //指向链表尾部的指针
long m_nSize; //链表长度
};
traits编程技法
5种迭代器型别的简单介绍：
1.value_type：迭代器所指对象的类型，原生指针也是一种迭代器，对于原生指针int*，int即为指针所指对象的类型，也就是所谓的value_type。
2.difference_type用来表示两个迭代器之间的距离，对于原生指针，STL以C++内建的ptrdiff_t作为原生指针的difference_type。
3.reference_type是指迭代器所指对象的类型的引用，reference_type一般用在迭代器的*运算符重载上，如果value_type是T，那么对应的reference_type就是T&；如果value_type是const T，那么对应的reference_type就是const T&。
4.pointer_type就是相应的指针类型，对于指针来说，最常用的功能就是operator*和operator->两个运算符。
5.iterator_category的作用是标识迭代器的移动特性和可以对迭代器执行的操作，从iterator_category上，可将迭代器分为Input Iterator、Output Iterator、Forward Iterator、Bidirectional Iterator、Random Access Iterator五类，这样分可以尽可能地提高效率。
在定义自己的类时为了和 STL 兼容，必须包含如上 5 个型别，以便 traits 的萃取。下面是STL提供的 iterator class，如果每个新设计的迭代器都继承它，就可以保证符合STL规范了
template<typename Category,
typename T,
typename Distance = ptrdiff_t,
typename Pointer = T*,
typename Reference = T&>
struct iterator
{
typedef Category iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
}; //类iterator不包含任何成员变量，只有类型的定义，因此不会增加额外的负担。由于后面三个类型都有默认值，在继承它的时候，只需要提供前两个参数就可以了。
迭代器的分类
前面提到迭代器的分类，下面我们就简单讨论下迭代器的分类。
除了原生指针以外，迭代器被分为五类：
Input Iterator
此迭代器不允许修改所指的对象，即是只读的。支持==、!=、++、*、->等操作。
Output Iterator
允许算法在这种迭代器所形成的区间上进行只写操作。支持++、*等操作。
Forward Iterator
允许算法在这种迭代器所形成的区间上进行读写操作，但只能单向移动，每次只能移动一步。支持Input Iterator和Output Iterator的所有操作。
Bidirectional Iterator
允许算法在这种迭代器所形成的区间上进行读写操作，可双向移动，每次只能移动一步。支持Forward Iterator的所有操作，并另外支持–操作。
Random Access Iterator
包含指针的所有操作，可进行随机访问，随意移动指定的步数。支持前面四种Iterator的所有操作，并另外支持it + n、it - n、it += n、 it -= n、it1 - it2和it[n]等操作。
迭代器的分类和从属关系可用下面的图表示（注意，这里的箭头并不代表继承关系，而是一种概念上的联系）：
分类的原因：
设计算法时，如果可能，我们尽量针对上面某种迭代器提供一个明确定义，并针对更强化的某种迭代器提供另一种定义，这样才能在不同情况下提供最大效率。
比如，有个算法可接受Forward Iterator，但是你传入一个Random Access Iterator，虽然可用（Random Access Iterator也是一种Forward Iterator），但是不一定是最佳的，因为Random Access Iterator可能更加臃肿，效率不一定高。
使用继承的原因：
例：
下面进入正题 traits 类型萃取机：
欢迎交流~~