一、迭代器的头文件

• 所有的容器都定义有自己的iterator类型，因此如果单单使用容器，只需要包含对应容器的头文件即可
• 不过有些特殊的iterator，被定义在头文件<iterator>中

二、迭代器介绍

• 类似于容器，迭代器也定义了一组公共操作：
  • 一些操作所有迭代器都支持
  • 另外一些只有特定类型的迭代器才支持
• 例如，ostream_iterator只支持递增、解引用、赋值。vector、string等容器的迭代器除了这些操作之外，还支持递减、关系、算术运算

迭代器的继承关系

• 可以参阅：https://blog.csdn.net/qq_41453285/article/details/103540156
• 高层类型的迭代器支持底层类别迭代器的所有操作

三、五大类迭代器

输入迭代器（input iterator）

• 输入迭代器可以读取序列中的元素
• 输入迭代器必须支持：
  • 用于比较两个迭代器的相等和不相等运算符（==、!=）
  • 用于推进迭代器的前置和后置递增运算（++）
  • 用于读取元素的解引用运算符（*）；解引用只会出现在赋值运算符的右侧
  • 箭头运算符（->）等价于(*it).member，即，解引用迭代器，并提取对象的成员
• 特点：
  • 输入迭代器只用于顺序访问
  • 对于一个输入迭代器，*it++保证是有效的，但递增它可能导致所有其他指向流的迭代器失效。其结果就是，不能保证输入迭代器的状态可以保存下来并用来访问元素。因此，输入迭代器只能用于单遍扫描算法
  • 例如，算法find和accumlate要求输入迭代器，而istream_iterator是一种输入迭代器

输出迭代器（output iterator）

• 输出迭代器可以看做输入迭代器功能上的补集——只可以写而不可以读取元素
• 输出迭代器必须支持：
  • 用于推进迭代器的前置和后置递增运算（++）
  • 解引用运算符（*），只出现在赋值运算符的左侧（向一个已经解引用的输出迭代器赋值，僵尸将值写入它所指的元素）
• 特点：
  • 我们只能向一个输出迭代器赋值一次
  • 类似输入迭代器，输出迭代器只能用于单遍扫描算法。用作目的位置的迭代器通常都是输出迭代器
  • 例如，copy算法的第三个参数就是输出迭代器，ostream_iterator类型也是输出迭代器

前向迭代器（forward iterator）

• 可以读写元素
• 特点：
  • 这些迭代器只能在序列中沿一个方向移动
  • 前进迭代器支持所有输入和输出迭代器的操作，而且可以多次读写同一个元素
  • 因此，我们可以保存前向迭代器的状态，使用前向迭代器的算法可以对序列进行多遍扫描
  • 例如，算法replace要求前向迭代器，forward_list容器上的迭代器是前向迭代器

双向迭代器（binirectional iterator）

• 可以正向/反向读写序列中的元素
• 特点：
  • 除了支持所有前向迭代器的操作之外，双向迭代器还支持前置和后置递减 运算符（--）
  • 例如，算法reverse要求双向迭代器，除了forward_list容器之外，其他标准库都提供符合双向迭代器要求的迭代器

随机访问迭代器（random-access iterator）

• 提供在常量时间内访问序列中任意元素的能力，此类迭代器支持双向迭代器的所有功能
• 另外还支持：
  • 用于比较两个迭代器相对位置的关系运算符（<、<=、>、>=）
  • 迭代器和一个整数值的加减运算（+、+=、-、-=），计算结果是迭代器在序列中前进（或后退）给定整数个元素后的位置
  • 用于两个迭代器上的减法运算符（-），得到两个迭代器的距离
  • 下标运算符（iter[n]），与*(iter[n])等价

• 例如，算法sort要求随机访问迭代器。array、deque、string、vector的迭代器都是随机访问迭代器，用于访问内置数组元素的指针也是