吕子乔做网站吹的语录,怎么样做网站推广,农村自建房设计图软件,市桥网站建设哪家好【C】---STL之list的模拟实现 一、list模拟实现思路二、结点类的实现三、list迭代器的实现1、ListIterator类2、构造函数3、operator*运算符重载5、operator-运算符重载6、operator#xff01;运算符重载7、operator运算符重载8、前置9、后置10、前置--11、后置-- 四、lis… 【C】---STL之list的模拟实现 一、list模拟实现思路二、结点类的实现三、list迭代器的实现1、ListIterator类2、构造函数3、operator*运算符重载5、operator-运算符重载6、operator运算符重载7、operator运算符重载8、前置9、后置10、前置--11、后置-- 四、list类的实现1、list类2、构造3、析构4、拷贝构造5、赋值运算符重载1传统的赋值运算符重载2现代的赋值运算符重载 6、迭代器7、insert()8、erase()9、clear()10、push_front()11、push_back()12、pop_front()13、pop_back()14、empty()15、size() 五、完整代码 一、list模拟实现思路
list的模拟实现比 string vector的模拟实现略微复杂一点
1由于链表的每一个结点本身就是一个结构体里面包括数据和指针所以在接下来的模拟中我们会将链表的每一个结点封装为一个类也就是结点类。
2链表中数据的物理储存空间是不连续的但是string和vector他们的数据储存物理空间是连续的。因此在访问链表的数据的时候不能用原生的迭代器来进行访问我们需要自己重载一个迭代器自己封装一个迭代器的类。 list的模拟的大体思路
二、结点类的实现
单个结点类的成员变量有三个
1结点值_val
2指向前一个结点的指针_prev
3指向后一个结点的指针_next
结点无需拷贝构造、赋值运算符重载由于没有额外申请空间因此也不需要析构 // 1.单个的结点类templateclass Tstruct Listnode{T _val;ListnodeT* _next;ListnodeT* _prev;// 构造:Listnode(const T x T()):_val(x), _next(nullptr), _prev(nullptr){}};三、list迭代器的实现
1、ListIterator类
1我们为什么要对链表的迭代器进行一个单独的封装
因为之前普通的迭代器都是连续可以直接进行访问数据。
但是链表不一样物理空间连续所以说我要把这个迭代器进行一个类的封装然后在里面对他运算符重载例如我们就可以掌控这个迭代器的行为
当原生的迭代器或者运算符不合我们所需要的预期的话就可以把它进行一个封装我们自己来重载达到我们所需要的预期
2迭代器有两种一种是普通迭代器一种是const的迭代器
为了不使代码冗余我们就会将两个迭代器写在一起用模板
对于T类模板实例化出两个类一个是T类一个是const T类同理T*也一样。使用
templateclass T,class Ref,class Ptr// RefT PtrT*类模板就会实例化出来两个类一个是普通的、不带const的TT T*另一个是带const的Tconst T const T*其中Ref是引用Ptr是指针该类模板实例化了以下这两个类模板
template classT,T,T* iterator;
template classconst T, const T ,const T* const_iterator;这样我们就解决了两个类的问题。
2、构造函数
templateclass T,class Ref,class Ptrstruct ListIterator{typedef ListnodeT Node;// 1.(这个是单个结点“类型”的重定义) 不管你是什么类型的结点 我都给你整成Node因为ListnodeT是一个结点模版typedef ListIteratorT, Ref, Ptr Self; // 2.(这个是本迭代器指针“类型”的重定义)// 成员变量Node* _node;// 构造ListIterator(const Node* node):_node(node){}};3、operator*运算符重载
// 重载*(*it)// RefTRef operator*()// 为什么要传引用返回呢因为有的时候我们可能需要对it进行修改1,-1等等。{return _node-_data;}
5、operator-运算符重载
// 重载-//PtrT*Ptr operator-(){
6、operator运算符重载
对于和!的重载的时候我们一定要想清楚到底是对它里面节点的值来判断相不相等还是说来判断指向这个结点的迭代器指针相不相等。很明显我们这里重载 和通过判断结点的迭代器相等不相等来进行重载的。
// !bool operator!(const Self it){return _node ! it._node;}7、operator运算符重载
比较两个迭代器相等不相等的时候一定不能比较所指向节点中的值万一所有的节点里面值相等都是一样那你意思就是说这里面的所有迭代器都是相等吗不就扯淡吗所以说比较迭代器相不相等就是比较两者是不是指向同一个结点即比较指针是否相等因为迭代器本质上是指针
bool operator(const Self it){return _node it._node;}8、前置
//前置,(it)Self operator()//因为对内容进行了修改所以要传引用返回{_node _node-_next;return *this;}9、后置
//后置(it)Self operator(int){Self tmp *this;//因为后置要返回的是之前的值所以要先保存未的值在tmp里面_node _node-_next;return tmp;}10、前置–
//前置--,(--it)Self operator--()//因为--对内容进行了修改所以要传引用返回{_node _node-_prev;return *this;}11、后置–
//后置--(it)Self operator--(int){Self tmp *this;//因为后置--,要返回的是--之前的值所以要先保存未--的值在tmp里面_node _node-_prev;return tmp;}四、list类的实现
1、list类
list的成员只需要一个头节点然后通过迭代器来访问后面的其他元素即可。
2、构造
//1、构造list(){_head new Node;//会调ListNode的构造函数_head-_next _head;//整个链表只有头节点先构造一个没有实际节点的链表_head-_prev _head;//整个链表只有头节点先构造一个没有实际节点的链表}3、析构
// 2、析构~list(){clear();delete[] _head;_head nullptr;}4、拷贝构造 //特意写一个初始化一个哨兵位void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;_size 0;}// 3、拷贝构造// lt2(lt1)list(const listT lt){empty_init();//先初始化一个头结点for (auto e : lt)// 接下来在哨兵位后面 尾插 就可以实现拷贝构造{push_back(e);}}// 需要析构一般就需要自己写深拷贝// 不需要析构一般就不需要自己写深拷贝默认浅拷贝就可以};5、赋值运算符重载
1传统的赋值运算符重载 //赋值运算符重载 lt1 lt 传统写法listT operator(const listT lt){//链表已存在只需将节点尾插进去即可if(this ! lt){for (auto e : lt){push_back(e);}}}2现代的赋值运算符重载
//4、赋值运算符重载(深拷贝)// lt1lt2listT operator(listT lt){swap(lt);return *this;}void swap(listT lt){std::(_head, lt._head);std::(_size, lt._size);}6、迭代器
1普通迭代器
iterator begin(){//iterator it _head-_next;// 有名对象 //调用迭代器的构造函数创建一个迭代器it//return it;return iterator(_head-_next);// 匿名对象// return _head-_next; // 不能这样写因为返回类型是迭代其指针而你这样返回的是一个结点。}iterator end(){return iterator(_head);}只要你有节点的指针就可以构造迭代器 下面这里就是构造了一个迭代器因为它的返回类型是迭代器你只要有节点的指针我就可以构造一个迭代器只不过有两种情况是匿名对象另外一种是有名对象 2const迭代器 const_iterator begin() const{return const_iterator(_head-_next);//头节点不存数据}const_iterator end() const{return const_iterator(_head);//尾节点的下一个节点位置即头节点}7、insert()
// 3.insertvoid insert(iterator pos, const T val)//在pos位置之前插入val{//先用一个指针保存pos的位置Node* cur pos._node;//创建一个新的节点newnode来接受val的值Node* newnode new Node(val);//再保存pos位置前一个方便newnode插入Node* prev cur-_prev;//prev newnode cur三者之间的交换newnode-_prev prev;prev-_next newnode;newnode-_next cur;cur-_prev newnode;}8、erase()
iterator erase(iterator pos){// 1、先保存pos位置的前后Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;// 2、prev 和 next两者之间进行链接prev-_next next;next-_prev prev;// 3、直接删除curdelete cur;// 4、因为是模拟原本库里面的erase函数返回的就是要删除pos位置的下一个位置的迭代器。return iterator(next);}9、clear() void clear(){iterator it begin();while (it ! end()){it erase(it);//因为erase会返回要删除结点的下一个位置所以要用iterator类型的it接受}}10、push_front()
// 头插void push_front(const T x){insert(begin(), x);}11、push_back()
// 尾插void push_back(const T x){insert(end(), x);}12、pop_front()
// 头删void pop_front(){erase(begin());}13、pop_back()
// 尾删void pop_back(){erase(--end());}
14、empty()
bool empty(){return (_head-_next _head);}15、size()
size_t size()const{size_t count 0;Node* cur _head;while (cur-_next ! _head){cur cur-_next;count;}return count;}
五、完整代码
#pragma once
#include assert.h
#includeiostream
using namespace std;namespace yjl
{templateclass Tstruct Listnode{ListnodeT* _prev;ListnodeT* _next;T _data;//单个节点之间的内部构造Listnode(const T x T()):_prev(nullptr), _next(nullptr), _data(x){}};/// ///list迭代器的封装//templateclass T//struct ListIterator//{// typedef ListnodeT Node;// 1.(这个是单个结点“类型”的重定义) 不管你是什么类型的结点 我都给你整成Node因为ListnodeT是一个结点模版// typedef ListIteratorT Self; // 2.(这个是本迭代器指针“类型”的重定义)// Node* _node;// //构造// ListIterator(Node* node)// :_node(node)// {}// // 重载*(*it)// const T operator*()// 为什么要传引用返回呢因为有的时候我们可能需要对it进行修改1,-1等等。// {// return _node-_data;// }// // 重载-// const T* operator-()// {// return _node-_data;//得到的是地址T*// }// //前置,(it)// Self operator()//因为对内容进行了修改所以要传引用返回// {// _node _node-_next;// return *this;// }// //后置(it)// Self operator(int)// {// Self tmp *this;//因为后置要返回的是之前的值所以要先保存未的值在tmp里面// _node _node-_next;// return tmp;// }// //前置--,(--it)// Self operator--()//因为--对内容进行了修改所以要传引用返回// {// _node _node-_prev;// return *this;// }// //后置--(it)// Self operator--(int)// {// Self tmp *this;//因为后置--,要返回的是--之前的值所以要先保存未--的值在tmp里面// _node _node-_prev;// return tmp;// }// bool operator!(const Self it)// {// return _node ! it._node;// }// bool operator(const Self it)// {// return _node it._node;// }//};// typedef ListIteratorT,T,T* iterator;// typedef ListIteratorT,const T,const T* const_iterator;//list迭代器的封装templateclass T,class Ref,class Ptr// RefT PtrT*struct ListIterator{typedef ListnodeT Node;// 1.(这个是单个结点“类型”的重定义) 不管你是什么类型的结点 我都给你整成Node因为ListnodeT是一个结点模版typedef ListIteratorT,Ref,Ptr Self; // 2.(这个是本迭代器指针“类型”的重定义)Node* _node;//构造ListIterator(Node* node):_node(node){}// 重载*(*it)// RefTRef operator*()// 为什么要传引用返回呢因为有的时候我们可能需要对it进行修改1,-1等等。{return _node-_data;}// 重载-//PtrT*Ptr operator-(){return _node-_data;//得到的是地址T*}//前置,(it)Self operator()//因为对内容进行了修改所以要传引用返回{_node _node-_next;return *this;}//后置(it)Self operator(int){Self tmp *this;//因为后置要返回的是之前的值所以要先保存未的值在tmp里面_node _node-_next;return tmp;}//前置--,(--it)Self operator--()//因为--对内容进行了修改所以要传引用返回{_node _node-_prev;return *this;}//后置--(it)Self operator--(int){Self tmp *this;//因为后置--,要返回的是--之前的值所以要先保存未--的值在tmp里面_node _node-_prev;return tmp;}bool operator!(const Self it){return _node ! it._node;}bool operator(const Self it){return _node it._node;}};/// ///templateclass Tclass list{typedef ListnodeT Node;public:typedef ListIteratorT,T,T* iterator;typedef ListIteratorT, const T,const T* const_iterator;iterator begin(){//iterator it _head-_next;// 有名对象 //调用迭代器的构造函数创建一个迭代器it//return it;return iterator(_head-_next);// 匿名对象// return _head-_next; // 不能这样写因为返回类型是迭代其指针而你这样返回的是一个结点。}iterator end(){return iterator(_head);}// 1.多个节点之间的构造初始化一个哨兵位//特意写一个初始化一个哨兵位void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;_size 0;}// 构造list(){empty_init();}// 拷贝构造函数// lt2(lt1)list(const listT lt){empty_init();// 先构造一个哨兵位头结点for (auto e : lt)// 接下来在哨兵位后面 尾插 就可以实现拷贝构造{push_back(e);}}// 需要析构一般就需要自己写深拷贝// 不需要析构一般就不需要自己写深拷贝默认浅拷贝就可以//赋值运算符重载(深拷贝)// lt1lt2listT operator(listT lt){swap(lt);return *this;}void swap(listT lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}// 析构~list(){clear();delete _head;_head nullptr;}// 2.push_back() //void push_back(const T x)//{// Node* tmp new Node(x);// Node* tail _head-_prev;// 因为要尾插所以保存好尾节点// tail-_next tmp;// tmp-_prev tail;// tmp-_next _head;// _head-_prev tmp;//}// 头插void push_front(const T x){insert(begin(), x);}// 尾插void push_back(const T x){insert(end(), x);}// 头删void pop_front(){erase(begin());}// 尾删void pop_back(){erase(--end());}// 3.insertvoid insert(iterator pos, const T val)//在pos位置之前插入val{//先用一个指针保存pos的位置Node* cur pos._node;//创建一个新的节点newnode来接受val的值Node* newnode new Node(val);//再保存pos位置前一个方便newnode插入Node* prev cur-_prev;//prev newnode cur三者之间的交换newnode-_prev prev;prev-_next newnode;newnode-_next cur;cur-_prev 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;// 我们delete cur之后原来的pos迭代器指针也就消失了但是我们为什么必须要返回一个迭代器指针return iterator(next);// 因为删除的数据是有不确定性的万一要删除偶数或者后面有其他的用途我们没有原来pos的位置我们如何再找到其他的数据呢}void clear(){iterator it begin();while (it ! end()){it erase(it);//因为erase会返回要删除结点的下一个位置所以要用iterator类型的it接受}}//size_t size()const//{// size_t count 0;// while (_head-_next ! _head)// {// _head _head-_next;// 因为_head是不能被修改的所以要创建一个临时指针来指向_head// count;// }// return count;//}size_t size()const{size_t count 0;Node* cur _head;while (cur-_next ! _head){cur cur-_next;count;}return count;}bool empty(){return (_head-_next _head);}private:Node* _head;size_t _size;};好了今天的分享就到这里了 如果对你有帮助记得点赞关注哦 我的主页还有其他文章欢迎学习指点。关注我让我们一起学习一起成长吧
