|
大小: 6126
备注:
|
← 于2008-02-23 15:36:56修订的的版本11 ⇥
大小: 5475
备注: converted to 1.6 markup
|
| 删除的内容标记成这样。 | 加入的内容标记成这样。 |
| 行号 1: | 行号 1: |
| [[TableOfContents]] | ## page was renamed from 迭代子概述 <<TableOfContents>> |
| 行号 17: | 行号 18: |
| 最受限的迭代子是Input Iterator和Output Iterator，他们允许"单次遍历"算法但是不一定允许"多次遍历"算法。Input Iterator只保证读取访问，dereference一个Input Iterator，只能够保证能够读取它所指向的值，而不能够保证通过它赋予新的值。类似的，可以保证通过Output Iterator可以赋予新的值，但是不能保证能够读取它所指向的值。 | |
| 行号 18: | 行号 20: |
| Forward Iterators 是Input Iterators和Output Iterators的refinement：它们支持Input Iterator和Output Iterator的所有操作，并提供更多其它的操作。它允许"多次遍历"算法。Forward Iterator可以是只读的，可以通过它访问对象，但是不能通过它赋予新的值；也可以是可变的，就是既可读也可以赋予新的值。 | |
| 行号 19: | 行号 22: |
| The most restricted sorts of iterators are Input Iterators and Output Iterators, both of which permit "single pass" algorithms but do not necessarily support "multi-pass" algorithms. Input iterators only guarantee read access: it is possible to dereference an Input Iterator to obtain the value it points to, but not it is not necessarily possible to assign a new value through an input iterator. Similarly, Output Iterators only guarantee write access: it is possible to assign a value through an Output Iterator, but not necessarily possible to refer to that value. | Bidirectional Iterators和Forward Iterators类似，允许"多次遍历"算法。由名字可知，他们的不同之处在于移动的方向：Bidirectional Iterator允许自增使其指向下一个元素，也可以自减使其指向前一个元素。而Forward Iterator只需要支持单向移动。比如说，用来遍历单链表的迭代子就是一个Forward Iterator，而用来遍历双链表的迭代子是一个Bidirectional Iterator。 |
| 行号 21: | 行号 24: |
| Forward Iterators are a refinement of Input Iterators and Output Iterators: they support the Input Iterator and Output Iterator operations and also provide additional functionality. In particular, it is possible to use "multi-pass" algorithms with Forward Iterators. A Forward Iterator may be constant, in which case it is possible to access the object it points to but not to to assign a new value through it, or mutable, in which case it is possible to do both. | 最后，Random Access Iterator允许指针的算术运算：任意偏移量移动，下标操作，两个迭代子相减计算距离，等等。 |
| 行号 23: | 行号 26: |
| Bidirectional Iterators, like Forward Iterators, allow multi-pass algorithms. As the name suggests, they are different in that they support motion in both directions: a Bidirectional Iterator may be incremented to obtain the next element or decremented to obtain the previous element. A Forward Iterator, by contrast, is only required to support forward motion. An iterator used to traverse a singly linked list, for example, would be a Forward Iterator, while an iterator used to traverse a doubly linked list would be a Bidirectional Iterator. | 很多算法不是使用单个迭代子，而是使用一个区间的迭代子[1]。[first, last)这个记号表示所有的从first开始的迭代子，到last为止但是不包括last的所有迭代子。[2] 注意，一个区间可以是空的，也就是first和last是相同的。注意，如果区间内有n个迭代子，那么[first, last)需要n+1个位置表示。这是很重要的：对于n个东西进行操作的算法，常常需要有n+1个位置。比如说线性搜索(find)，必须能够返回表示搜索不成功的值。 |
| 行号 25: | 行号 28: |
| Finally, Random Access Iterators allow the operations of pointer arithmetic: addition of arbitrary offsets, subscripting, subtraction of one iterator from another to find a distance, and so on. Most algorithms are expressed not in terms of a single iterator but in terms of a range of iterators [1]; the notation [first, last) refers to all of the iterators from first up to, but not including, last. [2] Note that a range may be empty, i.e. first and last may be the same iterator. Note also that if there are n iterators in a range, then the notation [first, last) represents n+1 positions. This is crucial: algorithms that operate on n things frequently require n+1 positions. Linear search, for example (find) must be able to return some value to indicate that the search was unsuccessful. Sometimes it is important to be able to infer some properties of an iterator: the type of object that is returned when it is dereferenced, for example. There are two different mechanisms to support this sort of inferrence: an older mechanism called Iterator Tags, and a newer mechanism called iterator_traits [3]. |
有时候，必须能够从迭代子得出某些属性。比如说，要知道迭代子所指向的对象的类型。有两种不同的机制来得到属性：一种老的机制叫做Iterator Tags，一种新的机制叫做iterator_traits [3]。 |
| 行号 80: | 行号 79: |
| [1] Ranges are not a well-defined concept for Trivial Iterators, because a Trivial Iterator cannot be incremented: there is no such thing as a next element. They are also not a well-defined concept for Output Iterators, because it is impossible to compare two Output Iterators for equality. Equality is crucial to the definition of a range, because only by comparing an iterator for equality with the last element is it possible to step through a range. | [1] 在Trivial Iterator上没有明确定义区间这个概念，因为Trivial Iterator没有自增操作：没有下一个元素这样的东西。在Output Iterator上也没有明确定义区间，因为Output Iterator没有相等性比较运算。相等性比较是定义一个区间所必需的，因为只有与last判断相等性，才能完成一个区间的迭代。 |
| 行号 82: | 行号 81: |
| [2] Sometimes the notation [first, last) refers to the iterators first, first+1, ..., last-1 and sometimes it refers to the objects pointed to by those iterators: *first, *(first+1), ..., *(last-1). In most cases it will be obvious from context which of these is meant; where the distinction is important, the notation will be qualified explicitly as "range of iterators" or "range of objects". | [2] [first, last)这个标记有时候是指迭代子first, first+1, ..., last-1，有时候是指这些迭代子所指向的对象*first, *(first+1), ..., *(last-1)。在大多数情况下，从上下文可以知道标记所指的是什么。当区别是非常重要的时候，这个标记会被明确的用"迭代子的区间"或者"对象的区间"修饰。 |
| 行号 84: | 行号 83: |
| [3] The iterator_traits class relies on a C++ feature known as partial specialization. Many of today's compilers don't implement the complete standard; in particular, many compilers do not support partial specialization. If your compiler does not support partial specialization, then you will not be able to use iterator_traits, and you will instead have to continue using the functions iterator_category, distance_type, and value_type. | [3] iterator_traits类依赖于C++的一个称作模板偏特化(partial specialization)的语法特征。现在的很多编译器不能完全支持这一标准，甚至不少编译器完全不支持偏特化。如果你的编译器不支持偏特化，你就不能够使用iterator_traits，你必须依然使用函数iterator_category，distance_type和value_type。 |
迭代子 Iterators
1. 概述
迭代子是一种泛化的指针：它们是指向其他对象的对象。由名字可以看出，迭代子经常被用来迭代一个区间内的对象：如果一个迭代子指向一个区间内的某个元素，那么它可以自增以指向下一个元素。
迭代子是泛型编程的核心，因为它为容器和算法提供了一个接口。算法一般都使用迭代子作为参数，因此容器只要能提供访问元素的迭代子就可以了。这使得通用的泛型算法写出来可以对许多不同类型的容器进行操作，甚至像vector和双链表这样不大区别的容器。
STL定义了和迭代子相关的几个不同的概念，几个与定义的迭代子，和一组操作迭代子的类型和函数。
2. 描述
迭代子不是单独的一个概念，而是六个有层次关系的概念：其中有些概念只有很有限的一些操作，而另一些有更多的操作。被算法使用的五个概念是Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, and Random Access Iterator。第六个概念Trivial Iterator只是为了更清楚地描述其它迭代子概念而引入的。
最受限的迭代子是Input Iterator和Output Iterator，他们允许"单次遍历"算法但是不一定允许"多次遍历"算法。Input Iterator只保证读取访问，dereference一个Input Iterator，只能够保证能够读取它所指向的值，而不能够保证通过它赋予新的值。类似的，可以保证通过Output Iterator可以赋予新的值，但是不能保证能够读取它所指向的值。
Forward Iterators 是Input Iterators和Output Iterators的refinement：它们支持Input Iterator和Output Iterator的所有操作，并提供更多其它的操作。它允许"多次遍历"算法。Forward Iterator可以是只读的，可以通过它访问对象，但是不能通过它赋予新的值；也可以是可变的，就是既可读也可以赋予新的值。
Bidirectional Iterators和Forward Iterators类似，允许"多次遍历"算法。由名字可知，他们的不同之处在于移动的方向：Bidirectional Iterator允许自增使其指向下一个元素，也可以自减使其指向前一个元素。而Forward Iterator只需要支持单向移动。比如说，用来遍历单链表的迭代子就是一个Forward Iterator，而用来遍历双链表的迭代子是一个Bidirectional Iterator。
最后，Random Access Iterator允许指针的算术运算：任意偏移量移动，下标操作，两个迭代子相减计算距离，等等。
很多算法不是使用单个迭代子，而是使用一个区间的迭代子[1]。[first, last)这个记号表示所有的从first开始的迭代子，到last为止但是不包括last的所有迭代子。[2] 注意，一个区间可以是空的，也就是first和last是相同的。注意，如果区间内有n个迭代子，那么[first, last)需要n+1个位置表示。这是很重要的：对于n个东西进行操作的算法，常常需要有n+1个位置。比如说线性搜索(find)，必须能够返回表示搜索不成功的值。
有时候，必须能够从迭代子得出某些属性。比如说，要知道迭代子所指向的对象的类型。有两种不同的机制来得到属性：一种老的机制叫做Iterator Tags，一种新的机制叫做iterator_traits [3]。
3. 概念
- Trivial Iterator
- Input Iterator
- Output Iterator
- Forward Iterator
- Bidirectional Iterator
- Random Access Iterator
4. 类型
- istream_iterator
- ostream_iterator
- reverse_iterator
- reverse_bidirectional_iterator
- insert_iterator
- front_insert_iterator
- back_insert_iterator
- iterator_traits
- input_iterator_tag
- output_iterator_tag
- forward_iterator_tag
- bidirectional_iterator_tag
- random_access_iterator_tag
- input_iterator
- output_iterator
- forward_iterator
- bidirectional_iterator
- random_access_iterator
5. 函数
- distance_type
- value_type
- iterator_category
- distance
- advance
- inserter
- front_inserter
- back_inserter
6. 备注
[1] 在Trivial Iterator上没有明确定义区间这个概念，因为Trivial Iterator没有自增操作：没有下一个元素这样的东西。在Output Iterator上也没有明确定义区间，因为Output Iterator没有相等性比较运算。相等性比较是定义一个区间所必需的，因为只有与last判断相等性，才能完成一个区间的迭代。
[2] [first, last)这个标记有时候是指迭代子first, first+1, ..., last-1，有时候是指这些迭代子所指向的对象*first, *(first+1), ..., *(last-1)。在大多数情况下，从上下文可以知道标记所指的是什么。当区别是非常重要的时候，这个标记会被明确的用"迭代子的区间"或者"对象的区间"修饰。
[3] iterator_traits类依赖于C++的一个称作模板偏特化(partial specialization)的语法特征。现在的很多编译器不能完全支持这一标准，甚至不少编译器完全不支持偏特化。如果你的编译器不支持偏特化，你就不能够使用iterator_traits，你必须依然使用函数iterator_category，distance_type和value_type。