[C++初阶]list的模拟实现

news/2024/9/13 22:39:18/ 标签: c++, 开发语言, list, stl

一、对于list的源码的部分分析

1.分析构造函数

首先,我们一开始最先看到的就是这个结点的结构体,在这里我们可以注意到这是一个双向链表。有一个前驱指针,一个后继指针。然后在有一个存储数据的空间

其次它的迭代器是一个自定义类型,而非原生指针。这里我们先不管,我们接着往下看。

我们继续找成员变量,在这里我们就找到了成员变量,但是这个类型我们看不懂,于是我们先略过。

通过对定义的查找,可以看到这个实际上还是一个指针。但是这个指针我们还是看不懂。

于是我们继续去速览定义,于是就找到了这里

这里我们可以注意到这个结点的类型其实就是一个类模板,这个模板正好就是我们一开始就看到的用结构体定义的一个结点。因此我们可以知道,这个成员变量实际就是一个指针,这个指针指向一个结点。这样一想象,就有点像我们在c语言使用链表时候的头节点了。

那么接下来,我们应该分析一下构造函数是什么样子的。
不难发现,就在成员变量的下方,正好就是一个无参的构造函数。也就是默认构造函数

但是在这里它又封装了一层函数,于是乎我们继续深入查看

如下所示,我们看到了具体的函数内容,从名字上来看,get_node 我们挺名字就知道开空间的。也就是得到一个结点,然后返回这个结点指针。这样一来,我们的成员变量就获取的实际的一个结点,然后让它的next和prev都指向自己,这样一来这个结点形成一个自循环。现在就能看出来这是一个带头双向循环链

我们也可以继续深入

如上图所示,这里的allocated设计到空间配置器。这里我们就先不做了解了。之后在学习中我们详细介绍。

我们往下看会看到put_node,这个函数其实就是释放结点的。在后面还有这样一个函数,这个函数是create_node不难理解,这个就是获取一个结点,先给这个结点开空间,然后调用构造函数。等一系列操作。既然这里涉及到一个构造,那么我们可以继续深入,看看这个构造里面是什么东西?但是这里涉及到了C++11的内容了,这边我们就先不管它了,我们只需要知道这里的空间能new出来就行。

2.对于头尾插的分析

作为链表,我们知道除了构造最重要的,肯定是头尾插,这里我们先找到头尾插的对应的函数

我们发现头尾插都调用了insert这个函数,因此我们需要先找到这个函数,

这里我们也是能大概理解的,先创造一个结点,然后进行连接。现在我们也基本读懂了这个大体的框架了,但是这里还需要注意的是:由于一开始的结点里面的指针都是空指针,导致后面需要经历很多的强制类型转化。所以这里我们如果一开始就定义好指针的类型是最好的。


二、list的模拟实现

1.list的节点声明

为了不和标准库中的list类冲突,我们可以开一个自己的命名空间,

其次,C++中对结点进行定义的时候可以只写类名,这与class是一样的。注意不要忘记带上模板参数T,因为我们写的结点也只是一个模板。因为类名不是类型,他实例化以后可以有各种各样的结点类型

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

2.list类的成员变量

由于我们的结点是一个模板,对于它而言,它的类型就比较繁琐,我们可以在list类里面使用typedef进行一次重命名。然后再私有里面再定义一个指针,这个指针就是一个结点指针。

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

3.list类的默认构造函数

如下所示,我们定义好了成员变量以后,我们就写一个默认构造函数,当我们对这个链表类进行实例化的时候,自动调用这个默认构造函数,这个默认构造函数会为成员变量的头节点指针分配实际的空间,在new Node空间的时候,会调用它Node(即list_node<T>)类的默认构造函数函数。从而成功的开辟好这块空间。
 

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

4.list类的尾插

如下所示,我们的尾插逻辑也是比较简单的,先利用我们传过来的val去开辟一个新的结点,注意这里开辟新结点的时候使用new的话可以直接带一个括号去调用它的构造函数

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

5.结点的默认构造函数

有了上面的分析之后,我们现在缺的是一个结点的默认构造函数,我们直接给一个缺省值,使用T()就是一个匿名对象来初始化,对于内置类型也是同样适用的。然后我们使用初始化列表即可。

		list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}

6.list类的迭代器

首先我们思考一下,可否像vector一样直接在类里面typedef 一个迭代器?

显然是不行的,因为链表不支持下标随机访问,list是不连续的,指针加1后,地址早已不知道跑到哪个结点去了。其次这里仅仅只是结点的指针,解引用后,找到的仅仅只是结点,我们还需要进一步解引用才能找到对应的真正的值。

直接typedef的话,会使得迭代器的++和解引用操作均失效了,这时候我们只能使用运算符重载了。才能解决这个问题。既然要运算符重载,这里我们最好再次封装一个类出来。因为如果不封装一个类出来的话,我们无法完成此处的运算符重载。

如下所示,是我们实现的iterator的类

	template<class T>struct __list_iterator{typedef list_node<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}T& operator*(){return _node->_val;}__list_iterator<T>& operator++(){_node = _node->_next;return *this;}bool operator!=(const __list_iterator<T>& it){return _node != it._node;}};

这个类我们使用了一个结构体去封装,在这个结构体中,我们只有一个成员变量,这个成员变量是结点类的指针,用于指向某一个结点, 在我们一开始定义出迭代器的时候,我们需要先写一个构造函数,用于迭代器的初始化。即需要传一个参数node来控制。

与之对应的,我们在list中就需要写出对应的begin和end函数,来返回迭代器。

		typedef __list_iterator<T> iterator;iterator begin(){//return _head->_next //单参数的构造函数支持隐式类型转换return iterator(_head->_next);}iterator end(){return iterator(_head);}

下面我们这里将迭代器的基本操作写的稍微完善一些

	template<class T>struct __list_iterator{typedef list_node<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}T& operator*(){return _node->_val;}__list_iterator<T>& operator++(){_node = _node->_next;return *this;}__list_iterator<T> operator++(int){__list_iterator<T> tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const __list_iterator<T>& it){return _node != it._node;}bool operator==(const __list_iterator<T>& it){return _node == it._node;}};

7.const迭代器

我们可以拷贝一份原来的迭代器,然后改变一下类名和解引用这个成员函数的返回值即可

	template<class T>struct __list_const_iterator{typedef list_node<T> Node;Node* _node;__list_const_iterator(Node* node):_node(node){}const T& operator*() {return _node->_val;}__list_const_iterator<T>& operator++() {_node = _node->_next;return *this;}__list_const_iterator<T> operator++(int) {__list_const_iterator<T> tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const __list_const_iterator<T>& it) {return _node != it._node;}bool operator==(const __list_const_iterator<T>& it) {return _node == it._node;}};

即如上代码所示,但是这样设计太过于冗余了。不过这个也是可以正常运行的,我们先补两个接口

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

其实我们可以通过一个类型去控制这个返回值,而要控制这个类型,就需要增加一个模板参数即可

在迭代器类中添加一个Ref参数,然后让*的运算符重载返回这个模板参数,最后代码如下:

	template<class T, class Ref>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref> self;Node* _node;__list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const self & it){return _node != it._node;}bool operator==(const self & it){return _node == it._node;}};

当然现在还没完,还有时候,我们可能会写出这样的代码

	struct A{A(int a = 0, int b = 0):_a(a),_b(b){}int _a;int _b;};void test2(){list<A> lt;lt.push_back(A(1, 1));lt.push_back(A(2, 2));lt.push_back(A(3, 3));lt.push_back(A(4, 4));lt.push_back(A(5, 5));list<A>::iterator it = lt.begin();while (it != lt.end()){cout << it->_a << " ";it++;}cout << endl;}

我们显然发现是无法正常运行的。由于迭代器是类似于指针的操作,我们有时候就需要->操作符去解引用。所以,我们需要加上一个->的运算符重载。

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

如上所示,是写在迭代器里面的operator运算符重载,

然而当我们细心的话,我们会发现这个运算符重载是比较怪异的。哪里怪异呢?

首先我们这个运算符重载返回的是什么呢?是A*,也就是说它还需要一次->解引用才能找到真正的值。那么我们这里为什么可行呢?

严格来说,it->->_a,才是符合语法的。
因为运算符重载要求可读性,那么编译器特殊处理,省略了一个->

上面这个运算符重载仅仅只是针对于普通对象的,如果是const对象的话,那么我们只能使用跟*运算符重载一样的处理方法,多传一个参数,才可以解决这个问题。也就是我们需要三个模板参数才可以。
最终我们的迭代器代码如下所示

	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):_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 & it) const{return _node != it._node;}bool operator==(const self & it) const{return _node == it._node;}};

8.插入和删除接口

整体简单,这里直接展示源码:

		void push_back(const T& val){//insert(end(), val);Node* newnode = new Node(val);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}void push_front(const T& val){insert(begin(), val);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator insert(iterator pos, const T& val){Node* newnode = new Node(val);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;cur = nullptr;prev->_next = next;next->_prev = prev;return next;}

9.size

这个不难,我可以通过遍历解决得出size,但是这样子的时间复杂度可能有点高,

		size_t size(){size_t sz = 0;iterator it = begin();while (it != end()){it++;sz++;}return sz;}

这里我们也可以用第二种方法,多加一个成员变量存储节点数量,每次插入节点时++,删除节点时--,这里我就不多做解释了

10.clear

这个就是遍历释放空间就行

		void clear(){iterator it = begin();while (it != end()){it = erase(it);}}

11.析构函数

析构函数也是很简单的,析构和clear的区别就是析构会删除头节点,而clear不会删除头节点。

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

12.拷贝构造函数

这里设计空间的开辟,所以需要深拷贝,代码如下:

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

当然在这里我们发现拷贝构造和默认构造有点重复了。我们可以对前面重复的部分在封装一个函数,从而简化代码:

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

13.赋值运算符重载

如下所示,这个也是比较简单,我们直接使用现代写法吧:

		void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt){swap(lt);return *this;}

同时我们需要注意库里面的函数返回值和形参写的是类名,而不是类型,

这是因为在类模板里面写成员函数的时候,是允许用类名代替类型的。即我们的代码下面这些部分可以直接换为类名,但是呢,这里不建议使用,因为这种行为会降低可读性。

三、模拟list类的全部代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>
#include<assert.h>using namespace std;namespace Sim
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}};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):_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 & it) const{return _node != it._node;}bool operator==(const self & it) const{return _node == it._node;}};template<class T>class list{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;//typedef __list_const_iterator<T> const_iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin(){//return _head->_next //单参数的构造函数支持隐式类型转换return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{//return _head->_next //单参数的构造函数支持隐式类型转换return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){//_head = new Node;//_head->_next = _head;//_head->_prev = _head;//_size = 0;empty_init();}list(const list<T>& lt){//_head = new Node;//_head->_next = _head;//_head->_prev = _head;//_size = 0;empty_init();for (auto& e : lt){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt){swap(lt);return *this;}void push_back(const T& val){insert(end(), val);//Node* newnode = new Node(val);//Node* tail = _head->_prev;//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _head;//_head->_prev = newnode;}void push_front(const T& val){insert(begin(), val);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator insert(iterator pos, const T& val){Node* newnode = new Node(val);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;cur = nullptr;prev->_next = next;next->_prev = prev;--_size;return next;}size_t size(){//size_t sz = 0;//iterator it = begin();//while (it != end())//{//	it++;//	sz++;//}//return sz;return _size;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}private:Node* _head;size_t _size;};}
}


http://www.ppmy.cn/news/1475542.html

相关文章

OceanBase 配置项系统变量实现及应用详解(3):新增配置项的方法

本专题的第一篇文章&#xff0c;配置项的定义及使用方法&#xff0c;详细阐述了配置项的基础用法。对于那些对源码抱有浓厚兴趣的同学来说&#xff0c;或许还希望深入了解配置项的实现原理&#xff0c;甚至渴望亲自添加新的配置项&#xff0c;以满足个性化的功能需求。 本文通…

七、MyBatis-Plus高级用法:最优化持久层开发-个人版

七、MyBatis-Plus高级用法&#xff1a;最优化持久层开发 目录 文章目录 七、MyBatis-Plus高级用法&#xff1a;最优化持久层开发目录 一、MyBatis-Plus快速入门1.1 简介1.2 快速入门回顾复习 二、MyBatis-Plus核心功能2.1 基于Mapper接口CRUDInsert方法Delete方法Update方法Se…

云计算安全需求分析与安全保护工程

云计算基本概念 云计算&#xff08;Cloud Computing&#xff09;是一种通过互联网提供计算资源和服务的技术。它允许用户按需访问和使用计算资源&#xff0c;如服务器、存储、数据库、网络、安全、分析和软件应用等&#xff0c;而无需管理底层基础设施。以下是云计算的基本概念…

【数据救援实战】移动硬盘无法读取打不开?两步策略拯救你的数据

移动硬盘困境&#xff1a;读取障碍的深层剖析 在数据存储日益重要的今天&#xff0c;移动硬盘作为便携与容量的完美结合体&#xff0c;成为众多用户保存重要文件的首选。然而&#xff0c;当遇到移动硬盘无法读取或无法打开的情况时&#xff0c;那份焦急与无助感往往让人难以承…

Python-PLAXIS自动化建模技术与典型岩土工程

有限单元法在岩土工程问题中应用非常广泛&#xff0c;很多软件都采用有限单元解法。在使用各大软件进行数值模拟建模的过程中&#xff0c;您是否发现GUI界面中重复性的点击输入工作太繁琐&#xff1f;从而拖慢了设计或方案必选进程&#xff1f; 搭建自己的Plaxis模型&#xff…

IDEA中Git常用操作及Git存储原理

Git简介与使用 Intro Git is a free and open source distributed version control system designed to handle everything from small to very large projects with speed and efficiency. Git是一款分布式版本控制系统&#xff08;VSC&#xff09;&#xff0c;是团队合作开发…

bash: redi-cli: 未找到命令...

问题描述 在执行命令&#xff1a;redi-cli --bigkeys 提示&#xff1a;bash: redi-cli: 未找到命令... 确定服务器是否有Redis进程 ps -ef | grep redis查找Redis 文件信息 find / -name "redis-*"进入到当前目录 cd /usr/bin/再次执行命令 涉及redis-cli 连…

数据库系统中的Undo和Redo

在数据库管理系统&#xff08;DBMS&#xff09;中&#xff0c;undo 和 redo 是两种用于事务管理和故障恢复的重要机制。它们主要涉及事务的提交、回滚以及系统故障后的数据恢复。 Undo&#xff08;撤销&#xff09; 作用&#xff1a;undo 用于撤销未提交事务所做的修改&#…

Lab1 论文 MapReduce

目录 &#x1f339;资源链接 &#x1f354;调试技巧 &#x1f985;2 Programming Model &#x1f33c;2.1 Example &#x1f33c;2.2 Types &#x1f33c;2.3 More Examples &#x1f985;3 Implementation(实现) &#x1f33c;3.1 ~ 3.3 &#x1f33c;3.4 ~ 3.6…

36. Adam 算法详解

Adam&#xff08;Adaptive Moment Estimation&#xff09;是一种结合动量法和自适应学习率的优化算法&#xff0c;自2014年提出以来&#xff0c;迅速成为深度学习中最流行和常用的优化算法之一。Adam算法的核心思想是利用梯度的一阶动量和二阶动量来动态调整学习率&#xff0c;…

Java的高级特性

类的继承 继承是从已有的类中派生出新的类&#xff0c;新的类能拥有已有类的属性和行为&#xff0c;并且可以拓展新的属性和行为 public class 子类 extends 父类{子类类体 } 优点 代码的复用 提高编码效率 易于维护 使类与类产生关联&#xff0c;是多态的前提 缺点 类缺乏独…

RequestContextHolder多线程获取不到request对象

RequestContextHolder多线程获取不到request对象&#xff0c;调用feign接口时&#xff0c;在Feign中的RequestInterceptor也获取不到HttpServletRequest问题解决方案。 1.RequestContextHolder多线程获取不到request对象 异常信息&#xff0c;报错如下&#xff1a; 2024-07-0…

k8s集群新增节点

目前集群状态 如K8S 集群搭建中规划的集群一样 Masternode01node02IP192.168.100.100192.168.100.101192.168.100.102OSCent OS 7.9Cent OS 7.9Cent OS 7.9 目前打算新增节点node03 Masternode01node02node03IP192.168.100.100192.168.100.101192.168.100.102192.168.100.1…

FPGA设计之跨时钟域(CDC)设计篇(1)----亚稳态到底是什么?

1、什么是亚稳态? 在数字电路中,如果数据传输时不满足触发器FF的建立时间要求Tsu和保持时间要求Th,就可能产生亚稳态(Metastability),此时触发器的输出端(Q端)在有效时钟沿之后比较长的一段时间都会处于不确定的状态(在0和1之间振荡),而不是等于数据输入端(D端)的…

升级springboot3.2集成shiro的问题

由于之前的springcloud相关版本太久&#xff0c;很多新功能无法使用&#xff0c;所以打算抽时间把代码的版本做一下升级。使用最新版的springboot3.2&#xff0c;发现shiro过滤器无效。经检查发现原因&#xff1a; springboot3.x使用的是JDK17&#xff0c;从jdk8以后javax.serv…

【数据结构】单链表 双向链表

目录 链表链表的分类单链表单链表接口的实现内部类头插法尾插法任意位置插入查找是否包含关键字key是否在单链表当中删除第一次出现关键字为key的节点删除所有值为key的节点得到单链表的长度清空链表单链表的优缺点 双向链表双向链表接口的实现内部类头插法尾插法任意位置插入查…

微信小程序 - 本地存储 增加有效期

小程序的本地存储API提供了wx.setStorageSync和wx.setStorage来存储数据&#xff0c;注意的是&#xff0c;小程序的本地存储并没有明确的有效期设置&#xff0c;存储的数据在不超过限制的情况下&#xff0c;会一直保留。 一、小程序本地存储API 小程序的本地存储API提供了设置…

32路串口服务器 应用领域

32路串口服务器在多个领域有着广泛的应用&#xff0c;以下是详细的应用实例&#xff1a; 一、工业自动化 在工业自动化领域&#xff0c;32路串口服务器发挥着举足轻重的作用。传统的工业设备往往采用串口通信方式&#xff0c;而串口服务器能够将这些设备接入网络&#xff0c;…

800 元打造家庭版 SOC 安全运营中心

今天,我们开始一系列新的文章,将从独特而全面的角度探索网络安全世界,结合安全双方:红队和蓝队。 这种方法通常称为“紫队”,集成了进攻和防御技术,以提供对威胁和安全解决方案的全面了解。 在本系列的第一篇文章中,我们将指导您完成以 100 欧元约800元左右的预算创建…

金南瓜科技的SECS/GEM解决方案

1. 高稳定性和可靠性&#xff1a;金南瓜SECS/GEM解决方案已在多家知名半导体工厂中稳定运行&#xff0c;实现了7*24小时无重启无故障超过3年时间 。 2. 符合国际标准&#xff1a;金南瓜的解决方案符合SEMI E4、E5、E30、E37通信协议&#xff0c;确保与国际标准的兼容性&#x…