Iterators 迭代器

对指针概念的泛化——对容器元素的指针

EG：

键值对的含义

• 键即值：set 中的每个元素都是唯一的，且元素本身就是键。

• 底层实现：set 是基于 红黑树 实现的，因此每个元素在底层是作为树节点存储的，且按照排序规则组织。

迭代器的底层元素

2. 图片中初始化方式的解释

初始化方式解析

1. arr 是一个普通的 C++ 数组：
• arr 是数组的起始地址，arr + Size 是数组的结束地址（不包含该位置）。
• 通过指定 [arr, arr + Size) 的范围，可以将数组的元素拷贝到容器中。

2. 构造函数的使用：
• STL 容器（如 list、set 和 vector）都提供了一个构造函数，接受两个迭代器作为参数，用于初始化容器。
• 这里的 arr 和 arr + Size 是数组的起始和结束指针，符合迭代器要求。

3. set 的特点：
• 在初始化时，set 会自动去重并排序（默认升序）。
• 如果数组中有重复元素，set 只会保留一个。例如：

3. 总结

• set 的键值对：set 中的元素本身既是键，也是值。它不存储键值对，而是单一值。

• 迭代器指向的元素：set 的迭代器指向的是集合中的元素值。

• 图片中的初始化方式：
• 使用数组的起始地址和结束地址初始化 STL 容器。
• set 会自动排序并去重，list 和 vector 则会直接按数组顺序存储元素。

原生指针也是一种迭代器

每个容器类型的Iterators由Containers自己来实现和封装细节，使所有iterators在外在形式上是一样的

迭代器的类型参数萃取器

迭代器类型

1. Input Iterator（输入迭代器）

• 最基本的迭代器类型

• 主要特性：
• 只读，单向，单遍访问
• 只能向前移动（++）
• 只能读取元素（*it）
• 不保证多次遍历会得到相同结果

• 典型用例：
• 从文件读取数据
• istream_iterator

2. Output Iterator（输出迭代器）

• 与输入迭代器相对

• 主要特性：
• 只写，单向，单遍访问
• 只能向前移动（++）
• 只能写入元素（*it = value）
• 不能保证写入的值可以被重新读取

• 典型用例：
• 写入文件
• ostream_iterator

3. Forward Iterator（前向迭代器）

• 功能增强版的输入迭代器

• 主要特性：
• 可读可写
• 只能向前移动（++）
• 可以多次遍历
• 多次遍历时保证相同顺序

• 典型用例：
• forward_list
• 单向链表

4. Bidirectional Iterator（双向迭代器）

• 比前向迭代器更强大

• 主要特性：
• 可读可写
• 可以向前（++）和向后（–）移动
• 可以多次遍历

• 典型用例：
• list
• set
• map
• 双向链表

5. Random Access Iterator（随机访问迭代器）

• 最强大的迭代器类型

• 主要特性：
• 可读可写
• 可以向前和向后移动
• 支持随机访问（it + n）
• 支持迭代器算术运算（+, -, +=, -=）
• 支持比较运算（<, >, <=, >=）

• 典型用例：
• vector
• deque
• 数组

继承关系

• 每个后继类型都包含前面类型的所有功能

• RandomAccessIterator 是功能最完整的迭代器

• 从上到下，功能逐渐增强

• 使用时应该使用满足需求的最低级别迭代器，以获得最大的灵活性

实际应用建议

1. 如果只需要单次遍历和读取，使用 Input Iterator

2. 如果只需要写入，使用 Output Iterator

3. 如果需要多次遍历，使用 Forward Iterator

4. 如果需要双向遍历，使用 Bidirectional Iterator

5. 如果需要随机访问，使用 Random Access Iterator