随机存取迭代器


类别: 迭代器	组件类型: 概念

说明

随机存取迭代器是一种迭代器，它既提供递增又提供递减功能（就像双向迭代器），还提供固定时间的方法用于以任意大小的步长向前和向后移动。随机存取迭代器基本上提供了普通 C 指针算术的所有操作。

细化

双向迭代器、Less Than 可比较

关联类型

与双向迭代器相同

符号

`X`	一个随机存取迭代器模型的类型
`T`	值的类型`X`
`距离`	的距离类型`X`
`i`, `j`	类型的对象`X`
`t`	类型的对象`T`
`n`	类型的对象`距离`

定义

有效表达式

除了双向迭代器中定义的表达式，下列表达式也必须是有效的。

名称	表达式	类型要求	返回类型
迭代器加法	`i += n`		`X&`
迭代器加法	`i + n`或`n + i`		`X`
迭代器减法	`i -= n`		`X&`
迭代器减法	`i - n`		`X`
差异	`i - j`		`距离`
元素操作符	`i[n]`		可转换为`T`
元素赋值	`i[n] = t`	`X`是可变的	可转换为`T`

表达式语义

表达式的语义仅在与双向迭代器或Less Than 可比较中语义不同或未定义的地方进行定义。

名称	表达式	前提条件	语义	后置条件
向前运动	`i += n`	包括`i`其本身，后面一定有`n`可解引用或已经超过末尾的迭代器，前面或后面`i`，具体取决于`n`是正数还是负数。	如果`n > 0`，相当于执行`++i` `n`次。如果`n < 0`，相当于执行`n == 0` `n`次。如果`，这是一个空操作。 [1]`是可解引用的或已超过末尾的。	`i`与
迭代器加法	`i + n`或`n + i`	相同。`i += n`	相当于`{ X tmp = i; return tmp += n; }`. 这两种形式`i + n`和`n + i`是相同的。	结果是可解引用的或超过末尾的
迭代器减法	`i -= n`	包括`i`其本身，后面一定有`n`可解引用或已超过末尾的迭代器，后面或前面`i`，具体取决于`n`是正数还是负数。	相当于`i += (-n)`.	`i`与
迭代器减法	`i - n`	相同。`i -= n`	相当于`{ X tmp = i; return tmp -= n; }`.	结果是可解引用的或超过末尾的
差异	`i - j`	任一`i`可以从`j`或`j`可以从`i`访问，或两者都可以。	返回数字`n`如此`i == j + n`
元素操作符	`i[n]`	`i + n`存在并且是可解引用的。	相当于`*(i + n)` [2]
元素赋值	`i[n] = t`	`i + n`存在并且是可解引用的。	相当于`*(i + n) = t` [2]	`i[n]`是`t`.
Less	`i < j`	任一`i`可以从`j`或`j`可以从`i`的副本，或两者都可。 [3]	如小于比较 [4] 中所述

复杂性保证

对随机访问迭代器执行的所有操作均为摊销常数时间。 [5]

不变式

加法和减法的对称性	如果`i + n`定义明确，那么`i += n; i -= n;`和`(i + n) - n`为无操作。类似地，如果`i - n`定义明确，那么`i -= n; i += n;`和`(i - n) + n`则为无操作。
距离与加法之间的关系	如果`i - j`定义明确，那么`i == j + (i - j)`.
可达性和距离	如果`i`可以从`j`，那么`i - j >= 0`.
排序	`运算符 <`是一个严格的弱排序，如小于比较所定义。

模型

T*
vector<T>::iterator
vector<T>::const_iterator
deque<T>::iterator
deque<T>::const_iterator

备注

[1] “等效于”仅仅意味着i += n产生与以下情况相同的迭代器i已增量（递减）n倍。这并不意味着这是方法operator+=的实现方式；事实上，这并不是一个允许的实现。保证i += n为摊销常数时间，而与大小无关n. [5]

[2] 一个轻微的语法不一致：在 C 中，如果p是一个指针且n是一个 int，则p[n]和n[p]是等效的。但是，这一等效性不能保证适用于随机访问迭代器：仅i[n]需要受支持。但这不是一个特别重要的限制，因为以下等效性p[n]和n[p]基本上没有任何应用，除非用于晦涩的 C 竞赛。

[3] 在小于比较中定义的前提条件是i和j在运算符 <的域中。从本质上讲，这是一个该域的定义：它是这样的一对迭代器，其中一个迭代器可从另一个迭代器到达。

[4] 所有其他比较运算符具有相同的域，并根据运算符 <定义，因此它们具有与小于比较中描述的完全相同的语义。

[5] 这个复杂性保证实际上是随机访问迭代器作为不同概念存在的惟一原因。双向迭代器可以定义迭代器算法中的每个操作；事实上，算法advance和distance正是执行此类操作的。区别仅在于双向迭代器实现是线性时间，而随机访问迭代器必须支持以摊销常数时间随机访问元素。这对可以使用这两种类型的迭代器合理编写的算法类型具有重大影响。

另请参阅

LessThan 可比较, 琐碎迭代器, 双向迭代器, 迭代器概览