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

C++：list类（迭代器）

news 来源：原创 2024/9/19 13:24:09

目录

前言

数据结构

push_back

push_front

默认构造函数

拷贝构造函数

list迭代器

结构 

构造函数

*运算符重载

->运算符重载

前置++运算符重载

后置++运算符重载

前置--运算符重载

后置--运算符重载

!=运算符重载

==运算符重载

list迭代器完整代码

begin和end

swap

赋值重载函数

insert

erase

迭代器失效问题

pop_back

pop_front

clear

析构函数

size

empty

完整代码

前言

list是链表的意思

它属于链表中的带头双向循环链表

建议先掌握数据结构中的链表

C数据结构：单链表-CSDN博客

C数据结构：双向链表（带头循环）_c带头双向循环链表-CSDN博客

数据结构

首先我们需要一个链表的节点

template<class T>
struct ListNode
{T _data;ListNode* _next;ListNode* _prev;ListNode(const T& data = T()):_data(data),_next(nullptr),_prev(nullptr){}
};

因为这个ListNode类节点里面的内容可以是公开的，所以使用了struct默认即为public，当然也可以使用class来定义类，只需注意使用访问限定符即可

双向链表当然需要next和prev两个指针来指向后面和前面

类中还定义了一个默认构造函数用来构造节点

成员变量和成员函数放置的顺序前后都是可以的，但通常会把成员变量放到最下面

template<class T>
class list
{typedef ListNode<T> Node;
public:private:Node* _head;size_t _size = 0;
};

Node*指针指向链表头节点，我们还可以定义一个size成员函数，这样可以在计算链表大小的时候减少遍历节点次数

push_back

void push_back(const T& data)
{Node* newnode = new Node(data);Node* tail = _head->prev;tail->_next = newnode;newnode->_next = _head;newnode->_prev = tail;_head->_prev = newnode;_size++;
}

生成新节点，将它插入到最后面即可 

push_front

void push_front(const T& data)
{Node* newnode = new Node;Node* next = _head->_next;_head->_next = newnode;newnode->_prev = _head;newnode->_next = next;next->_prev = newnode;insert(begin(), data);
}

生成新节点，插入到_head的下一个位置即可

默认构造函数

list()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}

构造出我们的哨兵位头节点，并初始化next和prev指针和size大小

因为这段默认构造函数在其他的成员函数内部也可能会使用，并且默认构造函数不方便显示调用，所以我们可以把这段代码用一个函数来封装起来，方便其他成员函数使用

void EmptyInit()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}list()
{EmptyInit();
}

这样我们把空初始化的逻辑放到EmptyInit函数中即可

拷贝构造函数

list(const list<T>& lt):_head(lt._head),_size(lt._size)
{}

这是经典的错误写法！ 

这里只是将lt里面的_head按字节拷贝给了this的_head（浅拷贝）

所以最终是两个_head用同一个链表，同一块空间

为了避免这个问题，我们需要重新生成一段空间来完成深拷贝

list(const list<T>& lt)
{EmptyInit();for (auto& x : lt){push_back(x);}
}

复用EmptyInit和push_back的逻辑

因为EmptyInit会初始化出一个哨兵位头节点，我们只需要在这个头节点后面依次插入lt里面的元素即可，因为push_back也是会开新空间的

但是这里的遍历是还完不成的，因为范围for需要有begin，end，重载!=函数，这些函数又需要我们的迭代器，但是我们类中目前是还没有实现的，所以我们还需要先实现完成迭代器和这些成员函数才能完成这个拷贝构造

list迭代器

这里迭代器的实现就没有前面vector和string的那么简单了，因为它们两个的迭代器都可以通过指针的+-来遍历整个容器，但是list由于空间的不连续，所以不能简单的只是使用指针进行+-运算，而是需要我们手动完成对++，--这些运算符的重载操作

结构 

template<class T, class Ref, class Ptr>
struct list_iterator
{typedef ListNode<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;
};

这里需要有三个模板的支撑，前面的T代表数据类型，后面的Ref和Ptr代表的是引用和指针的意思

为什么要有这两个模板？

迭代器分为普通迭代器和const迭代器，稍后我们实现完普通迭代器后就会发现const迭代器我们需要重新拷贝一份普通迭代器的板子加上const，虽然能完成功能，但是这样代码的观赏性就不是很好，所以加上这两个模板后我们就可以在一个list_iterator类中完成iterator和const_iterator

具体讲解参考下文 

构造函数

list_iterator(Node* node):_node(node)
{}

我们可以用一个node的节点来构造我们的list_iterator类

*运算符重载

Ref operator*()
{return _node->_data;
}

当我们外面定义的迭代器是it = begin()时，我们*it返回的当然就需要是it里面的数据了，所以我们需要返回节点里的数据 

->运算符重载

Ptr operator->()
{return &_node->_data;
}

->也是需要返回数据，但这里我们为什么返回的是一个数据的地址？

当我们在外面调用 it->_变量 时，编译器其实调用的是it.operator->()->_变量

这里有两个箭头，第一个箭头就是调用了我们自己写的operator函数，而第二个就是把拿到的这个数据的地址解引用拿到了里面的数据

但是为了可读性，编译器会特殊处理掉这里的一个->，所以我们只需要一个->就可以完成解引用操作

前置++运算符重载

Self& operator++()
{_node = _node->_next;return *this;
}

++后当然就是往链表里的下一个节点next走，所以我们在operator里面需要让当前iterator里面的成员变量_node指向它的next即可 

后置++运算符重载

Self operator++(int)
{Self tmp = *this;_node = _node->_next;return tmp;
}

和前置++一样

但是我们需要提前用一个tmp来保存原来的位置然后返回，这也是后置++自己的特点 

前置--运算符重载

Self& operator--()
{_node = _node->_prev;return *this;
}

--当然就是往前走，也就是使用prev指针往前跳 

后置--运算符重载

Self operator--(int)
{Self tmp = _node;_node = _node->_prev;return tmp;
}

和后置++一样的需要tmp保存并返回tmp 

!=运算符重载

bool operator!=(const Self& s) const
{return _node != s._node;
}

 判断两个迭代器不相等的逻辑当然就是比较两个节点是否是同一个

==运算符重载

bool operator==(const Self& s) const
{return _node == s._node;
}

和前面的!=运算符重载一样

这样就完成了

当我们在list类中定义迭代器iterator的时候我们是这样定义的

typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;

这样就完美的完成了iterator和const_iterator，因为iterator和const_iterator的本质就是解引用逻辑后的数据能否改变的问题，所以我们把它们定义成了两个类模板，这样就可以只用一个list_iterator类来完成iterator和const_iterator

否则我们就需要定义两个类，list_iterator和const_list_iterator来分别完成iterator和const_iterator，这样代码的可读性就降低了

list迭代器完整代码

template<class T, class Ref, class Ptr>
struct list_iterator
{typedef ListNode<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp = *this;_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp = _node;_node = _node->_prev;return tmp;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}
};

begin和end

iterator begin()
{//return iterator(_head->_next);return _head->_next;
}iterator end()
{return _head;
}const_iterator begin() const
{return _head->_next;
}const_iterator end() const
{return _head;
}

开始位置当然就是哨兵位头节点的下一个位置了

结束位置当然就是最后一个数据的下一个位置，也就是我们的哨兵位头节点的位置

这里明明返回值是iterator，但为什么我们可以返回一个Node*类型的指针？

C++的单参数构造函数是支持隐式类型转换的

所以我们不仅仅可以使用iterator(_head)这样的模式来构造一个iterator来返回

还可以直接返回_head来隐式类型转换成iterator类

因为这个类的构造函数就是单参数构造函数

swap

void swap(list<T> lt)
{std::swap(lt._head, _head);std::swap(lt._size, _size);
}

赋值重载函数

list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}

和前面vector和string的逻辑相同，现代写法 

insert

iterator insert(iterator pos, const T& data)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(data);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return newnode;
}

只需要在pos节点位置的前面插入一个节点数据为data的即可，和数据结构中的insert一致

逻辑也很简单

完成了insert之后我们是可以直接复用insert来简单的实现push_back和push_front的

void push_back(const T& data)
{insert(end(), data);
}void push_front(const T& data)
{insert(begin(), data);
}

erase

iterator erase(iterator pos)
{Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;prev->_next = next;next->_prev = prev;--_size;delete del;return next;
}

erase的逻辑也是和数据结构中的erase一致，思路比较简单

要注意的就是注意释放掉删除的那块空间，防止内存泄漏

所以完成了erase，那么pop_back和pop_front就很容易了

迭代器失效问题

list的insert和erase也是存在迭代器失效的问题的，具体细节可以参考vector中的迭代器失效问题

C++：vector类（default关键字，迭代器失效）-CSDN博客

pop_back

void pop_back()
{erase(--end());
}

pop_front

void pop_front()
{erase(begin());
}

clear

void clear()
{auto it = begin();while (it != end()){it = erase(it);// it++ 错误写法：erase后迭代器失效}
}

循环遍历整个链表，将除了哨兵位头节点的其他节点全部删除，删除哨兵位头节点的任务当然是交给析构函数了

只需要复用erase删除即可

析构函数

~list()
{clear();delete _head;_head = nullptr;_size = 0;
}

 首先复用clear将除了哨兵位头节点的全部节点删除

然后手动删除哨兵位头节点即可

size

size_t size() const
{return _size;
}

empty

bool empty() const
{return _size == 0;
}

完整代码

#pragma once#include<iostream>
using namespace std;namespace lyw
{template<class T>struct ListNode{T _data;ListNode* _next;ListNode* _prev;ListNode(const T& data = T()):_data(data),_next(nullptr),_prev(nullptr){}};template<class T, class Ref, class Ptr>struct list_iterator{typedef ListNode<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp = *this;_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp = _node;_node = _node->_prev;return tmp;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};template<class T>class list{typedef ListNode<T> Node;public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){//return iterator(_head->_next);return _head->_next; // 单参数构造函数支持隐式类型转换}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void EmptyInit(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){EmptyInit();}list(initializer_list<T> il){EmptyInit();for (auto& x : il){push_back(x);}}// 浅拷贝//list(const list<T>& lt)//	:_head(lt._head)//	,_size(lt._size)//{}list(const list<T>& lt){EmptyInit();for (auto& x : lt){push_back(x);}}list<T>& operator=(list<T> lt){swap(lt);return *this;}void swap(list<T> lt){std::swap(lt._head, _head);std::swap(lt._size, _size);}~list(){clear();delete _head;_head = nullptr;_size = 0;}void clear(){auto it = begin();while (it != end()){it = erase(it);// it++ 错误写法：erase后迭代器失效}}iterator insert(iterator pos, const T& data){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(data);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return newnode;}iterator erase(iterator pos){Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;prev->_next = next;next->_prev = prev;--_size;delete del;return next;}void push_back(const T& data){//Node* newnode = new Node(data);//Node* tail = _head->prev;//tail->_next = newnode;//newnode->_next = _head;//newnode->_prev = tail;//_head->_prev = newnode;//_size++;insert(end(), data);}void push_front(const T& data){//Node* newnode = new Node;//Node* next = _head->_next;//_head->_next = newnode;//newnode->_prev = _head;//newnode->_next = next;//next->_prev = newnode;insert(begin(), data);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}size_t size() const{return _size;}bool empty() const{return _size == 0;}private:Node* _head;size_t _size = 0;};
}

完

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • Spring SSM框架--MVC
  • [数据集][目标检测]手钳检测数据集VOC+YOLO格式141张1类别
  • 一：《Python基础语法汇总》— 数据类型与输入输出
  • sql总结
  • C++入门——21特殊的类
  • PostgreSQL下载、安装（Windows 10/11 64位）详细教程【超详细，保姆级教程！！！】
  • python——常见创建型设计模式
  • 仿RabbitMq实现简易消息队列正式篇(路由匹配篇)
  • BFS解决单源最短路问题
  • MySql 高阶二（SQL 性能分析）
  • QT翻金币小游戏（含音频图片文件资源）
  • c#使用Microsoft.Office.Interop.Word提示无法嵌入或操作型“ApplicationClass”。请改用试用的接口。
  • day45-dynamic programming-part12-8.16
  • Python、R用RFM模型、机器学习对在线教育用户行为可视化分析|附数据、代码
  • 【排序算法】八大排序（上）（c语言实现）（附源码）
  • css选择器
  • docker-consul
  • gcc介绍及安装
  • js写一个简单的选项卡
  • log4j2输出到kafka
  • oldjun 检测网站的经验
  • Selenium实战教程系列（二）---元素定位
  • windows-nginx-https-本地配置
  • 编写符合Python风格的对象
  • 大数据与云计算学习：数据分析（二）
  • 和 || 运算
  • 排序算法学习笔记
  • 使用agvtool更改app version／build
  • 我的面试准备过程--容器(更新中)
  • 【运维趟坑回忆录 开篇】初入初创, 一脸懵
  • postgresql行列转换函数
  • 如何通过报表单元格右键控制报表跳转到不同链接地址 ...
  • ​猴子吃桃问题：每天都吃了前一天剩下的一半多一个。
  • #、%和$符号在OGNL表达式中经常出现
  • （1）虚拟机的安装与使用,linux系统安装
  • （7）摄像机和云台
  • （C#）if (this == null)？你在逗我，this 怎么可能为 null！用 IL 编译和反编译看穿一切
  • （ISPRS，2021）具有遥感知识图谱的鲁棒深度对齐网络用于零样本和广义零样本遥感图像场景分类
  • (libusb) usb口自动刷新
  • （Matalb回归预测）PSO-BP粒子群算法优化BP神经网络的多维回归预测
  • （动态规划）5. 最长回文子串 java解决
  • （附源码）springboot 房产中介系统 毕业设计 312341
  • （附源码）springboot助农电商系统 毕业设计 081919
  • （黑马出品_高级篇_01）SpringCloud+RabbitMQ+Docker+Redis+搜索+分布式
  • (解决办法)ASP.NET导出Excel，打开时提示“您尝试打开文件'XXX.xls'的格式与文件扩展名指定文件不一致
  • （六）c52学习之旅-独立按键
  • （六）vue-router+UI组件库
  • （一）u-boot-nand.bin的下载
  • （转）memcache、redis缓存
  • (自用)网络编程
  • .gitignore文件忽略的内容不生效问题解决
  • .mp4格式的视频为何不能通过video标签在chrome浏览器中播放？
  • .NET 4.0中使用内存映射文件实现进程通讯
  • .NET CF命令行调试器MDbg入门(一)
  • .NET8使用VS2022打包Docker镜像