iterator category

共有5类, 按照泛型算法对迭代器的需求进行分类

	拥有元素读权限	拥有元素写权限	支持单次扫描序列	支持多次扫描序列	支持递增运算	支持递增/递减运算	支持算术运算
输入迭代器	O	-	O	-	O	-	-
输出迭代器	-	O	O	-	O	-	-
前向迭代器	O	O	O	O	O	-	-
双向迭代器	O	O	O	O	O	O	-
随机访问迭代器	O	O	O	O	O	O	O

每个算法都会给出每个迭代器参数的最小类别

使用泛型算法时, 需传入满足要求的迭代器

向算法传递一个能力更差的迭代器会产生问题，但编译器不一定会给出警告或提示

五类迭代器层次关系

迭代器是按它们所提供的操作来分类的，而这种分类形成了一种层次:

• 可将前向迭代器用作输入迭代器和输出迭代器; 前向迭代器还支持对元素进行读写, 多次扫描序列
  
• 可将双向迭代器用作前向迭代器; 双向迭代器支持迭代器双向移动
  
• 可将随机访问迭代器用作双向迭代器; 随机访问迭代器还支持部分算术运算, 具有常量时间内访问序列中任意元素的能力
  

除了输出迭代器外，一个高层类别的迭代器满足低层迭代器的所有要求

输入迭代器

input iterator

读取序列中的元素:

• 拥有元素的读权限
  
• 支持递增运算
  
• 单次扫描序列
  

istream_iterator是输入迭代器

输入迭代器支持的操作

1. 相等运算符和不等运算符
   
   比较两个迭代器的相等和不相等
   

   Copy1it1 == it2;
   2it1 != it2;

2. 前置/后置递增运算符
   
   推进迭代器
   

   Copy1++it;
   2it++;

3. 解引用运算符
   
   访问元素
   
   *it只能出现在赋值运算符的右侧
   

   Copy1*it;

4. 成员访问运算符
   
   访问元素数据成员
   

   Copy1it->mem;

对输入迭代器执行(*it++)保证有效, 可能会导致其他所有指向流的迭代器失效

后置递增运算符优先级高于解引用运算符

istream_iterator是输入迭代器

• (*it++)返回的是递增之前所指元素的引用
  
• 递增输入迭代器之后, 其可能指向尾后元素, 即该迭代器不再有效
  
  此时, 与之交替读取输入流的输入迭代器同样指向尾后元素, 不再有效
  

输入迭代器只能用于单遍扫描算法

示例

• 在输入流迭代器的例子中, in和in2均绑定cin, 二者交替从流中读取数据
  

• 使in3保存in的状态, in和in2交替从cin读取数据
  

  1. 未对in3执行递增操作, 对其解引用得到的值不变
     
  2. in与in2交替从cin读取数据
     
  3. in读取 3 并递增后, in和in2均为尾后迭代器, 不再有效
     

  Copy 1#include <vector>
   2#include <iterator>
   3
   4using namespace std;
   5
   6int main()
   7{
   8    istream_iterator<int> in(cin), in2(cin), eof;
   9    vector<int> vec;
  10
  11    int i = 0;
  12
  13    auto in3 = in;
  14
  15    while(in != eof)
  16    {
  17        cout << "in3: " << *in3 << endl;
  18
  19        if (++i % 2 == 0)
  20            cout << "in2: " << *in2++ << "\t" << *in << endl;
  21        else
  22            cout << "in: " << *in++ << "\t" << *in2 << endl;
  23    }
  24    return 0;
  25}

  输入
  

  1 2 3 q

  输出
  

  in3: 1
  in: 1	2
  in3: 1
  in2: 2	3
  in3: 1
  in: 3	0

输出迭代器

output iterator

对输出迭代器指向的元素执行写操作:

• 拥有元素的写权限
  
• 支持递增运算
  
• 单次扫描序列
  

ostream_iterator是输出迭代器

插入迭代器是输出迭代器

输出迭代器支持的操作

1. 前置/后置递增运算符
   
   推进迭代器
   

   Copy1++it;
   2it++;

2. 解引用运算符
   
   对元素执行写操作
   

   只能对输出迭代器进行一次赋值
   

   *it只能出现在赋值运算符的左侧
   

   Copy1*it = val;

ostream_iterator作为输出迭代器

1. 对输出流迭代器执行写操作时, 直接对迭代器进行赋值即可
   

   Copy1it = val;

2. 对输出流迭代器执行解引用操作, 递增操作, 获得的还是输出流迭代器
   

   Copy1*it;
   2++it;
   3it++;

3. 只能对输出迭代器进行一次赋值
   
   每次对输出流迭代器进行赋值, 相当于往流输出一次数据
   
4. 对输出迭代器执行解引用操作的运算结果只能出现在赋值运算符左侧
   
5. 输出迭代器只能用于单遍扫描算法
   

插入迭代器作为输出迭代器

略

前向迭代器

forward iterator

可以对元素进行读写

支持递增运算: 单向移动

可以多次遍历序列(保存迭代器初始状态)

forward_list提供前向迭代器

前向迭代器支持输入/输出迭代器的所用功能

双向迭代器

bidirectional iterator

可以对元素进行读写

迭代器支持递增/递减运算

可以多次遍历序列

list提供双向迭代器

双向迭代器支持前向迭代器的所有功能

随机访问迭代器

random-access iterator

可以对元素进行读写

迭代器支持递增/递减运算和算术运算

具有在常量时间内访问序列中任意元素的能力

可以多次遍历序列

array, vector(string), deque提供随机访问迭代器

随机访问迭代器支持双向迭代器的所有功能

支持所有关系运算符

大于运算符, 小于运算符, 大于等于运算符, 小于等于运算符: 比较同一个容器或内置数组的迭代器之间的相对位置, 只有随机访问迭代器支持

相等运算符和不等运算符: 所有迭代器都支持

支持与整数的加/减运算

迭代器向前/向后移动整数个位置

Copy1iter + n;
2iter - n;

支持同一个容器的迭代器之间的减法运算

得到二者的距离, 有正负

Copy1iter1 - iter2;

支持下标运算符

获取迭代器之后位置的元素

Copy1iter[n];
2
3// <=>
4// *(iter + n);
5
6// <=>
7// *(iter[n]);

获取指向数组元素的随机迭代器

1. 头文件
   

   Copy1#include <iterator>

2. 获取指向数组首元素的迭代器
   

   Copy1begin(a);

3. 获取指向数组尾后元素的迭代器
   

   Copy1end(a);

示例

指针也是迭代器

Copy1int ia[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
2int *beg = begin(ia); // <=> int *b = arr;
3int *end = end(ia); // <=> int *e = &arr[10];