当前位置：首页 > article >正文

【C++】深入理解自定义 list 容器中的 list_iterator：迭代器实现详解

article 2024/11/16 5:39:44

个人主页: 起名字真南的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 提供统一的接口，使链表可以通过迭代器进行遍历、插入和删除操作。