16.7　迭代器简介

迭代器（iterator）是一个对象，它在其他对象的容器上遍历，每次选择它们中的一个，不需要提供对这个容器的实现的直接访问。迭代器提供了一种访问元素的标准方法，无论容器是否提供了直接访问元素的方法。迭代器常常与容器类联合使用，而且迭代器在标准C++容器的设计和使用中是一个基本概念，这方面的知识在本书的第2卷（可从www.BruceEckel.com下载）中有全面的描述。迭代器也是一种设计模式（design pattern），这是第2卷中的有一章的主题。

在许多情况下，迭代器是一个“灵巧指针”；并且事实上，我们会注意到：迭代器通常模仿大多数指针的运算。然而，不同的是，迭代器的设计更安全，所以数组越界的可能性更小（或者说，如果有数组越界，就会更早被发现）。

考虑本章的第一个例子，这里增加了一个简单的迭代器。

创建IntStackIter，以便只与IntStack一起工作。注意，IntStackIter是IntStack的友元，这就允许访问IntStack的所有私有成员。

像指针一样，IntStackIter的工作是遍历IntStack，并提取值。在这个简单的例子中，IntStackIter只能向前移动（用operator++的前缀和后缀形式）。然而，迭代器定义没有限制，而只是有与它一起工作的容器的约束限制。在与迭代器相联系的容器中，迭代器可以用任何方式移动，并且可以通过它修改被包含的值。

习惯上，用构造函数来创建迭代器，并把它与一个容器对象联系，并且在它的生命期中，不把它与不同的容器联系。（迭代器通常是小的和廉价的，所以可以很容易地再做一个。）

使用迭代器，我们可以扫描栈的元素而不用弹出它们，这就像指针遍历数组的元素一样。然而，迭代器知道栈的下层结构，并知道如何遍历栈的元素，所以即便我们正在以“向前移动指针”的方式遍历栈的元素，我们也应该使用迭代器。下面将介绍更多的内容。迭代器的关键是：从一个容器元素移动到下一个元素的复杂过程被抽象为就像一个指针一样。目标是使程序中的每个迭代器都有相同的接口，使得使用这个迭代器的任何代码都不用关心它指向什么，只需要知道它能用同样的方法重新配置所有的迭代器，所以这个迭代器所指向的容器并不重要。用这种方法，我们可以编写更一般性的代码。标准C++库的所有容器和算法都基于迭代器的这一原则。

为了让事情更一般化，最好能说“每一个容器有一个相关的名为iterator的类”，但是这引起典型的名字问题。解决的办法是为每个容器增加一个嵌套的iterator类（注意，在这种情况下，“i t e r a t o r”以小写字母开始，使得它与标准C++库的风格一致）。下面是IterIntStack.cpp，带有一个嵌套的iterator。

当创建一个嵌套friend类的时候，我们必须经过首先声明这个类的名称，然后声明它是友元，最后定义这个类的过程。否则，编译器将会产生混淆。

我们在迭代器中增加了一些新的手法。current（）成员函数产生容器中的由迭代器当前选择的元素。我们可以用operator+=使迭代器向前“跳跃”任意个元素。而且，我们还会看到两个重载运算符：==和！=，它们将比较两个迭代器。它们能比较任意两个IntStack：iterator，但是它们的最初意图是测试这个迭代器是否已经到达了序列的终点，采用“实际的”标准C++库迭代器所用的相同方法。其思想是，两个迭代器定义了一个范围，第一个迭代器指向第一个元素，第二个迭代器指向最后一个元素后面的位置。如果希望遍历由这两个迭代器所定义的范围，可以写为如下形式：

这里，start和end是在这个范围内的两个迭代器。注意，end迭代器并不反向引用，只是告诉我们已经到了这个范围的终点，我们称之为“终止哨兵”（end sentinel）。因而它代表“终点后面的一个”。

大多数情况下我们希望在容器中遍历整个序列，所以这个容器需要某种方法产生表示这个序列的开始和终止哨兵的迭代器。在此，就像在标准C++库中一样，这些迭代器由容器的成员函数begin（）和end（）产生。begin（）使用第一个迭代器构造函数，它默认指向这个容器的开始（这就是压入这个栈的第一个元素）。然而，第二个构造函数，由end（）使用，对于创建终止哨兵迭代器是必需的。“在终点”的意思是指向这个栈的顶部，因为top允许指向下一个可用的但是尚未使用的位置。这个迭代器构造函数采用第二个类型为bool的参数，它是哑元，以区别两个构造函数。

在main（）中再次使用斐波纳契数来填充IntStack，用迭代器遍历整个IntStack并且还遍历序列的一个小范围。

当然，下一步是通过对它所包含的类型模板化来让代码一般化，所以不是强迫仅能存放int，而是可以存放任何类型。

可以看到，从正规类到模板的转换是适度透明的。首先创建和调试一个普通类，然后让它成为模板，一般认为这种方法比一开始就创建模板更容易。

注意，不是只写：

这段代码是：

这是重要的，因为名字“iterator”已经在一个范围内，来自一个被包含的文件。

不是用current（）成员函数，而是iterator有一个operator*，用来选择当前的元素，这使iterator看上去更像一个指针，这是一个普通的习惯。

下面是一个用来测试模板的修改过的例子：

迭代器的第一个应用只移动它从开始到最后（可以看到终止哨兵工作正常）。在第二个应用中，我们可以看到迭代器如何允许我们容易地指定元素的范围（在标准C++库中，容器和迭代器随处使用范围的概念）。重载operator+=移动start和end迭代器到is中元素范围的中间位置，打印出这些元素。注意，在输出中，终止哨兵不在范围内，这样，它可以是范围终点后面的一个，可以让程序员知道他已经越过了终点，但是，不反向引用终止哨兵，否则就相当于反向引用空指针。（在StackTemplate：iterator中我已经做了防护，但是在标准C++库中的容器和迭代器中，出于效率的原因，没有这样的代码，所以必须注意。）

最后，为了验证StackTemplate与类对象一起工作，采用一个string的实例，它用源代码文件中的行填充这些字串，然后打印出它们。

16.7.1　带有迭代器的栈

重复具有动态长度Stack类的过程，这是贯穿本书的例子。这里Stack类带有一个嵌套的迭代器。

我们已经注意到，这个类已经被修改以支持所有权，它能工作是因为这个类知道确切类型（或者至少知道基本类型，这是基于使用虚构造函数的假设而工作的）。对于容器的默认是销毁它的对象，但是我们要负责处理我们pop（）的任何指针。

迭代器是简单的，体积非常小，即单个指针的大小。当创建一个迭代器时，它被初始化为指向链表的头，只能沿着链表向前递增。如果希望指向起点之后，就创建一个新迭代器，如果希望记住表中的一点，就从已存在的迭代器中创建一个新迭代器，指向这一点（使用迭代器的拷贝构造函数）。

为了对由迭代器指向的对象调用函数，我们可以使用current（）函数、operator*和指针反向引用operator-＞（迭代器中的一个共同点）。后者的实现看上去与current（）一样，因为它返回一个指向当前对象的指针，但是实际上不同，因为这个指针反向引用运算符完成反向引用的外层（参见第12章）。

iterator类遵循前面例子中的形式。class iterator嵌套在容器类中，它包含构造函数，可以创建指向容器中一个元素的一个迭代器和一个“终止哨兵”迭代器，并且容器类有用来产生这些迭代器的begin（）和end（）方法。（当我们对标准C++库的学习更加深入之后，就会看到：在这里用的名字iterator、begin（）和end（）已经明确地被推举为标准容器类。在本章的最后将会看到，使用这些容器类就像使用标准C++库容器类一样。）

全部实现都包含在头文件中，所以这里没有单独的cpp文件。下面是用来检验迭代器的一个小测试：

Stack是一个示例，用来存放string对象，并用来自一个文件的行填充。然后创建一个迭代器，用于遍历这个序列。通过从第一个迭代器拷贝构造第二个迭代器，来记住第10行，然后打印这一行，并且销毁动态创建的迭代器。这里，使用动态对象创建来控制该对象的生命期。