迭代器库

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

迭代器是一种广义化的指针，它使得 C++ 程序可以通过统一的方式处理不同的数据结构（例如容器和范围 (C++20 起)。迭代器库提供了迭代器的定义，同时还提供了迭代器特征、适配器及相关的工具函数。

因为迭代器是指针的抽象，所以它们的语义是 C++ 的指针的大多数语义的泛化。这确保指针能够用于所有接受迭代器的函数模板。

迭代器分类

迭代器共有五 (C++17 前)六 (C++17 起)种：老式输入迭代器 (LegacyInputIterator) 、老式输出迭代器 (LegacyOutputIterator) 、老式向前迭代器 (LegacyForwardIterator) 、老式双向迭代器 (LegacyBidirectionalIterator) 、老式随机访问迭代器 (LegacyRandomAccessIterator) ，及老式连续迭代器 (LegacyContiguousIterator) (C++17 起)。

迭代器的分类的依据并不是迭代器的类型，而是迭代器所支持的操作。换句话说，某个类型只要支持相应的操作，就可以作为迭代器使用。例如，完整对象类型指针支持所有老式随机访问迭代器 (LegacyRandomAccessIterator) 要求的操作，于是任何需要老式随机访问迭代器 (LegacyRandomAccessIterator) 的地方都可以使用指针。

迭代器的所有类别（除了老式输出迭代器 (LegacyOutputIterator) 和老式连续迭代器 (LegacyContiguousIterator) ）能组织到层级中，其中更强力的迭代器类别（如老式随机访问迭代器 (LegacyRandomAccessIterator) ）支持较不强力的类别（例如老式输入迭代器 (LegacyInputIterator) ）的所有操作。如果迭代器落入这些类别之一且同时满足老式输出迭代器 (LegacyOutputIterator) 的要求，那么它被称为 可变 迭代器并且支持输入 还有 输出。非可变迭代器被称为 常 迭代器。

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

(C++20 起)
迭代器类别 操作和存储要求
     写           读      自增    自减    随机访问 连续存储
  无多趟     有多趟  
老式输出迭代器 (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，结果是具有某个类，枚举或基础类型 (C++11 前)对象类型 (C++11 起) T 的值，此类型被称为该迭代器的 值类型 。

输出迭代器 i 有一个可写入 (C++20 前)indirectly_writable 到 (C++20 起)该迭代器的非空类型集合；对于其中的每个类型 T，表达式 *i = o 在 o 的类型是 T 时合法。

每个定义了相等性 (C++20 前)的迭代器类型 X 都有一个对应的整数 (C++20 前)整数式 (C++20 起)类型，此类型被称为该迭代器的 差类型 。

可解性与有效性

与指向数组的通常指针保证存在一个指向该数组的尾后元素的指针值一样，任何迭代器类型也保证存在一个指向对应序列的尾后元素的迭代器值。这种值被称为 尾后 值。

迭代器 i 定义了表达式 *i 的值被称为 可解引用 的值。标准库 始终不会假设尾后值可解引用。

迭代器也可以具有不与任何序列关联的 奇异 值。大部分表达式对于奇异值的结果未定义，除了：

此时奇异值会和其他值一样被覆写。可解引用的值和尾后值始终不会是奇异值。

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

范围

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

对于两个迭代器 i 和 j，当且仅当在应用有限次表达式 ++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 == s 的迭代器 j 指向的元素为止的那些元素。

对于迭代器 i 和哨位 s，当且仅当在应用有限次表达式 ++i 使得 i == s 时，s 从 i 可及 。

如果 s 从 i 可及，那么 [i, s) 表示的范围 有效 。

计数范围

计数范围 i + [0, n) 在 n == 0 时为空；否则 i + [0, n) 指代数据结构中从 i 指向的元素开始到（但不包含，如果存在）应用了 n 次 ++i 的结果指向的元素为止的 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)
 指定类型为某个 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++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++14)
 创建拥有从实参推出的类型的 std::reverse_iterator
(函数模板)
(C++11)
 解引用结果为右值引用的迭代器适配器
(类模板)
(C++20)
 用于 std::move_iterator 的哨位适配器
(类模板)
(C++11)
 创建拥有从实参推出的类型的 std::move_iterator
(函数模板)
(C++20)
 适配一个迭代器类型及其哨位为一个公共迭代器类型
(类模板)
(C++20)
 用于知晓其边界的迭代器的默认哨位
(类)
(C++20)
 对到范围结尾距离进行跟踪的迭代器适配器
(类模板)
(C++20)
 始终与任何 weakly_incrementable 类型比较都不相等的哨位
(类)
用于在容器尾部插入的迭代器适配器
(类模板)
创建拥有从实参推出的类型的 std::back_insert_iterator
(函数模板)
用于在容器头部插入的迭代器适配器
(类模板)
创建拥有从实参推出的类型的 std::front_insert_iterator
(函数模板)
用于插入容器的迭代器适配器
(类模板)
创建拥有从实参推出的类型的 std::insert_iterator
(函数模板)

流迭代器

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

迭代器操作

定义于头文件 <iterator>
令迭代器前进给定的距离
(函数模板)
返回两个迭代器间的距离
(函数模板)
(C++11)
 令迭代器自增
(函数模板)
(C++11)
 令迭代器自减
(函数模板)
(C++20)
 令迭代器前进给定的距离或到给定的边界
(niebloid)
(C++20)
 返回迭代器与哨位间的距离，或范围起始与结尾间的距离
(niebloid)
(C++20)
 自增迭代器给定的距离或到边界
(niebloid)
(C++20)
 自减迭代器给定的距离或到边界
(niebloid)

范围访问

这些非成员函数提供对容器、通常数组，及 std::initializer_list 的通用接口。

定义于头文件 <array>
定义于头文件 <deque>
定义于头文件 <forward_list>
定义于头文件 <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)
 获得指向底层数组的指针
(函数模板)
定义于头文件 <ranges>
定义于头文件 <iterator>
定义于命名空间 std::ranges
(C++20)
 返回指向范围起始的迭代器
(定制点对象)
(C++20)
 返回指向只读范围起始的迭代器
(定制点对象)
(C++20)
 返回指示范围结尾的哨位
(定制点对象)
(C++20)
 返回指示只读范围结尾的哨位
(定制点对象)
(C++20)
 返回指向范围的逆向迭代器
(定制点对象)
(C++20)
 返回指向只读范围的逆向迭代器
(定制点对象)
(C++20)
 返回指向范围的逆向尾迭代器
(定制点对象)
(C++20)
 返回指向只读范围的逆向尾迭代器
(定制点对象)
(C++20)
 返回等于范围大小的整数
(定制点对象)
(C++20)
 返回等于范围大小的有符号整数
(定制点对象)
(C++20)
 检查范围是否为空
(定制点对象)
(C++20)
 获得指向连续范围的起始的指针
(定制点对象)
(C++20)
 获得指向只读连续范围的起始的指针
(定制点对象)

缺陷报告

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

缺陷报告 应用于 出版时的行为 正确行为
LWG 208 C++98 尾后迭代器不会持有奇异值 可能会持有奇异值
LWG 278 C++98 未定义迭代器的有效性 定义为始终不持有奇异值
LWG 324 C++98 输出迭代器具有值类型 改成具有可写入类型
来自“https://zh.cppreference.com/mwiki/index.php?title=cpp/iterator&oldid=75957”