|
大小: 6002
备注:
|
大小: 5433
备注:
|
| 删除的内容标记成这样。 | 加入的内容标记成这样。 |
| 行号 17: | 行号 17: |
| 最受限的迭代子是Input Iterator和Output Iterator，他们允许"单次遍历"算法但是不一定允许"多次遍历"算法。Input Iterator只保证读取访问，dereference一个Input Iterator，只能够保证能够读取它所指向的值，而不能够保证通过它赋予新的值。类似的，可以保证通过Output Iterator可以赋予新的值，但是不能保证能够读取它所指向的值。 | |
| 行号 18: | 行号 19: |
| Forward Iterators 是Input Iterators和Output Iterators的refinement：它们支持Input Iterator和Output Iterator的所有操作，并提供更多其它的操作。它允许"多次遍历"算法。Forward Iterator可以是只读的，可以通过它访问对象，但是不能通过它赋予新的值；也可以是可变的，就是既可读也可以赋予新的值。 | |
| 行号 19: | 行号 21: |
| 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: | 行号 23: |
| 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. 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. 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. |
最后，Random Access Iterator允许指针的算术运算：任意偏移量移动，下标操作，两个迭代子相减计算距离，等等。 |
| 行号 80: | 行号 78: |
| [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: | 行号 80: |
| [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: | 行号 82: |
| [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。