个人主页: 起名字真南的CSDN博客
个人专栏:
【数据结构初阶】 ? 基础数据结构【C语言】 ? C语言编程技巧【C++】 ? 进阶C++【OJ题解】 ? 题解精讲
目录
? 引言? 1. 为什么 `list` 容器需要 `list_iterator`? 2. `list_iterator` 的设计与实现✨ 2.1 `list_iterator` 的基本结构✨ 2.2 重载 `*` 和 `->` 操作符✨ 2.3 重载 `++` 和 `--` 操作符? 前置 `++` 和后置 `++`? 前置 `--` 和后置 `--` ✨ 2.4 重载比较运算符 `==` 和 `!=` ? 3. `list_iterator`、`list` 和 `list_node` 的关系✨ 3.1 `list_iterator` 与 `list_node`✨ 3.2 `list_iterator` 与 `list` ? 4. 使用 `list_iterator` 遍历链表? 5. const 迭代器的实现? 6. 迭代器失效问题? 总结
? 引言
在上一篇文章中，我们从零实现了一个 list 容器，包括节点结构、迭代器设计、增删查操作等。然而，对于一个成熟的容器来说，迭代器是不可或缺的部分，因为它提供了遍历和访问容器元素的标准接口。本篇文章将补充说明 list_iterator 的设计和实现，帮助大家深入理解迭代器的原理以及在 list 容器中的重要作用。
? 1. 为什么 list 容器需要 list_iterator
list 是一种双向链表，节点之间的内存地址并不连续。为了支持容器的标准遍历接口，必须通过迭代器封装节点间的前后关系。list_iterator 实现了 ++、--、*、-> 等操作符，使得我们可以在链表上使用 STL 的标准迭代器操作，并方便地对节点数据进行访问和修改。
? 2. list_iterator 的设计与实现
✨ 2.1 list_iterator 的基本结构
list_iterator 是一个模板类，内部封装了指向链表节点的指针 _node。通过 _node，迭代器可以在节点间移动，并访问节点的数据。
template<class T, class Ref, class Ptr>struct list_iterator { typedef list_node<T> Node; // 节点类型 typedef list_iterator<T, Ref, Ptr> Self; // 迭代器类型 Node* _node; // 当前节点的指针 // 构造函数，初始化为指定节点 list_iterator(Node* node = nullptr) : _node(node) {}};模板参数：
T：节点中数据的类型。Ref：* 操作符的返回类型，通常为 T& 或 const T&。Ptr：-> 操作符的返回类型，通常为 T* 或 const T*。 成员变量 _node：指向当前节点的指针，用于定位链表中的一个节点。
✨ 2.2 重载 * 和 -> 操作符
为了让迭代器可以像指针一样访问节点数据，我们重载了 * 和 -> 操作符。这两个操作符分别返回节点的数据值和数据地址。
Ref operator*() { return _node->_data; // 返回节点的数据引用}Ptr operator->() { return &_node->_data; // 返回节点数据的地址}operator*：返回当前节点的数据引用，类型为 Ref，通常为 T& 或 const T&。operator->：返回节点数据的地址，类型为 Ptr，通常为 T* 或 const T*。 这样一来，我们可以直接使用 *it 和 it-> 来访问节点的数据，例如：
*it += 10; // 修改当前节点的数据cout << it->value; // 访问节点数据成员✨ 2.3 重载 ++ 和 -- 操作符
在链表中，前进和后退一个节点的操作不是简单的指针加减，而是通过 _next 和 _prev 指针。因此，我们重载 ++ 和 -- 运算符，使迭代器能够在节点间移动。
? 前置 ++ 和后置 ++
Self& operator++() { _node = _node->_next; return *this;}Self operator++(int) { Self tmp(*this); // 创建当前迭代器的临时副本 _node = _node->_next; // 将 _node 指向下一个节点 return tmp; // 返回旧的迭代器}++：将 _node 指针移动到下一个节点，返回修改后的迭代器自身。后置 ++：先保存当前迭代器的副本，再将 _node 指向下一个节点，最后返回未修改的副本。 ? 前置 -- 和后置 --
Self& operator--() { _node = _node->_prev; return *this;}Self operator--(int) { Self tmp(*this); // 创建当前迭代器的临时副本 _node = _node->_prev; // 将 _node 指向前一个节点 return tmp; // 返回旧的迭代器}--：将 _node 指向前一个节点，返回修改后的迭代器自身。后置 --：先保存当前迭代器的副本，再将 _node 移动到前一个节点，最后返回旧的副本。 通过这两个运算符的重载，我们可以在链表上实现正向和反向遍历，符合 STL 迭代器的标准行为。
✨ 2.4 重载比较运算符 == 和 !=
为了判断两个迭代器是否指向相同的节点，我们重载了 == 和 != 运算符。当两个迭代器的 _node 指针相等时，它们表示相同的位置。
bool operator==(const Self& other) const { return _node == other._node;}bool operator!=(const Self& other) const { return _node != other._node;}operator==：比较两个迭代器的 _node 指针是否相等。operator!=：判断两个迭代器是否不相等，通常用于循环结束条件。 ? 3. list_iterator、list 和 list_node 的关系
✨ 3.1 list_iterator 与 list_node
list_iterator 依赖 list_node：list_iterator 通过 _node 指向 list_node，实现对链表节点的访问和操作。++ 和 -- 操作通过 _node->_next 和 _node->_prev 实现节点的前进和后退。数据访问依赖 list_node：* 和 -> 操作符的重载直接访问 _node->_data，即 list_node 中的数据域，使得迭代器可以返回节点中的数据。双向链接关系：list_node 的 _prev 和 _next 指针实现了双向链接，使得 list_iterator 可以方便地前后移动，而不需要依赖连续的内存地址。 ✨ 3.2 list_iterator 与 list
list 通过迭代器提供访问接口：list 的 begin() 和 end() 返回 list_iterator，分别指向链表的第一个节点和尾后节点。外部代码可以使用迭代器在 list 容器上进行遍历和访问。迭代器操作封装链表结构：list 的 insert、erase 等操作在返回迭代器时，允许用户在链表上插入和删除节点，保持接口一致性。迭代器失效问题：在 list 的 erase 等操作中，若迭代器失效，需要返回新的有效迭代器，这保证了链表操作的安全性。 ? 4. 使用 list_iterator 遍历链表
借助 list_iterator，我们可以像遍历数组那样遍历链表。例如，下面的代码展示了如何使用迭代器遍历自定义 list 容器。
list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);list<int>::iterator it = lt.begin();while (it != lt.end()) { cout << *it << " "; // 输出当前节点的数据 ++it; // 前进到下一个节点}在上述代码中，begin() 返回链表首节点的迭代器，end() 返回链表尾后位置的迭代器。通过 ++it 操作符，我们可以依次访问链表的每一个节点。
? 5. const 迭代器的实现
list_iterator 中使用了模板参数 Ref 和 Ptr，可以根据需求指定 T& 或 const T&，从而支持常量迭代器 const_iterator。当使用 const_iterator 时，数据不可被修改。
list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);list<int>::const_iterator it = lt.begin();while (it != lt.end()) { cout << *it << " "; // 仅能读取数据，不能修改 ++it;}在 const_iterator 中，Ref 和 Ptr 分别设置为 const T& 和 const T*，确保 *it 不能用于修改节点的数据。
? 6. 迭代器失效问题
在链表中删除或插入元素时，可能导致迭代器失效。例如，在 erase 删除某个节点后，指向该节点的迭代器将变为无效，继续使用会引发错误。因此，在 erase 函数中返回下一个有效迭代器，以确保遍历过程中不会访问失效的节点。
auto it = lt.begin();while (it != lt.end()) { if (*it % 2 == 0) { it = lt.erase(it); // 删除节点，返回下一个有效迭代器 } else { ++it; }}? 总结
通过 list_iterator，我们实现了自定义 list 容器的标准遍历方式。总结 list_iterator 的关键点如下：
list_iterator 通过持有 list_node 指针 _node 来访问和移动链表节点。重载操作符： * 和 -> 用于访问节点数据。++ 和 -- 用于迭代器的前进和后退。== 和 != 用于迭代器的比较。 list_iterator 与 list、list_node 的关系： list_iterator 依赖 list_node 实现节点移动和数据访问。list 通过 list_iterator 提供统一的接口，使链表可以通过迭代器进行遍历、插入和删除操作。 通过 list_iterator，自定义的 list 容器具备了与 STL 容器一致的遍历能力，使链表在不连续内存结构中也可以支持标准的迭代器操作。