命名空间
变体
操作

迭代器库

来自 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 起)）。 迭代器库为迭代器、迭代器 traits、适配器和实用函数提供定义。

由于迭代器是指针的抽象，因此它们的语义是 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 前)类整数(C++20 起)类型，称为迭代器的差分类型。

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

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

对于表达式 *i 已定义的迭代器 i 的值称为可解引用。 标准库从不假定过尾值是可解引用的。

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

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

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

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

[编辑] 范围

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

如果存在表达式 ++i 的有限次应用序列使 i == j 成立，则迭代器 j 称为从迭代器 i 可达。 如果 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) 表示有效范围。

计数范围

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

计数范围 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++ 标准。

DR 应用到 已发布行为 正确行为
CWG 1181 C++98 数组类型不能是值类型 它们可以是
LWG 208 C++98 past-the-end 迭代器始终是非奇异的 它们可以是奇异的
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”