C++ Iterator

我真的不知道我之前写的那个迭代器的总结去哪里了…实在不行就再写一遍呗…

什么是迭代器, 为什么要有迭代器

​ STL提供了很多种容器, 像什么array, vector之类的, 迭代器是能够提供一个统一的操作接口, 虽然不同容器的迭代器对象本身不同, 但暴露出来的接口是一样的, 可以通过同样的接口对其进行同样(至少是相似)的操作.

迭代器的分类

迭代器的动作分成读和写两种, 其实针对容器来说就是输入和输出两种, 一种是输入迭代器, 一种是输出迭代器. 输入迭代器的输入是指针对容器来说的, 往容器里写数据叫输入, 从容器往程序里输出数据叫输出.

此外, 根据迭代器的迭代方向, 可以分为正向迭代器, 反向迭代器, 随机访问迭代器, 双向迭代器几种不同的类型. 其中, 输入迭代器是典型的单项迭代器, 它只能递增但是不能倒退. 输入出迭代器也是单通行的. 双向迭代器则是可以具有正向迭代器所有特性的同时, 附加支持了两种递减运算, 即 ++i 和 i++ .

通常来说, 比较常用的是随机访问迭代器, 它具有双向迭代器所有的特性, 同时支持了随机访问的操作, 比如指针增加的运算, 以及对于元素进行排序的关系运算符.

到这儿你会发现, 迭代器其实是分三六九等的, 最高级的是随机访问迭代器, 它具备前述所有迭代器的所有功能的同时, 支持了一些其他类型迭代器不支持的功能. 当然, 这样做的代价自然是开销比较大. 如果你的程序对性能过于敏感, 则需要考虑这些区别, 否则可以直接使用随机访问迭代器.

各种迭代器的类型并不是确定的, 只是一种概念性的描述. 在具体的实现上, 是在每个容器类都定义了一个类级 typedef 的名称 iterator . 比如 vector<int> 类的迭代器类型就是 vector<int>::iterator. 然而, 这个类的文档也指出, vector 的迭代器是随机访问迭代器, 它允许使用基于任何迭代器类型的算法. 同样, list<int> 的迭代器就是 list<int>::iterator. 再比如说, STL写了一个双向链表, 这个双向链表具备一个双向迭代器, 但是这个迭代器不能使用基于随机访问的算法, 但是可以使用双向迭代器支持的算法.

常见的迭代器模型

1. 将指针用作迭代器

迭代器其实就是广义的指针, 而且指针也满足了迭代器的所有要求. 因为迭代器是STL算法的接口(interface), 而指针是迭代器, 因此, STL算法可以使用指着来对基于指针的非STL容器进行操作. 这样做可以把STL写好的算法用在自己的一些数据结构上, 而不仅仅是STL容器. 比如STL算法可以用于数组, 用 sort() 进行排序.

sort() 接受指向容器第一个元素的迭代器和指向超尾的迭代器作为参数. 我们现在假设有一个 double 型的数组叫 Receipts , 我们拿它作为例子, 进行升序排序:

const int SIZE = 100;
double Recipts[SIZE];

现在找出你想传进去的参数, 分别是 &Reciptes[0] 和 &Reciptes[SIZE] , 因此你可以按照这个函数的调用来对它进行排序:

sort(Reciptes, Reciptes[SIZE]);

当然, 你也可以用其他的STL函数, 比如 copy() , 甚至你可以把你的数组copy()到屏幕上, 只需要把它copy给ostream_iterator 就行.

#include <iterator>
ostream_iterator<int, char> out_iter(cout, " ");
copy(dice.begin(), dice.end(), out_iter);

2. 其他有用的迭代器

除了 ostream_iterator, 头文件 <iterator>还提供了其他的一些预定义迭代器类型, 比如reverse_iterator, back_insert_iterator, front_insert_iterator和insert_iterator. 这些各有千秋, 你可以找官方文档查看这些内容.