迭代器

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

摘要

迭代器是泛型编程的核心，因为它们是容器和算法之间的接口：算法通常以迭代器作为参数，因此容器只需要提供一种使用迭代器访问其元素的方法。这使得编写一个能够操作许多不同类型的容器的泛型算法成为可能，即使这些容器像 向量 和 双向链表 一样不同。

STL 定义了几个与迭代器相关的不同概念，几个预定义的迭代器，以及用于操作迭代器的一组类型和函数。

描述

限制最严格的迭代器是 输入迭代器 和 输出迭代器，它们都允许“单次遍历”算法，但不一定支持“多次遍历”算法。 输入迭代器 只保证读取访问：可以解引用 输入迭代器 以获取它指向的值，但不一定能够通过输入迭代器赋值。类似地，输出迭代器 仅保证写入访问：可以通过 输出迭代器 赋值，但不一定能够引用该值。

前向迭代器 是对 输入迭代器 和 输出迭代器 的改进：它们支持 输入迭代器 和 输出迭代器 操作，还提供额外的功能。特别是，可以使用“多次遍历”算法来使用 前向迭代器。 前向迭代器 可以是 *常量*，在这种情况下，可以访问它指向的对象，但不能通过它赋值，也可以是 *可变的*，在这种情况下，可以同时执行这两项操作。

双向迭代器 类似于 前向迭代器，允许多次遍历算法。顾名思义，它们的不同之处在于它们支持双向移动：双向迭代器 可以递增以获取下一个元素，也可以递减以获取上一个元素。相比之下，前向迭代器 只需要支持正向移动。例如，用于遍历单链表的迭代器将是 前向迭代器，而用于遍历双链表的迭代器将是 双向迭代器。

最后，随机访问迭代器 允许指针运算：添加任意偏移量、下标运算、从一个迭代器减去另一个迭代器以查找距离等等。

大多数算法不是用单个迭代器表示的，而是用一个迭代器 *范围* 表示 [1]；符号[first, last)指的是从first到，但不包括last的所有迭代器。 [2] 请注意，范围可能为空，即first和last可能是同一个迭代器。还要注意，如果一个范围内有n个迭代器，那么符号[first, last)表示n+1个位置。这一点至关重要：操作于n事物上的算法通常需要n+1位置。例如，线性搜索 (find) 必须能够返回某个值来表明搜索不成功。

有时需要能够推断迭代器的一些属性：例如，解引用时返回的对象类型。有两种不同的机制来支持这种推断：一种较旧的机制称为 迭代器标签，另一种较新的机制称为iterator_traits [3].

概念

• 平凡迭代器
• 输入迭代器
• 输出迭代器
• 前向迭代器
• 双向迭代器
• 随机访问迭代器

类型

• 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

函数

• distance_type
• value_type
• iterator_category

• distance
• advance

• inserter
• front_inserter
• back_inserter

注释

[1] 范围对于 平凡迭代器 来说不是一个定义良好的概念，因为 平凡迭代器 无法递增：不存在下一个元素的概念。它们对于 输出迭代器 也不是一个定义良好的概念，因为无法比较两个 输出迭代器 的相等性。相等性对于范围的定义至关重要，因为只有通过将迭代器与最后一个元素进行相等性比较，才能遍历范围。

[2] 有时符号[first, last)指的是迭代器first, first+1, ..., last-1有时指的是这些迭代器指向的对象*first, *(first+1), ..., *(last-1)。在大多数情况下，从上下文可以很明显地看出指的是哪一个；在区别很重要的场合，符号将明确地限定为“迭代器范围”或“对象范围”。

[3] 该iterator_traits类依赖于 C++ 中的一个称为 *部分特化* 的特性。如今许多编译器都没有实现完整的标准；特别是，许多编译器不支持部分特化。如果您的编译器不支持部分特化，那么您将无法使用iterator_traits，您将不得不继续使用函数iterator_category, distance_type和value_type.

另请参见