Team LiB
Previous Section Next Section

9.2. Iterators and Iterator Ranges

9.2. 迭代器和迭代器范围

The constructors that take a pair of iterators are an example of a common form used extensively throughout the library. Before we look further at the container operations, we should understand a bit more about iterators and iterator ranges.

在整个标准库中，经常使用形参为一对迭代器的构造函数。在深入探讨容器操作之前，先来了解一下迭代器和迭代器范围。

In Section 3.4 (p. 95), we first encountered vector iterators. Each of the container types has several companion iterator types. Like the containers, the iterators have a common interface: If an iterator provides an operation, then the operation is supported in the same way for each iterator that supplies that operation. For example, all the container iterators let us read an element from a container, and they all do so by providing the dereference operator. Similarly, they all provide increment and decrement operators to allow us to go from one element to the next. Table 9.3 lists the iterator operations supported by the iterators for all of the library containers.

第 3.4 节首次介绍了 vector 类型的迭代器。每种容器类型都提供若干共同工作的迭代器类型。与容器类型一样，所有迭代器具有相同的接口：如果某种迭代器支持某种操作，那么支持这种操作的其他迭代器也会以相同的方式支持这种操作。例如，所有容器迭代器都支持以解引用运算从容器中读入一个元素。类似地，容器都提供自增和自减操作符来支持从一个元素到下一个元素的访问。表 9.3 列出迭代器为所有标准库容器类型所提供的运算。

Table 9.3. Common Iterator Operations
表 9.3. 常用迭代器运算

*iter

Return a reference to the element referred to by the iterator iter.

返回迭代器 iter 所指向的元素的引用

iter->mem

Dereference iter and fetch the member named mem from the underlying element. Equivalent to (*iter).mem.

对 iter 进行解引用，获取指定元素中名为 mem 的成员。等效于 (*iter).mem

++iter iter++

Increment iter to refer to the next element in the container.

给 iter 加 1，使其指向容器里的下一个元素

--iter iter--

Decrement iter to refer to the previous element in the container.

给 iter 减 1，使其指向容器里的前一个元素

iter1 == iter2
iter1 != iter2

Compare two iterators for equality (inequality). Two iterators are equal if they refer to the same element of the same container or if they are the off-the-end iterator (Section 3.4, p. 97) for the same container.

比较两个迭代器是否相等（或不等）。当两个迭代器指向同一个容器中的同一个元素，或者当它们都指向同一个容器的超出末端的下一位置时，两个迭代器相等


Iterators on vector and deque Support Additional Operations

vector 和 deque 容器的迭代器提供额外的运算

There are two important sets of operations that only vector and deque support: iterator arithmetic (Section 3.4.1, p. 100) and the use of the relational operators (in addition to == and !=) to compare two iterators. These operations are summarized in Table 9.4 on the facing page.

C++ 定义的容器类型中，只有 vector 和 deque 容器提供下面两种重要的运算集合：迭代器算术运算（第 3.4.1 节），以及使用除了 == 和 != 之外的关系操作符来比较两个迭代器（== 和 != 这两种关系运算适用于所有容器）。表 9.4 总结了这些相关的操作符。

Table 9.4. Operations Supported by vector and deque Iterators
表 9.4. vector 和 deque 类型迭代器支持的操作

iter + n
iter - n

Adding (subtracting) an integral value n to (from) an iterator yields an iterator that many elements forward (backward) within the container. The resulting iterator must refer to an element in the container or one past the end of the container.

在迭代器上加（减）整数值 n，将产生指向容器中前面（后面）第 n 个元素的迭代器。新计算出来的迭代器必须指向容器中的元素或超出容器末端的下一位置

iter1 += iter2
iter1 -= iter2

Compound-assignment versions of iterator addition and subtraction. Assigns the value of adding or subtracting iter1 and iter2 into iter1.

这里迭代器加减法的复合赋值运算：将 iter1 加上或减去 iter2 的运算结果赋给 iter1

iter1 - iter2

Subtracting two iterators yields the number that when added to the right-hand iterator yields the left-hand iterator. The iterators must refer to elements in the same container or one past the end of the container.

两个迭代器的减法，其运算结果加上右边的迭代器即得左边的迭代器。这两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置

Supported only for vector and deque.

只适用于 vector 和 deque 容器

>, >=, <, <=

Relational operators on iterators. One iterator is less than another if it refers to an element whose position in the container is ahead of the one referred to by the other iterator. The iterators must refer to elements in the same container or one past the end of the container.

迭代器的关系操作符。当一个迭代器指向的元素在容器中位于另一个迭代器指向的元素之前，则前一个迭代器小于后一个迭代器。关系操作符的两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置

Supported only for vector and deque.

只适用于 vector 和 deque 容器


The reason that only vector and deque support the relational operators is that only vector and deque offer fast, random access to their elements. These containers are guaranteed to let us efficiently jump directly to an element given its position in the container. Because these containers support random access by position, it is possible for their iterators to efficiently implement the arithmetic and relational operations.

关系操作符只适用于 vector 和 deque 容器，这是因为只有这种两种容器为其元素提供快速、随机的访问。它们确保可根据元素位置直接有效地访问指定的容器元素。这两种容器都支持通过元素位置实现的随机访问，因此它们的迭代器可以有效地实现算术和关系运算。

For example, we could calculate the midpoint of a vector as follows:

例如，下面的语句用于计算 vector 对象的中点位置：

     vector<int>::iterator iter = vec.begin() + vec.size()/2;

On the other hand, this code

另一方面，代码：

     // copy elements from vec into ilist
     list<int> ilist(vec.begin(), vec.end());
     ilist.begin() + ilist.size()/2; // error: no addition on list iterators

is an error. The list iterator does not support the arithmetic operationsaddition or subtractionnor does it support the relational (<=, <, >=, >) operators. It does support pre- and postfix increment and decrement and the equality (inequality) operators.

是错误的。list 容器的迭代器既不支持算术运算（加法或减法），也不支持关系运算（<=, <, >=, >），它只提供前置和后置的自增、自减运算以及相等（不等）运算。

In Chapter 11 we'll see that the operations an iterator supports are fundamental to using the library algorithms.

第十一章中，我们将会了解到迭代器提供运算是使用标准库算法的基础。

Exercises Section 9.2

Exercise 9.7:

What is wrong with the following program? How might you correct it?

下面的程序错在哪里？如何改正。

     list<int> lst1;
     list<int>::iterator iter1 = lst1.begin(),
                         iter2 = lst1.end();
     while (iter1 < iter2) /* . . . */

Exercise 9.8:

Assuming vec_iter is bound to an element in a vector that holds strings, what does this statement do?

假设 vec_iter 与 vector 对象的一个元素捆绑在一起，该 vector 对象存放 string 类型的元素，请问下面的语句实现什么功能？

     if (vec_iter->empty()) /* . . . */

Exercise 9.9:

Write a loop to write the elements of a list in reverse order.

编写一个循环将 list 容器的元素逆序输出。
Exercise 9.10:

Which, if any, of the following iterator uses are in error?

下列迭代器的用法哪些（如果有的话）是错误的？

     const vector< int > ivec(10);
     vector< string >    svec(10);
     list< int >         ilist(10);

     (a) vector<int>::iterator    it = ivec.begin();
     (b) list<int>::iterator      it = ilist.begin()+2;
     (c) vector<string>::iterator it = &svec[0];
     (d) for (vector<string>::iterator
                  it = svec.begin(); it != 0; ++it)
                     // ...


9.2.1. Iterator Ranges

9.2.1. 迭代器范围

The concept of an iterator range is fundamental to the standard library.


迭代器范围这个概念是标准库的基础。


An iterator range is denoted by a pair of iterators that refer to two elements, or to one past the last element, in the same container. These two iterators, often referred to as first and last, or beg and end, mark a range of elements from the container.

C++ 语言使用一对迭代器标记迭代器范围（iterator range），这两个迭代器分别指向同一个容器中的两个元素或超出末端的下一位置，通常将它们命名为 first 和 last，或 beg 和 end，用于标记容器中的一段元素范围。

Although the names last and end are common, they are a bit misleading. The second iterator never refers to the last element of the range. Instead, it refers to a point one past the last element. The elements in the range include the element referred to by first and every element from first tHRough the element just before last. If the iterators are equal, then the range is empty.

尽管 last 和 end 这两个名字很常见，但是它们却容易引起误解。其实第二个迭代器从来都不是指向元素范围的最后一个元素，而是指向最后一个元素的下一位置。该范围内的元素包括迭代器 first 指向的元素，以及从 first 开始一直到迭代器 last 指向的位置之前的所有元素。如果两个迭代器相等，则迭代器范围为空。

This element range is called a left-inclusive interval. The standard notation for such a range is

此类元素范围称为左闭合区间（left-inclusive interval），其标准表示方式为：

     // to be read as: includes first and each element up to but not including last
     [ first, last )

indicating that the range begins with first and ends with, but does not include, last. The iterator in last may be equal to the first or may refer to an element that appears after the one referred to by first. The last iterator must not refer to an element ahead of the one referred to by first.

表示范围从 first 开始，到 last 结束，但不包括 last。迭代器 last 可以等于 first，或者指向 first 标记的元素后面的某个元素，但绝对不能指向 first 标记的元素前面的元素。

Requirements on Iterators Forming an Iterator Range

对形成迭代器范围的迭代器的要求

Two iterators, first and last, form an iterator range, if

迭代器 first 和 last 如果满足以下条件，则可形成一个迭代器范围：

  • They refer to elements of, or one-past-the-end of, the same container.

    它们指向同一个容器中的元素或超出末端的下一位置。

  • If the iterators are not equal, then it must be possible to reach last by repeatedly incrementing first. In other words, last must not precede first in the container.

    如果这两个迭代器不相等，则对 first 反复做自增运算必须能够到达 last。换句话说，在容器中，last 绝对不能位于 first 之前。

The compiler cannot itself enforce these requirements. It does not know to which container an iterator is bound, nor does it know how many elements are in a container. Failing to meet these requirements results in undefined run-time behavior.

编译器自己不能保证上述要求。编译器无法知道迭代器所关联的是哪个容器，也不知道容器内有多少个元素。若不能满足上述要求，将导致运行时未定义的行为。



Programming Implications of Using Left-Inclusive Ranges
使用左闭合区间的编程意义

The library uses left-inclusive ranges because such ranges have two convenient properties. Assuming first and last denote a valid iterator range, then

因为左闭合区间有两个方便使用的性质，所以标准库使用此烦区间。假设 first 和 last 标记了一个有效的迭代器范围，于是：

  1. When first equals last, the range is empty.

    当 first 与 last 相等时，迭代器范围为空；

  2. When first is not equal to last, there is at least one element in the range, and first refers to the first element in that range. Moreover, we can advance first by incrementing it some number of times until first == last.

    当 first 与不相等时，迭代器范围内至少有一个元素，而且 first 指向该区间中的第一元素。此外，通过若干次自增运算可以使 first 的值不断增大，直到 first == last 为止。

These properties mean that we can safely write loops such as the following to process a range of elements by testing the iterators:

这两个性质意味着程序员可以安全地编写如下的循环，通过测试迭代器处理一段元素：

     while (first != last) {
         // safe to use *first because we know there is at least one element
         ++first;
     }

Assuming first and last form a valid iterator range, then we know that either first == last, in which case the loop is exited, or the range is non-empty and first refers to an element. Because the condition in the while handles the case where the range is empty, there is no need for a special case to handle an empty range. When the range is non-empty, the loop will execute at least once. Because the loop body increments first, we know the loop will eventually terminate. Moreover, if we are in the loop, then we know that *first is safe: It must refer to an element in the non-empty range between first and last.

假设 first 和 last 标记了一段有效的迭代器范围，于是我们知道要么 first == last，这是退出循环的情况；要么该区间非空，first 指向其第一个元素。因为 while 循环条件处理了空区间情况，所以对此无须再特别处理。当迭代器范围非空时，循环至少执行一次。由于循环体每次循环就给 first 加 1,因此循环必定会终止。而且在循环内可确保 *first 是安全的：它必然指向 first 和 last 之间非空区间内的某个特定元素。

Exercises Section 9.2.1

Exercise 9.11:

What are the constraints on the iterators that form iterator ranges?

要标记出有效的迭代器范围，迭代器需要满足什么约束？
Exercise 9.12:

Write a function that takes a pair of iterators and an int value. Look for that value in the range and return a bool indicating whether it was found.

编写一个函数，其形参是一对迭代器和一个 int 型数值，实现在迭代器标记的范围内寻找该 int 型数值的功能，并返回一个 bool 结果，以指明是否找到指定数据。
Exercise 9.13:

Rewrite the program that finds a value to return an iterator that refers to the element. Be sure your function works correctly if the element does not exist.

重写程序，查找元素的值，并返回指向找到的元素的迭代器。确保程序在要寻找的元素不存在时也能正确工作。
Exercise 9.14:

Using iterators, write a program to read a sequence of strings from the standard input into a vector. Print the elements in the vector.

使用迭代器编写程序，从标准输入设备读入若干 string 对象，并将它们存储在一个 vector 对象中，然后输出该 vector 对象中的所有元素。
Exercise 9.15:

Rewrite the program from the previous exercise to use a list. List the changes you needed to change the container type.

用 list 容器类型重写习题 9.14 得到的程序，列出改变了容器类型后要做的修改。


9.2.2. Some Container Operations Invalidate Iterators

9.2.2. 使迭代器失效的容器操作

In the sections that follow, we'll see that some container operations change the internal state of a container or cause the elements in the container to be moved. Such operations invalidate all iterators that refer to the elements that are moved and may invalidate other iterators as well. Using an invalidated iterator is undefined, and likely to lead to the same kinds of problems as using a dangling pointer.

在后面的几节里，我们将看到一些容器操作会修改容器的内在状态或移动容器内的元素。这样的操作使所有指向被移动的元素的迭代器失效，也可能同时使其他迭代器失效。使用无效迭代器是没有定义的，可能会导致与悬垂指针相同的问题。

For example, each container defines one or more erase functions. These functions remove elements from the container. Any iterator that refers to an element that is removed has an invalid value. After all, the iterator was positioned on an element that no longer exists within the container.

例如，每种容器都定义了一个或多个 erase 函数。这些函数提供了删除容器元素的功能。任何指向已删除元素的迭代器都具有无效值，毕竟，该迭代器指向了容器中不再存在的元素。

When writing programs that use iterators, we must be aware of which operations can invalidate the iterators. It is a serious run-time error to use an iterator that has been invalidated.

使用迭代器编写程序时，必须留意哪些操作会使迭代器失效。使用无效迭代器将会导致严重的运行时错误。


There is no way to examine an iterator to determine whether it has been invalidated. There is no test we can perform to detect that it has gone bad. Any use of an invalidated iterator is likely to yield a run-time error, but there is no guarantee that the program will crash or otherwise make it easy to detect the problem.

无法检查迭代器是否有效，也无法通过测试来发现迭代器是否已经失效。任何无效迭代器的使用都可能导致运行时错误，但程序不一定会崩溃，否则检查这种错误也许会容易些。

When using iterators, it is usually possible to write the program so that the range of code over which an iterator must stay valid is relatively short. It is important to examine each statement in this range to determine whether elements are added or removed and adjust iterator values accordingly.

使用迭代器时，通常可以编写程序使得要求迭代器有效的代码范围相对较短。然后，在该范围内，严格检查每一条语句，判断是否有元素添加或删除，从而相应地调整迭代器的值。


Team LiB
Previous Section Next Section