在这个专题开始的时候就已经提及过，STL库中的泛型算法大多数情况下并不是为了某一种容器或某一类数据机构所设计的，他们总是服务于绝大多数的容器。然而在算法的设计中，大多数都需要依赖指针遍历数据结构从而进行某些操作，迭代器就是用来统一所有容器的指针的行为的，可以说他是一种泛化的指针。 通过迭代器，我们可以使得算法的设计和容器的设计分割开来，最后通过迭代器使算法应用于容器之中。
在前言中说到，迭代器是一种泛化的指针，通过操作符的重载，从而使一个class在使用上像是一个指针。想要实现这并不难，只需要拥有一个指针的数据成员，并且重载解引用操作符*和箭头操作符->就可以令一个class在行为上像是一个指针。
同时，迭代器还需要具备的一个特性是，通过++或 - - 操作可以顺序遍历整个容器，这是以后泛型算法可以利用迭代器去访问整个容器的必要条件，为了满足这个需求我们也需要重载这个class的++和- -操作符。
最后，在将萃取器的时候，我们知道算法有时需要通过萃取器获取迭代器的某些属性，这就需要我们自定义的迭代器定义了自己的五个型别 ，进而满足算法的提问。
总结的说，迭代器是每一个容器都需要定义的一个class，它最起码具有以下特征：
我们这一章的重点是迭代器，所以对于容器行为就不做过多的分析，这里我们只需要知道List的存储结构就行，因为这样我们就可以为他设计出一个迭代器。
List是STL库中一个较为简单的容器，他底层是一个双向链表的结构。 这就意味着：
第一条意味着我们不能单纯的通过原生指针的++操作，使迭代器前进到下一个节点。
第二条意味着我们可以通过节点中的指针从而移动迭代器
第三条为我们提供了移动上边界的判断条件。
在上边我们分析了List迭代器最基础的需求，现在我们就来简单的实现以下这些需求
先把大的框架搭出来：
template<class Item>
struct ListIter
: public bidirectional_iterator_tag
{
Item* ptr;//指向容器空间的指针
ListIter(Item* p = nullptr) :ptr(p) {};//构造函数
//这里不必实现拷贝构造函数、拷贝赋值函数和析构函数
//因为对于迭代器来说，编辑器默认的已经足够了
}
接下来，我们需要让这个类能够实现指针的解引用操作，那么就需要操作符重载：
template<class Item>
struct ListIter
: public bidirectional_iterator_tag
{
Item* ptr;//指向容器空间的指针
ListIter(Item* p = nullptr) :ptr(p) {};//构造函数
//这里不必实现拷贝构造函数、拷贝赋值函数和析构函数
//因为对于迭代器来说，编辑器默认的已经足够了
//使这个class具有指针的行为
Item& operator*() const { return *ptr; }
Item* operator->() const { return ptr; }
}
实现了最基本的指针操作，我们就需要重载++和- -，满足遍历整个容器的需求
template<class Item>
struct ListIter
: public bidirectional_iterator_tag
{
Item* ptr;//指向容器空间的指针
ListIter(Item* p = nullptr) :ptr(p) {};//构造函数
//这里不必实现拷贝构造函数、拷贝赋值函数和析构函数
//因为对于迭代器来说，编辑器默认的已经足够了
//使这个class具有指针的行为
Item& operator*() const { return *ptr; }
Item* operator->() const { return ptr; }
//实现对于整个元素的遍历操作
ListIter& operator++(){//前置++
ptr = ptr->next;
return *this;
}
ListIter operator++(int) {//后置++
ListIter temp = *this;
++*this;
return temp;
}
ListIter& operator--() {//前置--
ptr = ptr->pre;
return *this;
}
ListIter operator--(int) {//后置--
ListIter temp = *this;
--*this;
return temp;
}
bool operator==(const ListIter& i)
{ return ptr == i.ptr; }
bool operator!=(const ListIter& i)
{ return ptr != i.ptr; }
};
需要注意的是 ++和- -操作符都有前置或后置两种情况，我们需要对每种情况都进行重载
细心的话有可能会注意到，前置和后置两种版本的返回值类型不同，这是因为对于原生指针来说，后置++不能重复叠加使用（如 *p++ ++，这是非法的），所以在我们模仿指针的时候，也要向原生的指针靠近，我们就用这种方式阻止后置++的叠加使用。
最后，我们就需要完成对自身型别的定义，也就产生了完整的版本：
template<class Item>
struct ListIter
: public bidirectional_iterator_tag
{
//定义自己的型别
typedef Item value_type;//指针指向的元素类型
typedef Item& reference;//指针指向元素类型的引用
typedef Item* pointer;//指针指向元素类型的指针
typedef ptrdiff_t difference_type;//记录两个迭代器之间位置差的元素的类型
typedef bidirectional_iterator_tag iterator_category;//迭代器的移动类型
Item* ptr;//指向容器空间的指针
ListIter(Item* p = nullptr) :ptr(p) {};//构造函数
//这里不必实现拷贝构造函数和拷贝赋值函数
//因为对于迭代器来说，编辑器默认的已经足够了
//使这个class具有指针的行为
Item& operator*() const { return *ptr; }
Item* operator->() const { return ptr; }
//实现对于整个元素的遍历操作
ListIter& operator++(){//前置++
ptr = ptr->next;
return *this;
}
ListIter operator++(int) {//后置++
ListIter temp = *this;
++*this;
return temp;
}
ListIter& operator--() {//前置--
ptr = ptr->pre;
return *this;
}
ListIter operator--(int) {//后置--
ListIter temp = *this;
--*this;
return temp;
}
bool operator==(const ListIter& i)
{ return ptr == i.ptr; }
bool operator!=(const ListIter& i)
{ return ptr != i.ptr; }
};
这五个定义在STL的实际应用上只用到了其中的三个，但是为了融入STL，我们仍然需要按照标准去定义所有的型别。
接下来就来分析这五种型别
为了融入STL，我们的迭代器也必须定义自己的五个型别去满足算法的提问，他们分别是：
这个三个typedef顾名思义，分别记录迭代器所指向的类型、指针和引用。前两个没什么值得注意的地方，只有第三个reference有一点需要注意：
从能否改变只想元素的内容这一角度看，迭代器分为不能改变内容的constant和可以改变内容的mutable。若一个指针p他的value_type是T，如果他是mutable的，那么 * p的类型就不应该是T而应该是T&，因为只有这样才可以保证他是一个可被改变的左值；如果p是constant的，那么* p的类型也应该是const T&
在对迭代器或指针进行操作时，我们很有可能令两个指向同一个空间的指针相减，从而得到两个指针之间的距离，而difference_type型别的作用就是记录用什么样的元素去保存这个数值。若difference_type的类型是int，那么当两个指针之间的距离超过了int可能承载的数值时，就会出错。
大多数情况下，我们都会使用头文件 xutility 中所定义的类型ptrdiff_t去储存两个原生指针之间的距离，所以在迭代器中，一般情况下也使用这个类型作为difference_type.
这个型别记录了迭代器可以怎么进行移动，是最重要也是最经常被算法提问的型别，因为它的不同在很大程度上可以影响算法的复杂程度。STL定义了五种迭代器：
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{};
他们的继承关系如下图：
图片来自侯捷C++STL与泛型系列教程讲义
随机迭代器 继承自 双向迭代器 继承自 前序迭代器 继承自 输入迭代器
在他们的继承体系之外的是输出迭代器。
迭代器的移动类型对于算法效率的影响是很深远的，例如：
当我们需要在排序号的查找容器中的一个元素所在位置时
对于随即迭代器，我们可以采用二分查找，但是对于双向或者前序迭代器，我们只能遍历整个容器去查找。这两者最有情况下的时间复杂度分别是O(logN) 和 O(N)，效率差别还是挺大的。
所以说，在设计算法时，对于不同的迭代器的移动类型，最好额外设计一种偏特化的版本，这样有利于提高算法的效率。
总结的说，迭代器是每一个容器都需要定义的一个class，它最起码具有以下特征：
通过迭代器，我们可以实现算法和容器的分开设计，最后使用迭代器将二者联系起来