【C++】——list模拟实现(包懂的,细节满满)

2024-06-04 14:36

本文主要是介绍【C++】——list模拟实现(包懂的,细节满满),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

list的模拟实现和string和vector的有区别的,但是也有相同。

区别:list的迭代器底层和其他两个迭代器底层有很大区别,因为list的链式结构决定了与它们两个的不一样

相同:迭代器用法大致一样,其他成员函数的使用也大致一样。

本章不仅仅会模拟实现list,同时里面涉及的诸多细节也会一一解释,所以这次的模拟实现也可以是对之前的学习的总结和回顾。

目录

前言

list总体框架

一  list结点

二  list类框架

三  list迭代器

3.1 list迭代器框架

3.2  list常用迭代器

 3.2 list const迭代器

四  list类详解

4.1 插入和删除

 4.2  拷贝构造和赋值运算符重载

 4.3 list析构函数

五  list完整代码

六  细节处理

6.1迭代器的拷贝构造和析构函数

6.2  自定义类型

6.3  打印函数

总结


list总体框架

这里其实和链表一样,我们需要用一个类去把结点表示出来,同时我们还需要用一个类表示list,再者就是还需要一个类去表示迭代器。

在之前的模拟实现中,迭代器我们直接用的是指针表示,但是在这里不行,因为链表不是连续的空间,所以不能通过指针的加减来表示迭代器的进退,但是对于迭代器的操作来说我们可以用运算符重载去模拟,由由于把迭代器一起写进list里面会看起来非常冗余,所以这里采用封装的思想,把迭代器的实现封装起来,也有利于后面的操作

一  list结点

用类来封装一个一个结点,里面有两个指针,一个是指向下一个位置的指针,一个是指向前一个位置,还有一个用来存放数据的变量

template <class T>
struct List_node
{T _data;List_node<T>* _next;List_node<T>* _prev;//构造函数List_node(const T&x=T()):_data(x),_next(nullptr),_prev(nullptr){}
};

由于我们后面会在类外访问,所以为了避免麻烦就写成stuct,这样成员都是public

同时这里使用模板,为了适应各种数据类型

对于构造函数来说,我们直接用初始化列表进行初始化,对于_data的初始化来说,我们用const T&x=T() 这里的T()是一个匿名类型,如果我们没有传参,那么就会去调用相应类型的构造函数

二  list类框架

list类里面包含的是结点的指针,也就是哨兵位头节点的指针

template<class T>
class List
{public:typedef List_node<T> Node;//取别名void empty_Init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}List()//构造函数{empty_Init();}private:Node*_head;//头节点
}

 由于之前封装了结点,所以这里直接用,注意因为结点的封装是一个模板,所以我们在List里面声明的时候也要带上模板,不然会显示找不到对应的构造函数的

因为是双向循环链所以一开始先把所有指针都指向自己就行(注意需要new一个结点出来,这里很容易忘记)

构造的细节并没有写在构造函数里面,而是用一个函数封装起来,因为在之后的拷贝构造中我们也需要构造一个头节点的步骤。

 

三  list迭代器

3.1 list迭代器框架

在前面说了,这里的迭代器是用封装加运算符重载来实现的,由于迭代器也会有很多类型,所以我们使用模板的形式

template<class T>struct _list_iterator{typedef list_node<T> Node;//我们需要一个结点指针去指向结点typedef _list_iterator<T> iterator;//名字太长不好写Node* _node;_list_iterator(Node* node) :_node(node)//构造函数{}}

这里也要注意,因为前面都是模板,所以记得<T>

对于这里的构造函数来说,因为我们使用迭代器都是用一个结点的指针进行构造,同时单参数的构造函数支持隐式类型的转换(如果不理解,可以往后看

3.2  list常用迭代器

list迭代器的各种操作都是用运算符重载来模拟的,所以我们可以写出下面代码

template<class T>struct _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T> iterator;Node* _node;_list_iterator(Node* node) :_node(node){}iterator& operator++()//前置{_node = _node->_next;//直接往下一个结点走return *this;}iterator operator++(int)//后置{iterator tem(*this);_node = _node->_next;return tem;}iterator& operator--(){_node = _node->_prve;//往前一个结点走return *this;}iterator operator--(int){iterator tem(*this);_node = _node->_prve;return tem;}T& operator*(){return _node->_data;//取出结点的数据}T* operator->(){return &_node->_data;}bool operator!=(const iterator& s){return _node != s._node;//比较结点是否是同一个}};

迭代器的每一个操作都采用了运算符重载,其实这样看来还是指针在操作,只不过他不是直接的进行操作,而是换了一种方式

 3.2 list const迭代器

这里的const迭代器也和之前的迭代器有很大不同,之前的迭代器直接在前面加const就行,如果我们直接用 const iterator,那么这个const的作用是现在迭代器的变化,而不是限制迭代器指向的内容,所以这样使用会导致迭代器无法移动

 对于之前的string来说,const迭代器是const char* ,它修饰的是指向字符串的内容,但是这里是const iterator ,它修饰的是iterator,所以两者是不一样的

 所以我们只能再封装一个const迭代器

template<class T>struct const_list_iterator{typedef list_node<T> Node;typedef const_list_iterator<T> _iterator;Node* _node;const_list_iterator(Node* node) :_node(node){}iterator& operator++(){_node = _node->_next;return *this;}iterator operator++(int)//后置{iterator tem(*this);_node = _node->_next;return tem;}iterator& operator--(){_node = _node->_prve;return *this;}iterator operator--(int){iterator tem(*this);_node = _node->_prve;return tem;}const T& operator*()const {return _node->_data;}const T* operator->()const{return &_node->_data;}bool operator!=(const iterator& s){return _node != s._node;}};

但是我们发现const迭代器和非const迭代器的区别就是在 

这两个运算符重载的区别就在于这两个,变化很小,但是我们写了两个迭代器,这样看起来就很冗余

所以这里也可以采用模板的形式对它进行改造。

思路就是先写一个迭代器模板,用这个模板去构造两种迭代器,把任务交给编译器就行

template<class T,class Ref,class Ptr>
struct _List_iterator
{typedef _List_iterator<T,Ref,Ptr> iterator;typedef List_node<T> Node;Node* _node;//构造函数_List_iterator(Node* node):_node(node){}iterator& operator++(){_node = _node->_next;return *this;}iterator& operator++(int){iterator tmp(*this);_node = _node->_next;return tmp;}iterator& operator--(){_node = _node->_prev;return *this;}iterator& operator--(int){iterator tmp(*this);_node = _node->_prev;return tmp;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const iterator& s){return _node != s._node;}};

由于需要改动的重载函数,有两个不同的类型一个是*,一个是&,所以模板里面再加两个参数

有了这个模板,我们再list里面可以去构造两种迭代器 。

四  list类详解

弄好了迭代器,我们就可以写相应的成员函数了。

4.1 插入和删除

对于插入和删除来说,就是数据结构中链表的插入和删除

iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node*prve = cur->_prev;Node* newnode = new Node(x);prve->_next = newnode;newnode->_prev = prve;newnode->_next = cur;cur->_prev = newnode;return newnode;//这里不是pos的位置改变,这里返回的是新插入的位置//在用的时候可以不去接收返回值}iterator erase(iterator pos){Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;delete cur;prev->_next = next;next->_prev = prev;return next;//迭代器会失效}

这里的插入位置都是迭代器类型的变量

之前vector的插入和删除操作会导致迭代器失效的问题,list的插入操作不会导致迭代器失效,因为list没有扩容的操作。所以也就没有改变相应的位置,但是删除操作有迭代器失效的问题,所以我们在使用的时候记得去接收一下新的位置 

有了插入和删除这两个函数,那我们就可以轻松实现头插,尾插,头删,尾删了

void push_back(const T &x)//尾插{insert(end(), x);}void push_front(const T& x)//头插{insert(begin(), x);}void pop_back()//尾删{erase(end());}void pop_front()//头删{erase(begin());}
 4.2  拷贝构造和赋值运算符重载

对于这两个,相信我们都不会陌生了

拷贝构造:一个已经初始化的对象和一个没有初始化的对象

赋值运算符重载:两个都是已经存在的对象,所以赋值运算符重载另外一种写法就是先清理数据然后再一个个尾插。

拷贝构造

List(const List<T>& lt){empty_Init();for (auto e : lt){push_back(e);}}

 赋值运算符重载

	void swap( List<T>tmp){std::swap(_head, tmp._head);}List<T>operator=( List<T> tmp){swap(tmp);return *this;}

这里再对赋值运算符重载进行一下说明,我们在用的时候会传参给tmp,这里调用拷贝构造,创建了一个新的结点,所以交换一下,并没有说两个对象指向同一块空间,所以不存在析构两次的问题

对于赋值运算符重载来说,还有一种写法,就是先清理数据,然后再一个个尾插

 4.3 list析构函数
~List(){iterator it =begin();while(it != end()){it=erase(it);}}

就是把数据一个个删除就行。

 

五  list完整代码

#pragma once
template <class T>
struct List_node
{T _data;List_node<T>* _next;List_node<T>* _prev;//构造函数List_node(const T&x=T()):_data(x),_next(nullptr),_prev(nullptr){}
};template<class T,class Ref,class Ptr>
struct _List_iterator
{typedef _List_iterator<T,Ref,Ptr> iterator;typedef List_node<T> Node;Node* _node;//构造函数_List_iterator(Node* node):_node(node){}iterator& operator++(){_node = _node->_next;return *this;}iterator& operator++(int){iterator tmp(*this);_node = _node->_next;return tmp;}iterator& operator--(){_node = _node->_prev;return *this;}iterator& operator--(int){iterator tmp(*this);_node = _node->_prev;return tmp;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const iterator& 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;}//构造函数void empty_Init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}List(){empty_Init();}~List(){iterator it =begin();while(it != end()){it=erase(it);}}//List(const List<T>& lt){empty_Init();for (auto e : lt){push_back(e);}}void swap( List<T>tmp){std::swap(_head, tmp._head);}List<T>operator=( List<T> tmp){swap(tmp);return *this;}void push_back(const T &x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(end());}void pop_front(){erase(begin());}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node*prve = cur->_prev;Node* newnode = new Node(x);prve->_next = newnode;newnode->_prev = prve;newnode->_next = cur;cur->_prev = newnode;return newnode;}iterator erase(iterator pos){Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;delete cur;prev->_next = next;next->_prev = prev;return next;}private:Node* _head;
};//打印
template<typename Container>
void print_container(const Container& con)
{typename Container::const_iterator it = con.begin();while (it != con.end()){cout << *it << " ";++it;}cout << endl;
}

六  细节处理

6.1迭代器的拷贝构造和析构函数

在上面代码中我们没有写迭代器的析构函数和拷贝构造,因为我们不需要析构函数,我们不能说遍历一遍结点就把结点给释放了,再者就是拷贝构造

    List<int>::iterator it = lt.begin();这断代码表示的是lt.begin()返回一个迭代器类型,然后拷贝构造给it,那存不存在析构两次的问题呢,答案是不存在

我们需要的就是浅拷贝,我们要的就是it指向这个结点的位置,同时也只有它指向,所以在函数结束的时候,这个it会被销毁。

所以我们不需要写拷贝构造和析构函数,拷贝构造直接用编译器的浅拷贝就行。对于析构函数来说,因为这里的迭代器只起到遍历的作用,所以不需要去释放任何资源。而且如果写了析构还会出现各种析构两次的问题

6.2  自定义类型
class AA
{
public:AA(int a1=0,int a2=0):_a1(a1),_a2(a2){}int _a1;int _a2;
};
void test1()
{List<AA>lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(2, 2));List<AA>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}
}

对于这个来说这样写是错误的,因为AA类里面没有重载<<这个运算符

所以我们得换一直方式

void test1()
{List<AA>lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(2, 2));List<AA>::iterator it = lt.begin();while (it != lt.end()){cout << (*it)._a1 << " " << (*it)._a2 << endl;it++;}while (it != lt.end()){cout << it->_a1 << " " << it->_a2 << endl;it++;}
}

这就是为什么要重载->运算符的原因,这个是给自定义类型用的,对于知内置类型直接解引用就行。

6.3  打印函数

在上面的完整代码中有一个打印函数,它也是用模板实现的,主要是为了打印各种容器

//打印
template<typename Container>
void print_container(const Container& con)
{typename Container::const_iterator it = con.begin();while (it != con.end()){cout << *it << " ";++it;}cout << endl;
}

 这里的不同是我们之前都是用class的,这里用的是typename,原因在于编译器在编译的时候,会去Container里面去找const_iterator这个类型,但是Container是一个模板,并没有实例化,所以编译器也不知道怎么定义,所以就在编译的时候就过不了,但是我们在前面加一个typename就会告诉编译器,先过,后面再来实例化,这样就可以解决问题了

总结

以上就是list模拟实现的全部内容了,希望对你有所帮助 

 

 

这篇关于【C++】——list模拟实现(包懂的,细节满满)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1030337

相关文章

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、

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

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

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实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

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

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

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

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

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

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

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

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