7.3　更多迭代器

迭代器是为实现通用而做的抽象。它与不同类型的容器一起工作而不必了解那些容器的底层结构。绝大多数容器都支持迭代器，^[1]所以可以像下面这样：

为一个容器创建迭代器类型。每一个容器都有一个起始成员函数begin（）以产生指向容器中起始元素的迭代器，和一个末尾成员函数end（）用以产生容器的超越末尾的标记迭代器。如果容器是一个const（常）容器，则begin（）和end（）产生const（常）迭代器，即不允许更换这些迭代器所指向的元素（因为相应的运算符都是const的）。

所有的迭代器都可以在它们的序列中向前移动（通过运算符operator++），并且允许使用==和！=进行比较。因此，为在不超出范围的前提下前移一个名为it的迭代器，可以进行如下处理：

这里pastEnd是由容器的成员函数end（）产生的超越末尾的标记。

通过使用解析运算符（operator*），一个迭代器可用于产生其当前所指的容器元素。这可以有两种形式。如果it是一个可以遍历容器的迭代器，并且f（）是容器持有的对象类型的一个成员函数，就可以使用两种形式中的任一种形式：

或者

了解了这些以后，就可以创建一个可以与任何容器一起工作的模板了。在这里，函数模板apply（）为容器中的每个对象调用一个成员函数，它使用一个指向成员函数的指针作为参数进行传递：

在这里不能使用operator-＞，因为这将导致语句成为：

它将尝试使用迭代器的operator-＞*，而该操作符在迭代器类中并未提供。^[2]

就像在第6章中所看到的那样，可以更容易地使用for_each（）或者transform（）两者之中任一个函数应用到序列。

7.3.1　可逆容器中的迭代器

一个容器也可以是可逆的（reversible），这意味着容器可以产生一个从末尾反向移动的迭代器，这些迭代器也可以从容器的起始元素前向移动。所有标准的容器都支持这种双向迭代。

可逆容器拥有成员函数rbegin（）（用于产生一个选择了容器末尾的迭代器reverse_iterator）和rend（）（用于产生一个指向“超越起始”的迭代器reverse_iterator）。如果容器为const容器，则rbegin（）和rend（）将会产生const_reverse_iterator。

下面的例子使用vector，但该例适用于所有支持迭代操作的容器：

反向移动遍历一个容器，使用与一个前向移动遍历容器的普通的迭代器时相同的语法。

7.3.2　迭代器的种类

标准C++库中的迭代器被归类为若干“种类”以便描述它们的性能。通常对它们的描述顺序是从行为约束最严格的种类到行为功能最强大的种类。

1.输入迭代器：只读，一次传递

为输入迭代器的预定义实现只有istream_iterator和istreambuf_iterator，用于从一个输入流istream中读取。就像想象的那样，一个输入迭代器仅能对它所选择的每个元素进行一次解析，正如只能对一个输入流的特殊部分读取一次一样。它们只能前向移动。一个专门的构造函数定义了超越末尾的值。总之，输入迭代器可以对读操作的结果进行解析（对每一个值仅解析一次），然后前向移动。

2.输出迭代器：只写，一次传递

这是对输入迭代器的补充，不过是对写操作而不是读操作。为输出迭代器的预定义实现只有ostream_iterator和ostreambuf_iterator，用于向一个输出流ostream写数据，还有一个一般较少使用的raw_storage_iterator。再次强调，它们只能对每个写出的值进行一次解析，并且只能前向移动。对于输出迭代器来说，没有使用超越末尾的值来结束的概念。总之，输出迭代器可以对写操作的值进行解析（对每一个值仅解析一次），然后前向移动。

3.前向迭代器：多次读/写

前向迭代器包含了输入和输出迭代器两者的所有功能，加上还可以多次解析一个迭代器指定的位置，因此可以对一个值进行多次读/写。顾名思义，前向迭代器只能向前移动。没有专为前向迭代器预定义的迭代器。

4.双向迭代器：operator—

双向迭代器具有前向迭代器的全部功能，另外它还可以利用自减操作符operator—向后一次移动一个位置。由list容器中返回的迭代器都是双向的。

5.随机访问迭代器：类似于一个指针

最后，随机访问迭代器具有双向迭代器的所有功能，再加上一个指针所有的功能（一个指针就是一个随机访问迭代器），除了没有一种“空（null）”迭代器和空指针相对应。基本上可以这样说，一个随机访问迭代器就像一个指针那样可以进行任何操作，包括使用操作符operator[]进行索引，加某个整数值到一个指针就可以向前或向后移动若干个位置，或者使用比较运算符在迭代器之间进行比较。

6.重要性

人们为什么要关心这些分类法？当只需要以一种明确的方式（比如，仅仅是手工编码想要对某个容器中的对象进行所有的操作）来使用容器时，这些分类法通常并不重要。那么，对迭代器进行分类到底有什么用处。迭代器种类在下列场合中就很重要：

1）使用某些不久就要演示的C++爱好者内置的迭代器类型，或者用户已经“学成毕业”，能够胜任创建自己的迭代器的工作（在本章稍后演示）。

2）使用STL算法（第6章的主题）。每种算法对其迭代器都有使用场合的要求。在创建用户自己的可重用的算法模板的时候，迭代器种类的知识变得尤其重要，因为自定义算法需要的迭代器种类决定了该算法的灵活性。如果仅要求最基本的迭代器种类（输入或者输出迭代器），这种算法则适合于任何场合（copy（）就是这样的一个例子）。

一个迭代器的种类由一个迭代器的层次结构标记类进行标识。类名和迭代器的种类相符合，并且它们之间的派生层次结构反映了它们之间的关系：

类forward_iterator_tag仅从input_iterator_tag派生，而不是从output_iterator_tag派生，因为在使用前向迭代器的算法中需要超越末尾的迭代器值，但是使用输出迭代器的那些算法总是假定运算符operator*是可以解析的。为了这个原因，保证一个超越末尾的值绝不会传递到那些希望使用输出迭代器的算法中是很重要的。

为提高效率，某些算法为不同种类的迭代器提供不同的实现，这些迭代器是从由其定义的迭代器标记中推算出来的。在本章稍后部分当我们创建自己的迭代器类型时，将会用到这些标记类。

7.3.3　预定义迭代器

STL拥有一个用起来相当便利的预定义迭代器的集合。正如所见到的，对所有基本容器调用rbegin（）和rend（）可得到reverse_iterator对象。

因为某些STL算法需要插入迭代器（insertion iterator）—例如，copy（）算法—使用赋值操作符operator=将对象放进目的容器中去。在向容器中填充（fill）而不是覆盖已经存在于目的容器中的那些元素时，当在那里已经没有空间可填充的时候，就会产生问题。插入迭代器所做的事情就是改变运算符operator=的实现来替代赋值操作，称为该容器的“压入”或“插入”函数，因此该函数就引起容器分配新的存储空间。back_insert_iterator和front_insert_iterator两者的构造函数都使用一个基本序列容器对象（vector、deque或list）作为其参数，并产生一个分别调用push_back（）或push_front（）以进行赋值的迭代器。有益的函数back_inserter（）和front_inserter（）让程序员在产生这些插入迭代器对象的时候少写一些代码。因为所有的基本序列容器都支持push_back（），读者可能会发现，使用back_inserter（）已经成为某种经常性的工作。

insert_iterator能够向一个序列的中间插入元素，再一次代替了operator=的含义，但是这一次则是自动调用插入函数insert（）而不是某个“压入”函数。insert（）成员函数需要一个迭代器在插入前指定插入的位置，所以除了容器对象以外，insert_iterator还需要这个迭代器。插入器函数inserter（）产生相同的对象。

下面的例子演示了不同类型的插入器的使用：

因为vector不支持push_front（），所以它不能产生一个front_insert_iterator。然而，可以看到vector支持另外两种插入的类型（即便如此，稍后也将看到对于vector来说insert（）并不是一个高效的操作）。注意，这里用嵌套类型Cont：value_type而不是硬编码的int类型。

1.更多的流迭代器

在第6章中，结合copy（）函数介绍了流迭代器ostream_iterator（输出迭代器）和istream_iterator（输入迭代器）的用法。要记住，输出流是没有“结束”这个概念的，因为用户总是在持续地写出更多的元素。然而，输入流却最终会结束（比如，达到了文件末尾），所以需要有一种方法来表现这一点。istream_iterator有两个构造函数，一个获得输入流istream并且产生一个实际读取的迭代器，另一个是默认构造函数，用于产生一个作为超越末尾的标记的对象。在下面的例子中这个对象被命名为end：

当in用完输入时（在这个例子中，是指到达了文件的末尾），init与end相等，于是copy（）终止。

因为out是一个ostream_iterator＜string＞，使用运算符operator=可以分配任何string对象给解析后的迭代器，并且将那个string放入输出流中，就像在两个给out赋值的操作所做的那样。因为out在定义时以一个新行作为其第2个参数，所以这个赋值操作也在每次赋值时插入一个新行。

虽然可能创建一个istream_iterator＜char＞和ostream_iterator＜char＞，但实际上这样做会从语法上分析（parse）输入并且导致诸如自动地吃掉空白字符（空格、制表符和换行符），如果希望用一个输入流的精确地表现这样的动作，是不可取的。另一种方法可以使用特殊的迭代器istreambuf_iterator和ostreambuf_iterator，它们被设计用来严格地移动字符。^[3]虽然这些都是模板，但它们都想要使用char或者wchar_t作为模板参数。^[4]在下面的例子中，让我们来比较流迭代器和流缓冲迭代器的行为：

从语法上来分析，流迭代器使用由istream：operator＞＞来定义，如果读者正在直接从语法上分析字符的话这也许不是你所希望的—要从字符流中将所有的空白字符都去掉的做法相当罕见。事实上读者总希望在使用字符和流的时候使用流缓冲迭代器，而不是使用流迭代器。另外，istream：operator＞＞为每次操作增加了不小的开销，所以它只适合于较高级的操作，比如从语法上分析数字。^[5]

2.操纵未初始化的存储区

raw_storage_iterator在＜memory＞中定义，它是一个输出迭代器。它提供了使算法能够将其结果存储到未经初始化的内存的能力。其接口相当简单：构造函数持有一个指向某原始（未初始化）内存储区的迭代器（典型的指针），并且运算符operator=将一个对象分配给那个原始内存。模板参数是输出迭代器的类型和将要被存储的对象类型，输出迭代器指向该原始存储区。这里的例子创建了Noisy对象，它们打印出这些对象的构造、赋值以及析构时的跟踪语句（将在稍后介绍Noisy类的定义）：

为了能够正确地使用raw_storage_iterator模板，原始存储区类型必须与所创建的对象类型相同。这就是为什么来自新char数组的指针被类型转换为Noisy*的原因。赋值操作符使用拷贝构造函数将对象强制存入原始存储区。注意，必须显式地调用析构函数以便进行适当的清理工作，这也允许在操纵容器期间每次删除一个对象。但表达式delete np无论如何是无效的，因为在delete表达式中的一个静态指针类型，必须与new表达式中分配的类型相同。

[1]容器适配器、栈、队列和优先队列不支持迭代器，因为在用户看来它们的行为与序列的行为并不相同。

[2]它仅仅适用于那些使用了一个（a T*）指针作为迭代器类型的vector的实现，就像STLPort所做的那样。

[3]创建这些迭代器实际上是为了将现场面从输入输出流中抽象出来，从而使现场面能够处理任何字符序列，不仅仅是输入输出流。这样现场允许输入输出流可以轻易地处理一些不同的格式（比如货币符号的表示方式）。

[4]对于其他参数类型，用户需要提供一个用于特化的char_traits。

[5]我们应该感谢Nathan Myers对此的解释。