---

category: cs
tags:

• cs
• cpp
• 迭代器
• 计算机
  status: in-progress
  priority: “NULL”
  created: 2026-06-12
  updated: 2026-06-12

---

Reference:
https://zhuanlan.zhihu.com/p/661682470

1 自定义容器和迭代器的内涵

1.1自定义容器

自定义容器（Custom Containers）是用户根据特定需求创建的数据存储结构。它们不仅需要存储数据，还需要提供数据访问、插入、删除等操作的接口。每个自定义容器都应该有相应的迭代器（Iterators）来遍历容器中的元素。

迭代器是一个类似指针的对象，能够遍历容器中的元素。它提供了一种透明的方式来访问容器中的对象，无需关心容器的内部结构。

每种容器都有其特定的数据组织和存储方式，因此需要特定的迭代器来适配。例如，一个双向链表的迭代器需要能够前进和后退，而一个哈希表的迭代器则需要能够跳过空桶。

1.2 迭代器

迭代器本质上是类似指针的对象，在行为和用法上看起来非常像指针，但在底层实现上是一个封装了逻辑的类对象（class object）。

1. 行为像指针
   • 解引用、移动、比较、偏移的语法和指针完全一样，得益于操作符重载
2. 本质是对象
   • 迭代器内部通常是一个结构体或类，它不仅仅存了一个内存地址，还可能存了容器的引用或指针、额外的状态标记和逻辑检查。
   • C++ 的容器结构不同，而迭代器对象封装了这些差异，让你用统一的 ++ 操作，底层却根据容器类型执行不同的跳转逻辑。

2. 迭代器的类型

2.1 输入迭代器 (Input Iterator)

• 能力：只能单向遍历，且只能读取（一次遍历，只读）。
• 操作：*it (解引用), it++ (前缀/后缀), it == other, it != other.
• 限制：不能写回数据，不能回退。一旦遍历过，迭代器就失效（除非重新获取）。
• 典型容器/场景：std::istream_iterator (从输入流读取), 只读的单链表遍历。
• 算法示例：std::find, std::count。

2.2 输出迭代器 (Output Iterator)

• 能力：只能单向遍历，且只能写入（一次遍历，只写）。
• 操作：*it = value, it++.
• 限制：不能读取数据，不能回退。
• 典型容器/场景：std::ostream_iterator (写入输出流), std::back_inserter (向容器尾部插入)。
• 算法示例：std::copy (到输出流), std::generate。

2.3. 前向迭代器 (Forward Iterator)

• 能力：支持单向遍历，可以多次遍历，支持读写。
• 特点：它是输入和输出迭代器的超集。你可以多次从头开始遍历容器。
• 操作：支持输入/输出迭代器的所有操作，且可以多次解引用并修改。
• 典型容器：std::forward_list (单向链表), std::unordered_map, std::unordered_set。
• 算法示例：std::remove, std::unique。

2.4 双向迭代器 (Bidirectional Iterator)

• 能力：支持双向遍历（向前和向后），支持读写。
• 特点：在前向迭代器的基础上，增加了 --it (前缀) 和 it-- (后缀) 操作。
• 典型容器：std::list (双向链表), std::set, std::map, std::multiset, std::multimap。
• 算法示例：std::swap_ranges, std::rotate (部分实现)。

2.5. 随机访问迭代器 (Random Access Iterator)

• 能力：支持任意位置跳转，支持读写。
• 特点：功能最强大。除了双向迭代器的所有功能外，还支持指针算术运算。
• 操作：it + n, it - n, it += n, it -= n, it[n], it1 - it2 (计算距离), it1 < it2 (比较大小)。
• 典型容器：std::vector, std::deque, std::array, 原生数组指针。
• 算法示例：std::sort, std::binary_search, std::nth_element。

2.6 正向迭代器### (Forward Iterator / Normal Iterator)

• 定义：这通常指默认的迭代器行为。
• 行为：从容器头部（begin()）向尾部（end()）遍历。
• 对应关系：
  • 当我们说“正向迭代器”时，我们通常指的是容器提供的 iterator 类型。
  • 它的能力可以是前向、双向或随机访问（取决于容器）。
  • 例如：std::vector<int>::iterator 是一个随机访问的正向迭代器。

std::vector<int> v = {1, 2, 3};
for (auto it = v.begin(); it != v.end(); ++it) {
    // 正向遍历：1 -> 2 -> 3
    std::cout << *it << " ";
}

2.7 反向迭代器 (Reverse Iterator)

• 定义：一种只读的迭代器。
• 行为：遍历方式可以是正向或反向，但禁止修改所指向的元素。
• 核心机制：
  • operator* 返回的是 const T& 而不是 T&。
  • 尝试通过常量迭代器修改值会触发编译错误。
• 对应关系：
  • 容器通常提供两种迭代器类型：iterator (可读写) 和 const_iterator (只读)。
  • 在 const 对象上调用 begin() 会自动返回 const_iterator。
  • 你可以用 std::vector<int>::const_iterator 来遍历，也可以用 std::vector<int>::iterator 但将其赋值给 const T&（隐式转换）。

std::vector<int> v = {1, 2, 3};
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
    // 反向遍历：3 -> 2 -> 1
    std::cout << *rit << " ";
}

2.8 常量迭代器 (Constant Iterator / Const Iterator)

• 定义：一种只读的迭代器。
• 行为：遍历方式可以是正向或反向，但禁止修改所指向的元素。
• 核心机制：
  • operator* 返回的是 const T& 而不是 T&。
  • 尝试通过常量迭代器修改值会触发编译错误。
• 对应关系：
  • 容器通常提供两种迭代器类型：iterator (可读写) 和 const_iterator (只读)。
  • 在 const 对象上调用 begin() 会自动返回 const_iterator。
  • 你可以用 std::vector<int>::const_iterator 来遍历，也可以用 std::vector<int>::iterator 但将其赋值给 const T&（隐式转换）。

std::vector<int> v = {1, 2, 3};

// 方式1：显式使用 const_iterator
for (std::vector<int>::const_iterator it = v.begin(); it != v.end(); ++it) {
    // *it = 10; // 错误！不能修改
    std::cout << *it << " ";
}

// 方式2：const 容器自动返回常量迭代器
const std::vector<int> cv = {1, 2, 3};
for (auto it = cv.begin(); it != cv.end(); ++it) {
    // *it = 10; // 错误！
    std::cout << *it << " ";
}