0


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

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

个人专栏:

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

目录

📌 引言

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

  1. list

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

  1. list_iterator

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

  1. list

容器中的重要作用。


📌 1. 为什么

  1. list

容器需要

  1. list_iterator
  1. list

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

  1. list_iterator

实现了

  1. ++

  1. --

  1. *

  1. ->

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


📌 2.

  1. list_iterator

的设计与实现

✨ 2.1

  1. list_iterator

的基本结构

  1. list_iterator

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

  1. _node

。通过

  1. _node

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

  1. template<classT,classRef,classPtr>structlist_iterator{typedef list_node<T> Node;// 节点类型typedef list_iterator<T, Ref, Ptr> Self;// 迭代器类型
  2. Node* _node;// 当前节点的指针// 构造函数,初始化为指定节点list_iterator(Node* node =nullptr):_node(node){}};
  • 模板参数:- T:节点中数据的类型。- Ref* 操作符的返回类型,通常为 T&const T&。- Ptr-> 操作符的返回类型,通常为 T*const T*
  • **成员变量 _node**:指向当前节点的指针,用于定位链表中的一个节点。

✨ 2.2 重载

  1. *

  1. ->

操作符

为了让迭代器可以像指针一样访问节点数据,我们重载了

  1. *

  1. ->

操作符。这两个操作符分别返回节点的数据值和数据地址。

  1. Ref operator*(){return _node->_data;// 返回节点的数据引用}
  2. Ptr operator->(){return&_node->_data;// 返回节点数据的地址}
  • **operator***:返回当前节点的数据引用,类型为 Ref,通常为 T&const T&
  • **operator->**:返回节点数据的地址,类型为 Ptr,通常为 T*const T*

这样一来,我们可以直接使用

  1. *it

  1. it->

来访问节点的数据,例如:

  1. *it +=10;// 修改当前节点的数据
  2. cout << it->value;// 访问节点数据成员

✨ 2.3 重载

  1. ++

  1. --

操作符

在链表中,前进和后退一个节点的操作不是简单的指针加减,而是通过

  1. _next

  1. _prev

指针。因此,我们重载

  1. ++

  1. --

运算符,使迭代器能够在节点间移动。

🚀 前置

  1. ++

和后置

  1. ++
  1. Self&operator++(){
  2. _node = _node->_next;return*this;}
  3. Self operator++(int){
  4. Self tmp(*this);// 创建当前迭代器的临时副本
  5. _node = _node->_next;// 将 _node 指向下一个节点return tmp;// 返回旧的迭代器}
  • **前置 ++**:将 _node 指针移动到下一个节点,返回修改后的迭代器自身。
  • **后置 ++**:先保存当前迭代器的副本,再将 _node 指向下一个节点,最后返回未修改的副本。

🚀 前置

  1. --

和后置

  1. --
  1. Self&operator--(){
  2. _node = _node->_prev;return*this;}
  3. Self operator--(int){
  4. Self tmp(*this);// 创建当前迭代器的临时副本
  5. _node = _node->_prev;// 将 _node 指向前一个节点return tmp;// 返回旧的迭代器}
  • **前置 --**:将 _node 指向前一个节点,返回修改后的迭代器自身。
  • **后置 --**:先保存当前迭代器的副本,再将 _node 移动到前一个节点,最后返回旧的副本。

通过这两个运算符的重载,我们可以在链表上实现正向和反向遍历,符合 STL 迭代器的标准行为。


✨ 2.4 重载比较运算符

  1. ==

  1. !=

为了判断两个迭代器是否指向相同的节点,我们重载了

  1. ==

  1. !=

运算符。当两个迭代器的

  1. _node

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

  1. booloperator==(const Self& other)const{return _node == other._node;}booloperator!=(const Self& other)const{return _node != other._node;}
  • **operator==**:比较两个迭代器的 _node 指针是否相等。
  • **operator!=**:判断两个迭代器是否不相等,通常用于循环结束条件。

📌 3.

  1. list_iterator

  1. list

  1. list_node

的关系

✨ 3.1

  1. list_iterator

  1. 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

  1. list_iterator

  1. list
  • list 通过迭代器提供访问接口listbegin()end() 返回 list_iterator,分别指向链表的第一个节点和尾后节点。外部代码可以使用迭代器在 list 容器上进行遍历和访问。
  • 迭代器操作封装链表结构listinserterase 等操作在返回迭代器时,允许用户在链表上插入和删除节点,保持接口一致性。
  • 迭代器失效问题:在 listerase 等操作中,若迭代器失效,需要返回新的有效迭代器,这保证了链表操作的安全性。

📌 4. 使用

  1. list_iterator

遍历链表

借助

  1. list_iterator

,我们可以像遍历数组那样遍历链表。例如,下面的代码展示了如何使用迭代器遍历自定义

  1. list

容器。

  1. list<int> lt;
  2. lt.push_back(1);
  3. lt.push_back(2);
  4. lt.push_back(3);
  5. list<int>::iterator it = lt.begin();while(it != lt.end()){
  6. cout <<*it <<" ";// 输出当前节点的数据++it;// 前进到下一个节点}

在上述代码中,

  1. begin()

返回链表首节点的迭代器,

  1. end()

返回链表尾后位置的迭代器。通过

  1. ++it

操作符,我们可以依次访问链表的每一个节点。


📌 5. const 迭代器的实现

  1. list_iterator

中使用了模板参数

  1. Ref

  1. Ptr

,可以根据需求指定

  1. T&

  1. const T&

,从而支持常量迭代器

  1. const_iterator

。当使用

  1. const_iterator

时,数据不可被修改。

  1. list<int> lt;
  2. lt.push_back(1);
  3. lt.push_back(2);
  4. lt.push_back(3);
  5. list<int>::const_iterator it = lt.begin();while(it != lt.end()){
  6. cout
  7. <<*it <<" ";// 仅能读取数据,不能修改++it;}

  1. const_iterator

中,

  1. Ref

  1. Ptr

分别设置为

  1. const T&

  1. const T*

,确保

  1. *it

不能用于修改节点的数据。


📌 6. 迭代器失效问题

在链表中删除或插入元素时,可能导致迭代器失效。例如,在

  1. erase

删除某个节点后,指向该节点的迭代器将变为无效,继续使用会引发错误。因此,在

  1. erase

函数中返回下一个有效迭代器,以确保遍历过程中不会访问失效的节点。

  1. auto it = lt.begin();while(it != lt.end()){if(*it %2==0){
  2. it = lt.erase(it);// 删除节点,返回下一个有效迭代器}else{++it;}}

📌 总结

通过

  1. list_iterator

,我们实现了自定义

  1. list

容器的标准遍历方式。总结

  1. list_iterator

的关键点如下:

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

通过

  1. list_iterator

,自定义的

  1. list

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


标签: c++ list windows

本文转载自: https://blog.csdn.net/weixin_74837455/article/details/143650309
版权归原作者 起名字真南 所有, 如有侵权,请联系我们删除。

“【C++】深入理解自定义 list 容器中的 list_iterator:迭代器实现详解”的评论:

还没有评论