C++从入门到起飞之——list模拟实现 全方位剖析！

2024-08-31 04:20
文章标签 c++ 实现 入门 剖析 模拟 list 全方位 起飞

本文主要是介绍C++从入门到起飞之——list模拟实现 全方位剖析！，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

​ ​

 ​

🌈个人主页：秋风起，再归来~
🔥系列专栏：C++从入门到起飞          
🔖克心守己，律己则安

目录

​ ​1、list的整体框架

2、list迭代器

>整体分析

>整体框架

 >成员函数

>运算符->重载 

>const迭代器

>迭代器类的一些问题的思考

3、成员函数

4、完结散花

1、list的整体框架


list就是我们所熟悉的数据结构链表，通过查看源码以及我们对链表的了解我们知道在类模版list中的成员变量一个是指向有效链表的哨兵卫头结点_head，另一个是记录有效元素个数的_size，而链表中的有效元素的存储地址空间不是连续的，所以并没有容量capacity的概念！
而我们又知道链表是由一个又一个的节点组成的，而我们要实现的是带头双向循环链表，所以每个节点里面都存储着数据val、前驱指针pre、后继指针next！
所以我们可以先大概写出list的整体框架！

//链表的节点
template<class T>
struct list_node
{list_node(const T& val = T()):data(val),pre(nullptr),next(nullptr){}T data;//数据list_node<T>* pre;//前驱指针list_node<T>* next;//后继指针
};
/双向循环带头链表
template<class T>
class list
{
public:typedef list_node<T> node;//给节点取别名//成员函数//………………private:node* _head=nullptr;//带哨兵卫的头结点size_t _size = 0;//记录节点个数
};

2、list迭代器


>整体分析


为了后续方便遍历容器打印结果检测我们程序的正确性，我们先来实现list的迭代器！
我们知道我们之前模拟的string和vector的迭代器都是原生的指针，那是因为他们底层结构的优越性允许他们这样实现。但是，list如果我们还是使用原生指针的话就完全做不到迭代器的效果，因为我们对节点指针*取到的是节点本身，而不是节点里面的数据，对节点++或--，因为链表不是连续的物理空间，所以我们并不能拿到前一个或后一个的迭代器反而让迭代器成了野指针！
那怎么办呢！我们可以对list的迭代器进行封装，而迭代器的底层原理还是使用节点的指针！只不过，我们要在迭代器里面对*、++、--、==、!= 等操作进行运算符重载！


>整体框架


那我们先实现迭代器的整体框架！
因为该迭代器只是给list使用，外面根本不知道，所以我们干脆用struct定义，将所有成员公开！

//链表的迭代器
template<class T>
struct list_iterator
{typedef  list_node<T> node;//给节点取别名typedef     list_iterator<T> self;//给自己取别名node* it;//链表中的迭代器其实就是一个节点的指针//只不过其访问和迭代操作要用一个类封装起来list_iterator(node* node):it(node){}//成员函数//………………};

 >成员函数

//返回T&
T& operator*()
{return it->data;
}//（前置++）++it
self& operator++()
{it = it->next;return *this;
}//（前置--）--it
self& operator--()
{it = it->pre;return *this;
}//(后置++) it++
self operator++(int) 
{self tmp(*this);it = it->next;return tmp;//一定不能用引用接收，不然会有野指针！
}//(后置--) it--
self operator--(int) 
{self tmp(*this);it = it->pre;return tmp;
}//比较迭代器里面的it指针相不相等
bool operator==(const self& comp)
{return it==comp.it;
}
bool operator!=(const self& comp)
{return it!=comp.it;
}


>运算符->重载 

如果节点中存储的是自定义类型Pos(坐标类）

struct Pos
{int _row;int _col;Pos(int row, int col):_row(row), _col(col){}
};

​如果我们想要方便访问坐标，那我们可以重载->操作符

T* operator->()
{return &(it->data);
}
list<Pos> lt;
lt.push_back(Pos(1, 1)); 
lt.push_back(Pos(2, 2));
lt.push_back(Pos(3, 3));
lt.push_back(Pos(4, 4));auto it = lt.begin();
while (it != lt.end())
{cout << it->_col << " " << it->_row << endl;++it;
}
​

上面的->实际上的完整调用是下面的模式

auto it = lt.begin();
while (it != lt.end())
{cout << it.operator->()->_row << " " << it.operator->()->_col << endl;++it;
}

it先调用重载的->，返回Pos类型的原生指针指针后再调用原始指针的->。而为了方便与可读性，编译器允许我们省略一个->调用！ 


>const迭代器

我们在上面只实现了一个普通的迭代器，如果我们要再实现一个const的常量迭代器，我们是不是就要再自己实现一个迭代器类呢？雀氏行的通！

//链表的迭代器
template<class T>
struct list_const_iterator
{typedef  list_node<T> node;//给节点取别名typedef     list_const_iterator<T> self;//给自己取别名node* it;//链表中的迭代器其实就是一个节点的指针//只不过其访问和迭代操作要用一个类封装起来list_const_iterator(node* node):it(node){}//成员函数//………………};

不过，在内部的成员函数实现中，只有一些函数的返回值是不同的，而函数体的是一样的！想这样俩个相似度高度集中的类，我们就可以使用类模版的方法将俩个类进行合并！
而我们具体的做法则是增加模版参数！
​
合并后的完整代码：

//链表的迭代器
template<class T, class ref,class ptr>
struct list_iterator
{typedef  list_node<T> node;//给节点取别名typedef     list_iterator<T, ref, ptr> self;//给自己取别名node* it;//链表中的迭代器其实就是一个节点的指针//只不过其访问和迭代操作要用一个类封装起来list_iterator(node* node):it(node){}//返回T*ptr operator->(){return &(it->data);}//返回T&ref operator*(){return it->data;}//（前置++）++itself& operator++(){it = it->next;return *this;}/*self operator++(){it = it->next;return it;}*///（前置--）--itself& operator--(){it = it->pre;return *this;}/*self operator--(){it = it->pre;return it;}*///(后置++) it++self operator++(int) {self tmp(*this);it = it->next;return tmp;//一定不能用引用接收，不然会有野指针！}//(后置--) it--self operator--(int) {self tmp(*this);it = it->pre;return tmp;}//比较迭代器里面的it指针相不相等bool operator==(const self& comp){return it==comp.it;}bool operator!=(const self& comp){return it!=comp.it;}};

>迭代器类的一些问题的思考

(1) 类中是否需要写析构函数？
这个迭代器类不要写析构函数，因为这里的节点不是迭代器的，是链表的，不用把它释放。我们使用begin，end返回节点给迭代器，是借助迭代器修改，访问数据，所以我们不需要释放。
(2) 类中是否需要写拷贝构造进行深拷贝和写赋值拷贝？
这里也不需要写拷贝构造进行深拷贝，因为这里要的就是浅拷贝。begin返回了第一个节点的迭代器给it，这里就是用默认生成的拷贝构造，浅拷贝给it，那这两个迭代器就指向同一个节点，所以这里用默认的拷贝构造和赋值拷贝就可以了。

3、成员函数

对于list的常见成员函数的实现我们已近轻车熟路了！这里就直接给源码了！

//链表的节点
template<class T>
struct list_node
{list_node(const T& val = T()):data(val),pre(nullptr),next(nullptr){}T data;//数据list_node<T>* pre;//前驱指针list_node<T>* next;//后继指针
};//链表的迭代器
template<class T, class ref,class ptr>
struct list_iterator
{typedef  list_node<T> node;//给节点取别名typedef	 list_iterator<T, ref, ptr> self;//给自己取别名node* it;//链表中的迭代器其实就是一个节点的指针//只不过其访问和迭代操作要用一个类封装起来list_iterator(node* node):it(node){}//返回T*ptr operator->(){return &(it->data);}//返回T&ref operator*(){return it->data;}//（前置++）++itself& operator++(){it = it->next;return *this;}/*self operator++(){it = it->next;return it;}*///（前置--）--itself& operator--(){it = it->pre;return *this;}/*self operator--(){it = it->pre;return it;}*///(后置++) it++self operator++(int) {self tmp(*this);it = it->next;return tmp;//一定不能用引用接收，不然会有野指针！}//(后置--) it--self operator--(int) {self tmp(*this);it = it->pre;return tmp;}//比较迭代器里面的it指针相不相等bool operator==(const self& comp){return it==comp.it;}bool operator!=(const self& comp){return it!=comp.it;}};//双向循环带头链表
template<class T>
class list
{
public:typedef list_node<T> node;//给节点取别名typedef list_iterator<T, T&, T*> iterator;//普通迭代器typedef list_iterator<T, const T&, const T*> const_iterator;//常量迭代器//sizesize_t size() const{return _size;}//beginiterator begin(){return _head->next;}//enditerator end(){return _head;}//cbeginconst_iterator begin() const{return _head->next;}//cendconst_iterator end() const{return _head;}//clearvoid clear(){auto it = begin();while (it!= end()){it=erase(it);}}//swapvoid swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//emptybool empty(){return _size == 0;}//空初始化void emptyInit(){_head = new node;_head->next = _head->pre = _head;_size = 0;}//无参的默认构造list(){emptyInit();}//拷贝构造list(const list<T>& lt){emptyInit();//先空参构造_headfor (auto& e : lt){push_back(e);}/*auto it = lt.begin();while (it != lt.end()){push_back(*it);++it;}*/}//赋值运算符重载list<T>& operator=(list<T> tmp){swap(tmp);return *this;}//析构~list(){clear();delete _head;_head = nullptr;}//insertiterator insert(iterator pos, const T& val){node* newNode = new node(val);node* cur = pos.it;node* pre = cur->pre;newNode->next = cur;newNode->pre = pre;pre->next = newNode;cur->pre = newNode;_size++;return newNode;}//push_front（头插）void push_front(const T& val){insert(begin(), val);}//push_back（尾插）void push_back(const T& val)//传引用减少拷贝构造{/*node* newNode = new node(val);node* tail = _head->pre;tail->next = newNode;newNode->next = _head;newNode->pre = tail;_head->pre = newNode;++_size;*/insert(end(), val);}//eraseiterator erase(iterator pos){assert(pos != end());node* next = pos.it->next;node* pre = pos.it->pre;pre->next = next;next->pre = pre;delete pos.it;pos.it = nullptr;_size--;return next;}//pop_front(头删)void pop_front(){erase(begin());}//pop_back(尾删)void pop_back(){erase(--end());}private:node* _head=nullptr;//带哨兵卫的头结点size_t _size = 0;//记录节点个数
};

4、完结散花

好了，这期的分享到这里就结束了~

如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~

我们下期不见不散~~

​​​​​​

这篇关于C++从入门到起飞之——list模拟实现 全方位剖析！的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1122872。

相关文章

Springboot处理跨域的实现方式(附Demo)

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》：本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.
阅读更多...
Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE？1.2 SSE 的优点1.3 适用场景2. Spring WebFlu
阅读更多...
基于SpringBoot实现文件秒传功能

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.
阅读更多...
SpringBoot日志配置SLF4J和Logback的方法实现

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一：初识日志三、案例二：使用Lombok输出日志四、案例三：配置Logback一
阅读更多...
Python如何使用__slots__实现节省内存和性能优化

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景：内存吃得满满的类__slots__：你的内存管理小助手举个大概的例子：看看效果如何？1.
阅读更多...
Python+PyQt5实现多屏幕协同播放功能

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述：突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专
阅读更多...
Python实现无痛修改第三方库源码的方法详解

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很
阅读更多...
idea中创建新类时自动添加注释的实现

idea中创建新类时自动添加注释的实现

《idea中创建新类时自动添加注释的实现》在每次使用idea创建一个新类时,过了一段时间发现看不懂这个类是用来干嘛的,为了解决这个问题,我们可以设置在创建一个新类时自动添加注释,帮助我们理解这个类的用... 目录前言：详细操作：步骤一：点击上方的 文件（File），点击&nbmyHIgsp;设置（Setti
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
MySQL大表数据的分区与分库分表的实现

MySQL大表数据的分区与分库分表的实现

《MySQL大表数据的分区与分库分表的实现》数据库的分区和分库分表是两种常用的技术方案,本文主要介绍了MySQL大表数据的分区与分库分表的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有... 目录1. mysql大表数据的分区1.1 什么是分区？1.2 分区的类型1.3 分区的优点1.4 分
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2