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

个人主页: 起名字真南的CSDN博客

个人专栏:

• 【数据结构初阶】 📘 基础数据结构
• 【C语言】 💻 C语言编程技巧
• 【C++】 🚀 进阶C++
• 【OJ题解】 📝 题解精讲

目录

📌 引言

在上一篇文章中，我们从零实现了一个

list

容器，包括节点结构、迭代器设计、增删查操作等。然而，对于一个成熟的容器来说，迭代器是不可或缺的部分，因为它提供了遍历和访问容器元素的标准接口。本篇文章将补充说明

list_iterator

的设计和实现，帮助大家深入理解迭代器的原理以及在

list

容器中的重要作用。

📌 1. 为什么

list

容器需要

list_iterator

list

是一种双向链表，节点之间的内存地址并不连续。为了支持容器的标准遍历接口，必须通过迭代器封装节点间的前后关系。

list_iterator

实现了

++

、

--

、

*

、

->

等操作符，使得我们可以在链表上使用 STL 的标准迭代器操作，并方便地对节点数据进行访问和修改。

📌 2.

list_iterator

的设计与实现

✨ 2.1

list_iterator

的基本结构

list_iterator

是一个模板类，内部封装了指向链表节点的指针

_node

。通过

_node

，迭代器可以在节点间移动，并访问节点的数据。

template<classT,classRef,classPtr>structlist_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

指针相等时，它们表示相同的位置。

booloperator==(const Self& other)const{return _node == other._node;}booloperator!=(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

的关键点如下：

1. 封装节点指针：list_iterator 通过持有 list_node 指针 _node 来访问和移动链表节点。
2. 重载操作符： - * 和 -> 用于访问节点数据。- ++ 和 -- 用于迭代器的前进和后退。- == 和 != 用于迭代器的比较。
3. list_iterator 与 list、list_node 的关系： - list_iterator 依赖 list_node 实现节点移动和数据访问。- list 通过 list_iterator 提供统一的接口，使链表可以通过迭代器进行遍历、插入和删除操作。

通过

list_iterator

，自定义的

list

容器具备了与 STL 容器一致的遍历能力，使链表在不连续内存结构中也可以支持标准的迭代器操作。