9.2. Iterators and Iterator Ranges9.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 列出迭代器为所有标准库容器类型所提供的运算。
Iterators on vector and deque Support Additional Operationsvector 和 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 总结了这些相关的操作符。
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. 第十一章中,我们将会了解到迭代器提供运算是使用标准库算法的基础。
9.2.1. Iterator Ranges9.2.1. 迭代器范围 |
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 如果满足以下条件,则可形成一个迭代器范围:
|
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 标记了一个有效的迭代器范围,于是:
When first equals last, the range is empty.
当 first 与 last 相等时,迭代器范围为空;
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
|
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. 使用迭代器时,通常可以编写程序使得要求迭代器有效的代码范围相对较短。然后,在该范围内,严格检查每一条语句,判断是否有元素添加或删除,从而相应地调整迭代器的值。 |