命名空间
变体
操作

迭代器库

来自 cppreference.cn
< cpp
 
C++
 
迭代器库
迭代器概念
迭代器原语
算法概念与工具
间接可调用概念
常用算法要求
(C++20)
(C++20)
(C++20)
工具
(C++20)
迭代器适配器
范围访问
(C++11)(C++14)
(C++14)(C++14)  
(C++11)(C++14)
(C++14)(C++14)  
(C++17)(C++20)
(C++17)
(C++17)
 

迭代器是指针的推广，它允许 C++ 程序以统一的方式处理不同的数据结构（例如容器和范围(C++20 起)）。迭代器库提供了迭代器的定义，以及迭代器特性、适配器和实用函数。

由于迭代器是指针的抽象，其语义是指针在 C++ 中大部分语义的推广。这确保了所有接受迭代器的函数模板也适用于普通指针。

目录

[编辑] 迭代器类别

迭代器有五(C++17 前)六(C++17 起)种：LegacyInputIterator、LegacyOutputIterator、LegacyForwardIterator、LegacyBidirectionalIterator、LegacyRandomAccessIterator，以及LegacyContiguousIterator(C++17 起)。（另请参见最基本迭代器类型LegacyIterator。）

每种迭代器类别不是由特定类型定义的，而是由可以在其上执行的操作定义的。此定义意味着任何支持必要操作的类型都可以用作迭代器——例如，指针支持LegacyRandomAccessIterator所需的所有操作，因此指针可以在任何期望LegacyRandomAccessIterator的地方使用。

所有迭代器类别（除了LegacyOutputIterator）都可以组织成一个层次结构，其中更强大的迭代器类别（例如LegacyRandomAccessIterator）支持较弱类别（例如LegacyInputIterator）的操作。如果迭代器属于这些类别之一，并且还满足LegacyOutputIterator的要求，那么它被称为“可变”迭代器，并支持输入和输出。不可变迭代器被称为“常量”迭代器。

如果为满足迭代器类别要求而提供的所有操作都是constexpr 函数，则迭代器被称为constexpr迭代器。

 (C++20 起)
迭代器类别 操作和存储要求
     写入           读取      递增  递减     随机   
访问		  连续 
存储
不带
   多次   
传递		 带
   多次   
传递
LegacyIterator（传统迭代器） 必需
LegacyOutputIterator（传统输出迭代器） 必需 必需
LegacyInputIterator（传统输入迭代器）
（如果支持写入操作，则为可变） 		必需 必需
LegacyForwardIterator（传统前向迭代器）
（也满足LegacyInputIterator） 		必需 必需 必需
LegacyBidirectionalIterator（传统双向迭代器）
（也满足LegacyForwardIterator） 		必需 必需 必需 必需
LegacyRandomAccessIterator（传统随机访问迭代器）
（也满足LegacyBidirectionalIterator） 		必需 必需 必需 必需 必需
   LegacyContiguousIterator[1]
（也满足LegacyRandomAccessIterator） 		必需 必需 必需 必需 必需 必需
  1. ↑ LegacyContiguousIterator类别仅在 C++17 中正式指定，但在 C++17 之前的代码中，std::vector、std::basic_string、std::array和std::valarray的迭代器，以及指向 C 数组的指针通常被视为一个单独的类别。

注意：支持上表一行中所需操作的类型不一定属于相应的类别，完整要求列表请参见类别页面。

[编辑] 定义

[编辑] 类型和可写性

输入迭代器i支持表达式*i，结果是某种对象类型T的值，称为迭代器的值类型。

输出迭代器i拥有一组非空的类型，这些类型可写入(C++20 前)indirectly_writable(C++20 起)到迭代器；对于每个这样的类型T，表达式*i = o是有效的，其中o是类型T的值。

对于定义了相等性的每个迭代器类型X，存在一个对应的有符号整型(C++20 前)类似整型(C++20 起)类型，称为迭代器的差值类型。

[编辑] 解引用性与有效性

正如指向数组的普通指针保证存在指向数组最后一个元素之后位置的指针值一样，对于任何迭代器类型，也存在一个指向相应序列最后一个元素之后位置的迭代器值。这样的值称为末尾后值。

对于迭代器i，如果表达式*i已定义，则称其值为可解引用。 标准库从不假定末尾后值是可解引用的。

迭代器也可以具有与任何序列不关联的奇异值。大多数表达式的结果对于奇异值都是未定义的；唯一的例外是

  • 将非奇异值赋值给持有奇异值的迭代器，
  • 销毁持有奇异值的迭代器，以及
  • 对于满足DefaultConstructible要求的迭代器，使用值初始化的迭代器作为复制或移动(C++11 起)操作的源。

在这些情况下，奇异值像任何其他值一样被覆盖。可解引用值总是非奇异的。

无效迭代器是可能为奇异的迭代器。

[编辑] 范围

标准库中大多数对数据结构进行操作的算法模板都使用范围作为接口。

迭代器j被称为从迭代器i可达，当且仅当存在有限次应用表达式++i的序列，使得i == j。如果j可从i到达，则它们引用同一序列的元素。

范围是一对迭代器，它们指定了计算的开始和结束。[i, i)是一个空范围；通常，范围[i, j)指数据结构中从i所指向的元素开始，直到（但不包括）j所指向的元素。

范围[i, j)是有效的，当且仅当j可从i到达。

 (C++20 前)

范围可以由以下任一方式表示：

  • [i, s)，其中迭代器i和哨兵s指定计算的开始和结束（i和s可以具有不同的类型），或
  • i + [​0​, n)，其中迭代器i和计数n指定计算应用的开始和元素数量。
迭代器-哨兵范围

表示范围的迭代器和哨兵是可比较的。[i, s)为空，如果i == s；否则，[i, s)指的是数据结构中从i所指向的元素开始，直到（但不包括）第一个迭代器j所指向的元素（如果有的话），使得j == s。

当且仅当存在有限次应用表达式++i的序列，使得i == s，则称哨兵s从迭代器i可达。

如果s可从i到达，则[i, s)表示一个有效范围。

计数范围

计数范围i + [​0​, n)在n == 0时为空；否则，i + [​0​, n)指数据结构中从i所指向的元素开始，直到（但不包括）通过n次应用++i所指向的元素（如果有的话）。

计数范围i + [​0​, n)是有效的，当且仅当

  • n == 0；或者
  • 满足以下所有条件：
    • n为正，
    • i是可解引用的，并且
    • ++i + [​0​, --n)是有效的。
 (C++20 起)

将标准库中的函数应用于无效范围的结果是未定义的。

[编辑] 迭代器概念 (C++20 起)

一个基于概念的全新迭代器系统，它与 C++17 迭代器不同。虽然基本分类保持相似，但各个迭代器类别的要求有所不同。

定义于命名空间 std
(C++20)
 通过应用操作符*指定类型是间接可读的
(概念) [编辑]
(C++20)
 指定值可以写入迭代器引用的对象
(概念) [编辑]
(C++20)
 指定一个semiregular类型可以使用前置和后置增量运算符进行增量操作
(概念) [编辑]
(C++20)
 指定weakly_incrementable类型上的增量操作是保持相等性的，并且该类型是equality_comparable的
(概念) [编辑]
(C++20)(C++20)
 指定类型行为类似（有符号）整型
(仅供说明的概念*)[编辑]
(C++20)
 指定类型对象可以被增量和解引用
(概念) [编辑]
(C++20)
 指定类型是input_or_output_iterator类型的哨兵
(概念) [编辑]
(C++20)
 指定-运算符可应用于迭代器和哨兵，以常数时间计算它们的差值
(概念) [编辑]
(C++20)
 指定类型是一个输入迭代器，即其引用的值可读，并且可以进行前置和后置增量
(概念) [编辑]
(C++20)
 指定类型是给定值类型的输出迭代器，即该类型的值可以写入其中，并且可以进行前置和后置增量
(概念) [编辑]
(C++20)
 指定input_iterator是前向迭代器，支持相等比较和多趟遍历
(概念) [编辑]
(C++20)
 指定forward_iterator是双向迭代器，支持向后移动
(概念) [编辑]
(C++20)
 指定一个 bidirectional_iterator 是一个随机访问迭代器，支持常数时间步进和下标操作
(概念) [编辑]
(C++20)
 指定random_access_iterator是连续迭代器，引用内存中连续的元素
(概念) [编辑]

[编辑] 迭代器关联类型 (C++20 起)

定义于命名空间 std
(C++20)
 计算weakly_incrementable类型的差值类型
(类模板) [编辑]
(C++20)
 计算indirectly_readable类型的值类型
(类模板) [编辑]
(C++20)(C++20)(C++23)(C++20)(C++20)(C++20)
 计算迭代器的关联类型
(别名模板)[编辑]

[编辑] 迭代器原语

 提供迭代器属性的统一接口
(类模板) [编辑]
(C++20)
 用于指示迭代器类别的空类类型
(类) [编辑]
(C++17 中已弃用)
 基类，用于简化简单迭代器所需类型的定义
(类模板) [编辑]

[编辑] 迭代器定制点 (C++20 起)

定义于命名空间std::ranges
(C++20)
 将解引用对象的結果转换为其关联的右值引用类型
(定制点对象)[编辑]
(C++20)
 交换两个可解引用对象所引用的值
(定制点对象)[编辑]

[编辑] 算法概念和实用工具 (C++20 起)

一组概念和相关实用模板，旨在简化对常见算法操作的约束。

定义于头文件 <iterator>
定义于命名空间 std
间接可调用概念
(C++20)(C++20)
 指定可调用类型可以使用解引用indirectly_readable类型的结果进行调用
(概念) [编辑]
(C++20)
 指定可调用类型，当使用解引用indirectly_readable类型的结果调用时，满足predicate
(概念) [编辑]
(C++20)
 指定可调用类型，当使用解引用两个indirectly_readable类型的结果调用时，满足predicate
(概念) [编辑]
(C++20)
 指定可调用类型，当使用解引用两个indirectly_readable类型的结果调用时，满足equivalence_relation
(概念) [编辑]
(C++20)
 指定可调用类型，当使用解引用两个indirectly_readable类型的结果调用时，满足strict_weak_order
(概念) [编辑]
常用算法要求
(C++20)
 指定值可以从indirectly_readable类型移动到indirectly_writable类型
(概念) [编辑]
(C++20)
 指定值可以从indirectly_readable类型移动到indirectly_writable类型，并且该移动可以通过中间对象执行
(概念) [编辑]
(C++20)
 指定值可以从indirectly_readable类型复制到indirectly_writable类型
(概念) [编辑]
(C++20)
 指定值可以从indirectly_readable类型复制到indirectly_writable类型，并且该复制可以通过中间对象执行
(概念) [编辑]
(C++20)
 指定两个 indirectly_readable 类型所引用的值可以被交换
(概念) [编辑]
(C++20)
 指定两个indirectly_readable类型引用的值可以比较
(概念) [编辑]
(C++20)
 指定就地重新排序元素的算法的共同要求
(概念) [编辑]
(C++20)
 指定通过复制元素将已排序序列合并到输出序列中的算法的要求
(概念) [编辑]
(C++20)
 指定将序列排列成有序序列的算法的共同要求
(概念) [编辑]
工具
(C++20)
 计算在解引用一组indirectly_readable类型的结果上调用可调用对象的结果
(别名模板)[编辑]
(C++20)
 用于指定接受投影的算法约束的辅助模板
(类模板) [编辑]
(C++26)
 通过投影计算indirectly_readable类型的值类型
(别名模板)[编辑]

[编辑] 迭代器适配器

 用于反向遍历的迭代器适配器
(类模板) [编辑]
(C++14)
 创建从参数推断类型的std::reverse_iterator
(函数模板) [编辑]
 用于在容器末尾插入的迭代器适配器
(类模板) [编辑]
 创建从参数推断类型的std::back_insert_iterator
(函数模板) [编辑]
 用于在容器前端插入的迭代器适配器
(类模板) [编辑]
 创建从参数推断类型的std::front_insert_iterator
(函数模板) [编辑]
 用于在容器中插入的迭代器适配器
(类模板) [编辑]
 创建从参数推断类型的std::insert_iterator
(函数模板) [编辑]
(C++23)
 将迭代器转换为常量迭代器的适配器
(类模板) [编辑]
(C++23)
 为给定类型计算常量迭代器类型
(别名模板)[编辑]
(C++23)
 计算与常量迭代器一起使用的哨兵类型
(别名模板)[编辑]
(C++23)
 创建从参数推断类型的std::const_iterator
(函数模板) [编辑]
(C++23)
 创建从参数推断类型的std::const_sentinel
(函数模板) [编辑]
(C++11)
 解引用为右值的迭代器适配器
(类模板) [编辑]
(C++20)
 std::move_iterator的哨兵适配器
(类模板) [编辑]
(C++11)
 创建从参数推断类型的std::move_iterator
(函数模板) [编辑]
(C++20)
 将迭代器类型及其哨兵适配成一个通用迭代器类型
(类模板) [编辑]
(C++20)
 用于知道其范围边界的迭代器的默认哨兵
(类) [编辑]
(C++20)
 跟踪到范围末尾距离的迭代器适配器
(类模板) [编辑]
(C++20)
 始终与任何weakly_incrementable类型比较不相等的哨兵
(类) [编辑]

[编辑] 流迭代器

 从std::basic_istream读取的输入迭代器
(类模板) [编辑]
 写入std::basic_ostream的输出迭代器
(类模板) [编辑]
 从std::basic_streambuf读取的输入迭代器
(类模板) [编辑]
 写入std::basic_streambuf的输出迭代器
(类模板) [编辑]

[编辑] 迭代器操作

定义于头文件 <iterator>
 按给定距离前进迭代器
(函数模板) [编辑]
 返回两个迭代器间的距离
(函数模板) [编辑]
(C++11)
 递增迭代器
(函数模板) [编辑]
(C++11)
 递减迭代器
(函数模板) [编辑]
(C++20)
 将迭代器前进指定距离或到指定边界
(算法函数对象)[编辑]
(C++20)
 返回迭代器与哨兵之间，或范围开头与结尾之间的距离
(算法函数对象)[编辑]
(C++20)
 按给定距离或到边界递增迭代器
(算法函数对象)[编辑]
(C++20)
 按给定距离或到边界递减迭代器
(算法函数对象)[编辑]

[编辑] 范围访问 (C++11 起)

这些非成员函数模板为容器、普通数组和std::initializer_list提供了通用接口。

定义于头文件 <array>
在头文件 <deque> 中定义
在头文件 <flat_map> 中定义
在头文件 <flat_set> 中定义
在头文件 <forward_list> 中定义
在头文件 <inplace_vector> 中定义
定义于头文件 <iterator>
定义于头文件 <list>
定义于头文件 <map>
在头文件 <regex> 中定义
在头文件 <set> 中定义
在头文件 <span> 中定义
定义于头文件 <string>
定义于头文件 <string_view>
在头文件 <unordered_map> 中定义
定义于头文件 <unordered_set>
在头文件 <vector> 中定义
定义于命名空间 std
(C++11)(C++14)
 返回指向容器或数组开头的迭代器
(函数模板) [编辑]
(C++11)(C++14)
 返回指向容器或数组末尾的迭代器
(函数模板) [编辑]
(C++14)
 返回指向容器或数组开头的反向迭代器
(函数模板) [编辑]
(C++14)
 返回容器或数组的反向结束迭代器
(函数模板) [编辑]
(C++17)(C++20)
 返回容器或数组的大小
(函数模板) [编辑]
(C++17)
 检查容器是否为空
(函数模板) [编辑]
(C++17)
 获取指向底层数组的指针
(函数模板) [编辑]

[编辑] 缺陷报告

下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。

缺陷报告 应用于 发布时的行为 正确的行为
CWG 1181 C++98 数组类型不能是值类型 推导指引可以有尾随的requires子句
LWG 208 C++98 末尾后迭代器总是非奇异的 它们可以是奇异的
LWG 278 C++98 迭代器的有效性未定义 定义为始终非奇异
LWG 324 C++98 输出迭代器具有值类型 输出迭代器转而具有可写类型
LWG 407 C++98 奇异迭代器不能被销毁 允许
LWG 408
(N3066)		 C++98 奇异迭代器不能被复制 如果它们是值初始化的，则允许
LWG 1185
(N3066)		 C++98 LegacyForwardIterator、LegacyBidirectionalIterator
和LegacyRandomAccessIterator
总是满足LegacyOutputIterator		 它们可能不满足LegacyOutputIterator
LWG 1210
(N3066)		 C++98 迭代器奇异性和
可达性的定义依赖于容器		 转而依赖于序列
LWG 3009 C++17 <string_view>未提供
范围访问函数模板		 提供这些模板
LWG 3987 C++23 <flat_map>和<flat_set>未
提供范围访问函数模板		 提供这些模板
取自“https://cppreference.cn/mwiki/index.php?title=cpp/iterator&oldid=179898”