C++——list模拟实现

目录

前言

一、list的结构

二、默认成员函数

构造函数

析构函数

clear

拷贝构造

赋值重载

swap

三、容量相关

empty

size

四、数据访问

front/back

五、普通迭代器

begin/end

六、const迭代器

begin/end

七、插入数据

insert

push_back

push_front

八、删除数据

erase

pop_back

pop_front

九、代码

总结


前言

我们之前讲解了string和vector的模拟实现,它们都是类似于顺序表的结构,string的底层是一个指针,一个元素的数量,一个空间总容量,而vector的底层是三个指针,这是它们结构上不一样的地方,但是实现的方法和原理还是大差不差的,那本篇我们来谈谈list,list的迭代器和之前的容器是不一样的,而且是一个双向带头循环链表,任意位置的插入删除效率都是O(1),那我们开始正题


一、list的结构

list的结构是一个一个的节点,所以我们在定义的时候就要去定义一个节点

template<class T>
struct list_node
{list_node<T>* _prev;list_node<T>* _next;T _val;
};

_prev指向前一个节点

_next指向下一个节点

_val表示节点中存储的值

list_node这个类可以写成class,然后放成公有,也可以直接定义成struct的,因为这个类中的成员在list这个类中会用到,所以像这种节点类就直接放成公有就好


template<class T>
class list
{typedef list_node<T> Node;
private:Node* _head;size_t _size;
};

对于list这个类,我们需要先把list_node这个类给typedef,否则一直用他太长了,而且要带上模版参数,要注意的是,typedef也会受到访问限定符的限制,所以在外面是看不到Node的,然后我们用这个Node来定义一个头结点,也就是指向头节点的指针_head,然后还有一个成员函数是_size,_size是用来返回链表内的数据个数的,如果没有_size的话就只能遍历求一遍,这样增加一个成员变量代价反而小了


二、默认成员函数

构造函数

构造函数要来初始化成员变量,所以就需要先去给_head去new一个节点,然后它的前驱和后继都指向自己,_size初始化成0就好了,因为头节点不存储有效数据,所以也就不算做元素个数了

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

对于Node这个类在new的时候会去调用它的构造函数,所以我们要给Node类补上一个构造,用匿名对象做这里的缺省参数

template<class T>
struct list_node
{list_node<T>* _prev;list_node<T>* _next;T _val;list_node(const T& val = T()):_prev(nullptr), _next(nullptr), _val(val){}
};

析构函数

析构函数需要把所有的节点都释放了,因为所有节点都是new出来的,那就先来实现一个clear函数

clear

clear是要清空除头节点外链表中所有的节点,就要从头节点的下一个节点开始,去删除每一个节点,但是删除了当前节点就会找不到下一个节点,所以要先保存一下下一个节点

void clear()
{Node* cur = _head->_next;while (cur != _head){Node* next = cur->_next;delete cur;cur = next;}
}

cur表示的是当前节点,next记录下一个节点的位置,循环判断的条件就是不等于头结点就继续删,删到最后一个节点,那它的next就是头结点了,也就证明删完了,循环结束


那在析构函数中就先去调用clear先把后面链接的节点全部删掉,然后再把头节点删掉并置空就好了

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

拷贝构造

这里就不能再去用memcpy或者赋值来写了,因为list在物理上并不是连续的空间,不可以用下标来访问,所以采用的方法是遍历有数据的这个容器,然后依次尾插进被拷贝的容器中

//l2(l1)
list(const list<T>& l)
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;for (auto e : l){push_back(e);}
}

然后这里的l2在插入数据前一定要去初始化,要把头节点new出来再把前后都指向自己,否则在访问时会出问题,这里用的是范围for,那就需要支持迭代器才可以,并且push_back也还没有实现,所以暂时这个拷贝构造是不能跑的,大家可以等下面的实现完再回来看


赋值重载

赋值就写一个现代写法去调用拷贝构造就可以,这个我们很详细的说过了,在这里就不再多赘述了

swap

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

//l2 = l1
list<T>& operator=(list<T> l)
{swap(l);return *this;
}

三、容量相关

empty

判空的逻辑是判断头节点的前驱和后继是不是指向自己,且元素个数是否为0

bool empty() const
{return _head->_next == _head&& _head->_prev == _head&& _size == 0;
}

size

size函数只需要返回_size的值就可以

size_t size() const
{return _size;
}

四、数据访问

front/back

front就是返回第一个节点里存储的值,back返回最后一个节点里的值,一定要注意是第一个存储有效数据的节点,所以是头结点的下一个节点,而不是头节点中存储的值

front和back各自分别有两个版本,一个普通版本,一个const版本,跟我们之前讲的一样,普通对象优先调用普通版本,如果没有普通版本再去调用const版本,const对象只能调用const版本

T& front()
{return _head->_next->_val;
}const T& front() const
{return _head->_next->_val;
}T& back()
{return _head->_prev->_val;
}const T& back() const
{return _head->_prev->_val;
}

五、普通迭代器

我们在最开始的时候说过,list的迭代器与前面的有些不一样,我们就来看看list的迭代器有哪些不一样,可以说list最重要的部分就是迭代器,大家先来看可不可以这么写我们的迭代器呢?

typedef Node* iterator

答案显而易见,肯定是不可以的,因为迭代器我们解引用是要拿到数据,但是现在解引用拿到的是一个节点,而且++要向下一个位置走,--要向前一个位置走,现在这个迭代器++走到哪去谁能知道呢?所以我们要用运算符重载来控制这里的逻辑,也就要再封装一个迭代器的类来控制

template<class T>
struct __list_iterator
{typedef list_node<T> Node;Node* _node;
};

在外面需要去访问这个类中的成员函数,所以我们把这个迭代器类定义成struct的,里面有一个节点的指针_node,我们先来实现下*和->,*就是返回数据的引用,->是返回数据的地址

T& operator*()
{return _node->_val;
}T* operator->()
{return &(_node->_val);
}

然后是++和--,++就是向下一个节点走,--就是向前一个节点走,而++和--呢又分为前置和后置,我们先实现前置,前置的话就是_node走完返回迭代器的本身,那这个迭代器类的名字太长了,我们也同样来typedef一下

typedef __list_iterator<T> Self;

这个typedef就和Node的typedef放在一起就行 

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

前置++返回的是迭代器走完的结果,所以就可以用引用返回


后置是返回++或者--之前的值,那就需要先保存一份才可以,然后返回保存的这一份,区分前置和后置,就是给后置加上一个int类型的参数

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

迭代器判断循环结束的条件还有一个不等于,我们来实现一下,就是比较两个指针一不一样就可以了

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

begin/end

begin就是返回头节点的下一个位置,因为迭代器是左闭右开,所以end应该返回的是最后一个有效数据的下一个位置,也就是头节点_head

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

那在list这个类中需要用到iterator,我们就把这个类给嵌到list这个类里,这个要放成公有的,外面要用迭代器

public:typedef __list_iterator<T> iterator;

而且还要给迭代器类实现一个构造函数,用节点指针去构造迭代器,现在的begin和end是隐式类型转换,构造加拷贝构造,拷贝构造我们不需要实现,迭代器去浅拷贝就可以了,也可以返回匿名对象或者是先构造出来对象再返回这个对象,这三种都可以,我们这种是最简单的,直接隐式类型的转换

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

我们再结合迭代器的使用来看

int main()
{hx::list<int> l;hx::list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl;return 0;
}

需要什么我们就写什么就可以了,迭代器也就是需要这几个函数,不需要实现其他功能了,那我们的普通迭代器就实现好了


六、const迭代器

下面我们来看一下const迭代器,有了刚才的封装,那const迭代器可不可以直接套上一个const呢?

typedef __list_iterator<T> iterator;
typedef const __list_iterator<T> const_iterator;

这样写也是不行的,因为这样写就是修饰迭代器本身不能修改了,那迭代器本身都不能修改了还怎么++/--呢?所以const迭代器也是需要我们自己去封装一个自定义类型来控制,那我们就照葫芦画瓢来实现一个

template<class T>
struct __list_const_iterator
{typedef __list_const_iterator<T> Self;typedef list_node<T> Node;Node* _node;__list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->_val;}const T* operator->(){return &(_node->_val);}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(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};

那大家有没有发现,普通迭代器和const迭代器不一样的地方就在于*和->的返回值,其他的地方全都一样,那这样设计就太冗余了,我们有没有办法可以就用一个类来控制一下*和->的返回值呢?其实很好办,只需要增加模版参数就可以

template<class T, class Ref, class Ptr>
struct __list_iterator
{typedef __list_iterator<T, Ref, Ptr> Self;typedef list_node<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &(_node->_val);}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(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};

Ref是引用,也就是operator*的返回值,Ptr是指针,也就是operator->的返回值,然后不要忘记在typedef Self的时候把这两个模版参数给加上,然后在list类中我们把后面的两个模版参数写死就可以了

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

begin/end

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

begin和end还是一样的实现逻辑,返回值变一样,再设计成const成员函数就可以

那迭代器部分我们就说到这里,因为这里可能会比较复杂,三个类互相缠绕,所以在文章的最后会把所有的代码给贴出来,如果大家对这里还有不太懂的地方可以去参考


七、插入数据

insert

insert是在某个迭代器插入一个val,那就是把这个迭代器里存的节点指针定义出来,然后找到前一个,再新创建一个节点,把他们之间互相链接起来就行了,最后返回新插入的这个节点的迭代器

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

push_back

push_back是尾插,直接去复用insert,给一个迭代器位置

void push_back(const T& val)
{insert(end(), val);
}

 end就是头结点,那在头节点的前面插入也就是尾插


push_front

push_back是头插,直接去复用insert,给一个迭代器位置

void push_front(const T& val)
{insert(begin(), val);
}

begin就是头结点的下一个位置,在begin之前插入,也就是在头结点和第一个节点之间插入,就是头插


八、删除数据

erase

erase是要删除某个迭代器位置,那也是把迭代器里存的节点指针定义出来,然后找到前后节点,把前后节点互相连起来就好了,最后再删除,然后要返回删除的这个位置的下一个节点的迭代器

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

pop_back

pop_back是尾删,直接去复用erase,给一个迭代器位置

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

end是头节点的位置,那--end就是头结点的前一个,也就是最后一个节点


pop_front

pop_front是头删,直接去复用erase,给一个迭代器位置

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

begin是头结点的下一个位置,也就是第一个存放有效数据的节点


九、代码

namespace hx
{template<class T>struct list_node{list_node<T>* _prev;list_node<T>* _next;T _val;list_node(const T& val = T()):_prev(nullptr), _next(nullptr), _val(val){}};template<class T, class Ref, class Ptr>struct __list_iterator{typedef __list_iterator<T, Ref, Ptr> Self;typedef list_node<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &(_node->_val);}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(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}};template<class T>class list{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}list(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}//l2(l1)list(const list<T>& l){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;for (auto e : l){push_back(e);}}//l2 = l1list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete _head;_head = nullptr;}void swap(list<T>& l){std::swap(_head, l._head);std::swap(_size, l._size);}bool empty() const{return _head->_next == _head&& _head->_prev == _head&& _size == 0;}size_t size() const{return _size;}void clear(){Node* cur = _head->_next;while (cur != _head){Node* next = cur->_next;delete cur;cur = next;}}T& front(){return _head->_next->_val;}const T& front() const{return _head->_next->_val;}T& back(){return _head->_prev->_val;}const T& back() const{return _head->_prev->_val;}iterator insert(iterator pos, const T& val){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(val);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return newnode;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;return next;}void push_back(const T& val){insert(end(), val);}void pop_back(){erase(--end());}void push_front(const T& val){insert(begin(), val);}void pop_front(){erase(begin());}private:Node* _head;size_t _size;};
}

总结

本篇文章我们讲了list,以及关于迭代器部分,list的迭代器类型是一个自定义类型,跟以前不太一样,但是这种方式在以前也还是很常见的,比如map/set,unordered map/unordered set,还是要这么用,迭代器部分都要去这样封装,大家还是要习惯这种方式,那本篇文章就到这里啦,如果觉得下篇写的不错的小伙伴,可以给小编一个一键三连表示支持,感谢大家!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/22600.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

虚拟机从零实现机器人控制

1. 系统安装 因Docker不适合需要图形界面的开发&#xff0c;因此使用虚拟机VMware方便可视化界面方式查看效果&#xff0c;相关软件可以从官网下载&#xff0c;这里有一整套免费安装文件百度网盘地址&#xff1a; 2. ROS安装 Ubuntu 22.04&#xff1a;https://docs.ros.org…

【Blender】二、建模篇--06,曲线建模/父子级和蒙皮修改器

00:00:03,620 --> 00:00:09,500 前几节可能我们已经做了很多种类型的模型了 但是有一种类型 我们一直避开就是这种管道 1 00:00:10,050 --> 00:00:19,370 藤条头发啊 衣服架子啊这种弯弯绕绕的 需要一定柔软度的模型 那么这节课呢我们都来集中看一下曲线的模型 我们应该…

机器学习实战(7):聚类算法——发现数据中的隐藏模式

第7集&#xff1a;聚类算法——发现数据中的隐藏模式 在机器学习中&#xff0c;聚类&#xff08;Clustering&#xff09; 是一种无监督学习方法&#xff0c;用于发现数据中的隐藏模式或分组。与分类任务不同&#xff0c;聚类不需要标签&#xff0c;而是根据数据的相似性将其划…

静态时序分析:时钟组间的逻辑独立、物理独立和异步的区别

相关阅读 静态时序分析https://blog.csdn.net/weixin_45791458/category_12567571.html 当设计中存在多个时钟&#xff08;同步或异步&#xff09;时&#xff0c;该如何使用SDC命令约束设计呢&#xff1f;本文就将对此进行讨论。 逻辑独立 例1 多个时钟完全逻辑独立 图1 逻辑…

【从0做项目】Java文档搜索引擎(9)烧脑终章!

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 文章导读 零&#xff1a;项目结果展示 一&#xff1a;导入 二&#xff1a;问题引入 1&#xff1a;情…

gsplat 抗锯齿

关键代码 无论时候开启抗锯齿&#xff0c;都会进行二维膨胀&#xff1a; template <typename T> inline __device__ T add_blur(const T eps2d, mat2<T> &covar, T &compensation) {T det_orig covar[0][0] * covar[1][1] - covar[0][1] * covar[1][0];…

根据音频中的不同讲述人声音进行分离音频 | 基于ai的说话人声音分离项目

0.研究背景 在实际的开发中可能会遇到这样的问题&#xff0c;老板让你把音频中的每个讲话人的声音分离成不同的音频片段。你可以使用au等专业的音频处理软件手动分离。但是这样效率太慢了&#xff0c;现在ai这么发达&#xff0c;我们能否借助ai之力来分离一条音频中的不同的说…

一台服务器将docker image打包去另一天服务器安装这个镜像

一台服务器将docker image打到去另一天服务器安装这个镜像 1. 打包2.另一台服务器执行 1. 打包 docker save -o nebula-graph-studio.tar harbor1.vm.example.lan/dockerio/vesoft/nebula-graph-studioxxx.tar 是打包好的文件 后面的是 docker image 2.另一台服务器执行 docke…

STM32-心知天气项目

一、项目需求 使用 ESP8266 通过 HTTP 获取天气数据&#xff08;心知天气&#xff09;&#xff0c;并显示在 OLED 屏幕上。 按键 1 &#xff1a;循环切换今天 / 明天 / 后天天气数据&#xff1b; 按键 2 &#xff1a;更新天气。 二、项目框图 三、cjson作用 https://gi…

自由学习记录(37)

课 对于这一方面&#xff0c;先把课都过一遍吧&#xff0c;尽量快的摸清楚底 软件工程 没有复杂的逻辑推理&#xff0c;概念性和理论很强&#xff0c;所以靠记 ------ 数据&#xff1a;是使程序能够适当处理信息的数据结构 程序&#xff1a;是能够完成预定功能和性能的可执行…

Docker仿真宇树狗GO1

1. 启动容器 docker run -it --rm humble_suo bash2. 安装Go1 的仿真包 apt update apt install -y git cmake build-essential git clone https://github.com/unitreerobotics/unitree_ros.git cd unitree_ros colcon build source install/setup.bash3. 启动仿真环境 ros2…

《游戏人工智能编程 案例精粹》阅读心得

最近读完了这本《游戏人工智能编程 案例精粹》&#xff0c;感觉获益匪浅&#xff0c;在对游戏人工智能的设计上有了更深的感悟。 这本书既适合初学者学习&#xff0c;因为次书会从最基础的数学物理公式推导一步一步介绍到完整的人工智能开发&#xff1b;同时也适合进阶程序员&a…

黑马点评_商品信息缓存模块

保证缓存不要有空档期 删除后马上要写入中间不能插入任何阶段(如查询数据库) 对于单体系统1&#xff0c;将缓存与数据库操作放在同一个事务中&#xff08;当前项目就是一个单体项目&#xff0c;所以选择这种方式&#xff09; 对于分布式系统2&#xff0c;利用TCC&#xff08;Tr…

OnlyOffice:前端编辑器与后端API实现高效办公

OnlyOffice&#xff1a;前端编辑器与后端API实现高效办公 一、OnlyOffice概述二、前端编辑器&#xff1a;高效、灵活且易用1. 完善的编辑功能2. 实时协作支持3. 自动保存与版本管理4. 高度自定义的界面 三、后端API&#xff1a;管理文档、用户与权限1. 轻松集成与定制2. 实时协…

面阵工业相机提高餐饮业生产效率

餐饮行业是一个快节奏、高要求的领域&#xff0c;该领域对生产过程中每一个阶段的效率和准确性都有很高的要求。在食品加工、包装、质量控制和库存管理等不同生产阶段实现生产效率的优化是取得成功的关键步骤。面阵工业相机能够一次性捕捉对象的二维区域图像&#xff0c;并支持…

现场可以通过手机或者pad实时拍照上传到大屏幕的照片墙现场大屏电子照片墙功能

现场可以通过手机或者pad实时拍照上传到大屏幕的照片墙现场大屏电子照片墙功能&#xff0c;每个人都可以通过手机实时拍照上传到大屏幕上,同时还可以发布留言内容&#xff0c;屏幕上会同步滚动播放展示所有人的照片和留言。相比校传统的照片直播功能更加灵活方便&#xff0c;而…

【多线程】线程安全

目录 一、初识线程安全 什么是线程安全问题 理解线程不安全的原因 原因总结 二、解决线程不安全 加锁&#x1f510; 锁对象 synchronized几种使用方式 死锁&#x1f50f; 死锁的三个场景 (1)一个线程针对一把锁连续加锁两次 (2)两个线程两把锁 (3)N个线程M个锁 如…

传统文旅+AI构建数字文旅新生态

传统文旅AI构建数字文旅新生态 前言&#xff1a; 当前许多旅游景区在旅游管理和旅游基础设施配套上都下足了功夫&#xff0c;在一定程度上也给旅客和消费者带来了舒适的体验感。但是针对于我们游客而言&#xff0c;似乎只有欣赏沿途风景、了解景区历史文化、拍照打卡和品尝特色…

VSCode - VSCode 切换自动换行

VSCode 自动换行 1、基本介绍 在 VSCode 中&#xff0c;启用自动换行可以让长行代码自动折行显示&#xff0c;避免水平滚动条频繁使用&#xff0c;提升代码阅读体验 如果禁用自动换行&#xff0c;长行代码就需要手动结合水平滚动条来阅读 2、演示 启用自动换行 禁用自动换…

解锁音频新境界:LALAL.AI 与 Audo Studio 深度解析

在音频处理的世界里&#xff0c;噪音常常是困扰我们的一大难题。无论是专业的音频工作者&#xff0c;还是普通的音频爱好者&#xff0c;都渴望拥有一款强大的工具来解决这个问题。今天&#xff0c;就为大家介绍两款来自 AI 工具导航&#xff08;AIDH.NET&#xff09;的 AI 语音…