15.3　序列和迭代器

序列是STL中的核心概念。从STL的角度来看，数据集合就是一个序列。序列具有头部和尾部。我们可以对一个序列从头到尾进行遍历，对序列中的元素进行有选择的读写操作。我们利用一对迭代器来表示序列头部和尾部。迭代器（iterator）是一种可以标识序列中元素的对象。我们可以按照如下方式来看待一个序列：

 

这里的begin与end就是迭代器，它们标识了序列的头部和尾部。我们通常称STL的序列是“半开”的，因为由begin所标识的元素是序列的一部分，而迭代器end通常指向序列尾部之后的一个位置。在数学中，这种序列（区间）可以表示为[begin: end)。两个元素间的箭头表示如果有一个指向第一个元素的迭代器，那么我们就可以得到一个指向第二个元素的迭代器。

那么究竟什么是迭代器呢？迭代器是一个相当抽象的概念：

迭代器指向序列中的某个元素（或者序列末端元素之后）。

可以使用==和!=来对两个迭代器进行比较。

可以使用单目运算符*来访问迭代器所指向的元素。

可以利用操作符++来令迭代器指向下一个元素。

例如，如果p和q是两个指向同一个序列的迭代器：

标准迭代器的基本操作

p==q 当且仅当p和q指向序列中的同一个元素或都指向序列末端元素之后为真

p!=q !(p==q)

*p 表示p所指向的元素

*p=val 对p所指向的元素进行写操作

val=*p 对p所指向的元素进行读操作

++p 使p指向序列中的下一个元素或序列末端元素之后

 

很明显，迭代器的概念与指针（见12.4节）相关。实际上，指向数组中某一元素的指针就是一个迭代器。但是，许多迭代器不仅仅是指针。比如说，我们可以定义一个边界检查的迭代器，当试图使它指向[begin: end)之外时抛出一个异常。把迭代器作为一种抽象的概念而不是类型可以给我们带来很大的灵活性和通用性。本章和下一章将会举例说明这一点。

试一试

编写一个函数void copy(int* f1, int* e1, int* f2)，该函数把[f1: e1)定义的int型数组复制到数组[f2: f2+(e1-f1))中。注意只能使用上面所提到的迭代器操作（不能用索引）。

我们可以利用迭代器来实现代码（算法）与数据的连接。程序编写人员了解迭代器的使用方法（并不需要了解迭代器实际是如何访问数据的），数据提供者向用户提供相应的迭代器而不是数据存储的细节信息。这样得到的是一个简单的程序结构，而且使算法和容器之间保持了很好的独立性。正如Alex Stepanov所说：“STL算法和容器可以共同完成很强大的功能，而这却是因为它们根本不知道对方的存在。”但是，它们都知道由一对迭代器所定义的序列。

 

换句话说，我们的代码不再需要知道存储和访问数据的不同方法，它只需要对迭代器有一定的了解。另一方面，作为数据提供方，我们不再需要为不同的用户分别编写代码，而只需要为我们的数据配备好合适的迭代器。实际上，最简单的迭代器只是由*、++、==、!=等操作所定义的，这无疑会令它既方便又快速。

STL框架包含大概10种容器和60种由迭代器相连接的算法（参见第16章）。另外，许多组织和个人都在开发符合STL风格的容器和算法。STL可能是目前最著名的泛型编程的例子（见14.3.2节）。只要你了解了它的基本概念和一些简单的例子，就可以很容易掌握其他相关的内容。

15.3.1　回到实例

下面我们来看看如何使用STL来描述问题“查找序列中的最大元素”：

 

注意我们去掉了用来存储当前最大元素的变量h。当我们不能确定序列中元素的类型时，使用-1来完成初始化看起来非常随意和奇怪。这是因为它确实非常随意和奇怪！其中还隐藏着潜在错误：在我们的例子中-1能奏效仅仅是因为恰好不会存在负的速度。我们要记住像-1这样的“魔数”是非常不利于程序的维护的（见4.3.1节、7.6.1节、10.11.1节等）。在本例中，我们可以看到它还会限制函数的用途，并意味着我们对问题求解方案还没有形成一个比较全面的认识，也就是说，“魔数”是一种偷懒的表现。

注意这里的high()可以被用于所有可以使用<进行比较的元素类型。比如说，我们可以利用high()来查找vector<string>中按字典序最靠后的字符串（见习题7）。

high()模板函数可以用于任何由一对迭代器定义的序列。举例来说，我们可以严格复制例程：

 

 

这里的两个调用中，high()的Iterator模板参数的类型为double*。除了（最终）确保high()被正确实现外，这和我们之前的例子没有任何区别。更准确地说，所运行的代码并没有什么不同，但在代码的通用性上却有很大的区别。high()的模板版本适用于任何由一对迭代器所定义的序列。在进一步了解STL规范细节和所提供的能免除我们编写常见繁琐代码之苦的算法之前，我们先来集中了解数据元素集合的存储方法。

试一试

在我们的程序中有一个严重的错误。请找到并修改它，提出一种针对这种问题的通用解决方法。