STL 2迭代器

1.迭代器

1.迭代器
1.抽象的指针：迭代器是一种行为类似指针的对象，提供对容器元素的间接访问。
2.统一接口：通过迭代器，算法可以操作任意容器（如 vector、list、map），无需关心容器的底层实现。

2 核心作用
1.遍历容器：替代直接操作容器内部结构，简化代码。
2.算法复用：STL 算法（如 std::sort、std::find）通过迭代器操作数据，不依赖具体容器。

2.输入迭代器

输入迭代器是迭代器分类中功能最弱的类型，其设计目标是单遍读取数据，具有以下特点：
std::istream_iterator

1.支持的操作：
1.自增操作（++it 或 it++）：移动到下一个元素。
2.解引用（*it）：读取当前元素的值（返回右值，不可修改）。
3.相等性比较（== 和 !=）：判断两个迭代器是否指向同一位置。

2.关键限制
1.不可重复读取：同一元素只能通过迭代器读取一次，多次解引用行为未定义（类似输入流）。
2.不可写操作：不能通过 *it 修改元素值（解引用结果为右值）。
3.不支持反向移动：无法通过 – 回到前一个元素。

3.输出迭代器

输出迭代器是迭代器分类中用于单遍写入数据的接口，其设计目标是高效地将数据写入目标位置。它具有以下特点：
ostream_iterator
1.支持的操作
1.自增操作（++it 或 it++）：移动到下一个写入位置。
2.解引用赋值（*it = value）：将值写入当前位置。
3.注意：输出迭代器的解引用结果必须是可修改的左值（Lvalue）。

2.关键限制
1.不可读取：不支持通过 *it 读取元素值，仅用于写入。
2.单遍写入：同一位置只能写入一次，多次写入行为未定义。
3.不支持反向移动：无法通过 – 回到前一个位置。

1.插入迭代器

插入迭代器（Insert Iterator）是输出迭代器（Output Iterator）的具体实现，二者的关系可概括为：
1.插入迭代器继承了输出迭代器的接口，并扩展了容器插入元素的能力。

2.常见插入迭代器
1.尾插迭代器（std::back_inserter）
适配容器：需支持 push_back()（如 vector、deque、list）。
2.头插迭代器（std::front_inserter）
适配容器：需支持 push_front()（如 list、deque）。
3.任意位置插入迭代器（std::inserter）
适配容器：需支持 insert(pos, value)（如所有标准容器）。

4.前向迭代器

前向迭代器是 STL 迭代器分类中的一种，它在输入 / 输出迭代器的基础上支持多次读写，并具有以下特点：
forward_list、unordered_set

1.支持的操作
1.输入迭代器的全部操作：自增（++）、解引用读取（*it）、相等比较（==/!=）。
2.输出迭代器的全部操作：解引用写入（*it = value）。
3.多次遍历：可保存迭代器状态并重复使用（如多次解引用同一位置）。

2.关键限制
1.单向移动：仅支持 ++ 操作，无法通过 – 回到前一个位置。
2.不支持随机访问：不能直接跳跃到任意位置（如 it + 5）。
前向迭代器适用于单向链表、哈希表等只能单向遍历的数据结构，
单向链表（std::forward_list）

5.双向迭代器

双向迭代器是 STL 迭代器分类中的一种，它在前向迭代器的基础上增加了反向移动能力，具有以下特点：
list、set、map
1.支持的操作
1.前向迭代器的全部操作：自增（++）、解引用读写（*it、*it = value）、多次遍历。
2.反向移动：支持递减操作（–it 或 it–），可向前遍历。

2.关键限制
1.不支持随机访问：无法直接跳跃到任意位置（如 it + 5），只能逐个移动。
2.必须成对使用 ++ 和 --：例如，若从 begin() 开始，必须通过 – 回到 begin() 之前的位置（如 rend()）。

6.随机访问迭代器

随机访问迭代器是 STL 迭代器分类中功能最强的类型，它在双向迭代器的基础上增加了随机访问能力，具有以下特点：
vector、deque、原生数组

1.支持的操作
1.双向迭代器的全部操作：自增（++）、自减（–）、解引用读写（*it、*it = value）。
2.随机位置跳转：支持 +=、-=、+、- 操作（如 it += 5 直接跳到第 5 个位置）。
3.位置比较：支持 <、>、<=、>= 比较迭代器位置。
4.下标访问：支持 it[n] 语法（等价于 *(it + n)）。

2.时间复杂度：所有操作均为 O (1)。

7.不同容器返回的迭代器类型

1.输入 / 输出迭代器

这类迭代器通常由适配器或流对象生成，而非直接来自容器：

2.前向迭代器

std::forward_list
std::unordered_set
std::unordered_map

3.双向迭代器

std::list
std::set
std::map
std::multiset
std::multimap

4.随机访问迭代器

std::vector
std::deque
std::array

5.特殊迭代器适配器

由算法或适配器生成的迭代器，
std::reverse_iterator
std::back_inserter
std::front_inserter
std::inserter

6.为什么 unordered_set 只提供前向迭代器？

哈希表的元素存储顺序不确定，且遍历时通常按桶的顺序访问，因此不支持双向移动。