C++学习笔记 —— 迭代器

一、迭代器

迭代器提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围。迭代器就如同一个指针。事实上，C++的指针也是一种迭代器。但是，迭代器不仅仅是指针，因此你不能认为他们一定具有地址值。例如，一个数组索引，也可以认为是一种迭代器。

迭代器有各种不同的创建方法。程序可能把迭代器作为一个变量创建。一个STL容器类可能为了使用一个特定类型的数据而创建一个迭代器。作为指针，必须能够使用*操作符类获取数据。你还可以使用其他数学操作符如++。典型的，++操作符用来递增迭代器，以访问容器中的下一个对象。如果迭代器到达了容器中的最后一个元素的后面，则迭代器变成past-the-end值。使用一个past-the-end值得指针来访问对象是非法的，就好像使用NULL或为初始化的指针一样。

提示
STL不保证可以从另一个迭代器来抵达一个迭代器。例如，当对一个集合中的对象排序时，如果你在不同的结构中指定了两个迭代器，第二个迭代器无法从第一个迭代器抵达，此时程序注定要失败。这是STL灵活性的一个代价。STL不保证检测毫无道理的错误。

二、迭代器类型

STL定义了5种迭代器，并根据所需的迭代器类型对算法进行了描述。对于这5种迭代器，都可以执行解除引用操作（即为它们定义了运算符），也可进行比较，看其是相等（使用==运算符，可能被重载了）还是不相等（使用!=运算符，可能被重载了）。如果两个迭代器相同，则对它们执行解除引用操作得到的值将相同。

2.1 输入迭代器

1. 提供对数据的只读访问，不允许修改容器中的值。
2. 单通行，可以递增，但不能倒退。

2.2 输出迭代器

1. 提供对数据的只写访问，不允许读取容器中的值。
2. 单通行。

2.3 正向迭代器

1. 提供对数据的读写操作，也可以只读。
2. 固定和可重复排序。
3. 单通行。

2.4 双向迭代器

1. 具有正向迭代器的所有特性。
2. 同时支持两种（前缀和后缀）递减运算符。

2.5 随机访问迭代器

1. 具有双向迭代器的所有特性
2. 同时添加了支持随机访问的操作（如指针增加运算）。

三、指针迭代器

正如下面的小程序显示的，一个指针也是一种迭代器。该程序同样显示了STL的一个主要特性——它不只是能够用于它自己的类类型，而且也能用于任何C或C++类型。Listing 1.iterdemo.cpp, 显示了如何把指针作为迭代器用于STL的find()算法来搜索普通的数组。
Listing 1. iterdemo.cpp

#include <iostream.h>
#include <algorithm>
 
using namespace std;
 
#define SIZE 100
int iarray[SIZE];
 
int main()
{
  iarray[20] = 50;
  int* ip = find(iarray, iarray + SIZE, 50);
  if (ip == iarray + SIZE)
     cout << "50 not found in array" << endl;
  else
     cout << *ip << " found in array" << endl;
  return 0;
}

在引用了I/O流库和STL算法头文件（注意没有.h后缀），该程序告诉编译器使用std名字空间。使用std名字空间的这行是可选的，因为可以删除该行对于这么一个小程序来说不会导致名字冲突。

程序中定义了尺寸为SIZE的全局数组。由于是全局变量，所以运行时数组自动初始化为零。下面的语句将在索引20位置处地元素设置为50,并使用find()算法来搜索值50:
iarray[20] = 50;
int* ip = find(iarray, iarray + SIZE, 50);

find()函数接受三个参数。头两个定义了搜索的范围。由于C和C++数组等同于指针，表达式iarray指向数组的第一个元素。而第二个参数iarray + SIZE等同于past-the-end 值，也就是数组中最后一个元素的后面位置。第三个参数是待定位的值，也就是50。find()函数返回和前两个参数相同类型的迭代器，这儿是一个指向整数的指针ip。

提示
必须记住STL使用模板。因此，STL函数自动根据它们使用的数据类型来构造。
为了判断find()是否成功，例子中测试ip和 past-the-end 值是否相等：
if (ip == iarray + SIZE) ...
如果表达式为真，则表示在搜索的范围内没有指定的值。否则就是指向一个合法对象的指针，这时可以用下面的语句显示：
cout << *ip << " found in array" << endl;
测试函数返回值和NULL是否相等是不正确的。不要像下面这样使用：
int* ip = find(iarray, iarray + SIZE, 50);
if (ip != NULL) ... // ??? incorrect
当使用STL函数时，只能测试ip是否和past-the-end 值是否相等。尽管在本例中ip是一个C++指针,其用法也必须符合STL迭代器的规则。

四、容器迭代器

尽管C++指针也是迭代器，但用的更多的是容器迭代器。容器迭代器用法和iterdemo.cpp一样，但和将迭代器申明为指针变量不同的是，你可以使用容器类方法来获取迭代器对象。两个典型的容器类方法是begin()和end()。它们在大多数容器中表示整个容器范围。其他一些容器还使用rbegin()和rend()方法提供反向迭代器，以按反向顺序指定对象范围。

下面的程序创建了一个矢量容器（STL的和数组等价的对象），并使用迭代器在其中搜索。该程序和前一章中的程序相同。
Listing 2. vectdemo.cpp

#include <iostream.h>
#include <algorithm>
#include <vector>
 
using namespace std;
 
vector<int> intVector(100);
 
void main()
{
  intVector[20] = 50;
  vector<int>::iterator intIter =
     find(intVector.begin(), intVector.end(), 50);
  if (intIter != intVector.end())
     cout << "Vector contains value " << *intIter << endl;
  else
     cout << "Vector does not contain 50" << endl;
}

注意用下面的方法显示搜索到的数据：
cout << "Vector contains value " << *intIter << endl;

• 由 Leung 写于 2018 年 9 月 7 日

• 参考：C++学习篇——C++ STL中迭代器介绍