命名空间
变体
操作

迭代器库

来自 cppreference.com
< 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 中正式规范，但 std::vector、std::basic_string、std::array 和 std::valarray 的迭代器，以及指向 C 数组的指针，通常在 C++17 之前的代码中被视为一个单独的类别。

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

[编辑] 定义

[编辑] 类型和可写性

输入迭代器 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 起) 操作的来源。

在这些情况下，单一值将以与任何其他值相同的方式被覆盖。可解引用的值始终是非单一的。

无效迭代器是指可能为单一的迭代器。

[编辑] 范围

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

迭代器 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。

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

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

计数范围

计数范围 i + [​0​, n) 为空，如果 n == 0；否则，i + [​0​, n) 引用数据结构中的 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 是一个连续迭代器，它引用内存中连续的元素
(概念) [编辑]

[编辑] 迭代器关联类型

在命名空间 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 中已弃用)
 基类，用于简化简单迭代器的必需类型的定义
(类模板) [编辑]

[编辑] 迭代器定制点

定义在命名空间 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)
 将迭代器向后移动给定距离或移动到边界
(niebloid)[编辑]

[编辑] 范围访问

这些非成员函数模板为容器、普通数组和 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 越界迭代器始终是非单一的 它们可以是单一的
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=175988"