2021年最新的网站,500网站建设,那个网站可以做恒指 买涨买跌,沈阳工程信息网官网文章目录 全部的实现代码放在了文章末尾准备工作包含头文件定义命名空间类的成员变量为什么节点类是用struct而不是class呢#xff1f;为什么要写get_head_node? 迭代器迭代器在list类里的实例化和重命名普通迭代器operator-()的作用是什么#xff1f; const迭代器反向迭… 文章目录 全部的实现代码放在了文章末尾准备工作包含头文件定义命名空间类的成员变量为什么节点类是用struct而不是class呢为什么要写get_head_node? 迭代器迭代器在list类里的实例化和重命名普通迭代器operator-()的作用是什么 const迭代器反向迭代器迭代器的获取 构造函数默认构造使用n个val构造迭代器区间构造解决迭代器区间构造 和 用n个val构造的冲突initializer_list构造拷贝构造 析构函数swap赋值运算符重载erase删除pos迭代器指向的节点为什么要返回next 删除迭代器区间 insert在迭代器pos之前插入一个节点为什么要返回newnode?在迭代器pos之前插入一个迭代器区间的数据 push_backpush_frontpop_frontpop_backsizeemptybackfrontassignresizeclear全部代码 全部的实现代码放在了文章末尾
准备工作
创建两个文件一个头文件mylist.hpp一个源文件test.cpp
【因为模板的声明和定义不能分处于不同的文件中所以把成员函数的声明和定义放在了同一个文件mylist.hpp中】 mylist.hpp存放包含的头文件命名空间的定义成员函数和命名空间中的函数的定义
test.cpp存放main函数以及测试代码 包含头文件 iostream用于输入输出 assert.h用于使用报错函数assert 定义命名空间
在文件mylist.hpp中定义上一个命名空间mylist 把list类和它的成员函数放进命名空间封装起来防止与包含的头文件中的函数/变量重名的冲突问题 类的成员变量
参考了stl源码中的list的实现stl中list的底层链表是双向带头循环链表 【可以看我这篇文章了解双向带头循环链表的实现链表的极致——带头双向循环链表】 成员变量只有一个就是指向双向带头循环链表的头节点的指针。
节点类 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PgC6iunX-1720663070797)(https://i-blog.csdnimg.cn/direct/667727a5535e4a7c95e931618f6a1662.png#pic_center)]
为什么节点类是用struct而不是class呢
因为节点类里面的成员变量在实现list的时候需要经常访问所以需要节点类的成员变量是公有的【使用友元也可以但是比较麻烦】 struct的默认访问权限就是公有不用加访问限定符了stl中实现的节点类也是struct class的默认访问权限是私有的 list类 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZKrXfgK4-1720663070798)(https://i-blog.csdnimg.cn/direct/2546f7b1d9fe49029c3dc6aa0fd84f00.png#pic_center)]
为什么要写get_head_node?
因为插入节点之前必须要有头节点 所以把创建初始头节点的操作写成了一个函数用于 所有构造函数插入节点之前进行申请头节点 迭代器
因为list存储数据的方式是创建一个一个的节点存储数据 所以存储数据的空间不是连续的所以不能直接用指针作为迭代器
因为指向一个节点的指针直接,是不一定能指向下一个节点的
所以要把迭代器实现成一个类这样才可以正确地支持- -*等操作
迭代器在list类里的实例化和重命名
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qjqNyMDi-1720663070799)(https://i-blog.csdnimg.cn/direct/506afbbbf0534c61b435d2d371e2113d.png#pic_center)]
普通迭代器
templateclass T, class R, class F
struct Iterator
{把自己的类型重命名一下typedef IteratorT, R, F Self;成员变量的类型是 双向带头循环链表的节点类型listnodeT* _n;Iterator(listnodeT*lnullptr) 构造函数{_n l;}Self operator()前置{就是指向下一个节点_n _n-_next;return *this;}Self operator(int) 后置{Self tmp *this; 先记录一下之前的值_n _n-_next; 再return tmp;}Self operator--() 前置--{--就是指向上一个节点_n _n-_prev;return *this;}Self operator--(int) 后置--{Self tmp *this; 先记录一下--之前的值_n _n-_prev; 再--return tmp;}R operator*()const{类比指针*就是获取 节点中存储的数据return _n-_data;}F operator-()const{返回 节点中 存储数据的成员变量的 地址return (_n-_data);}bool operator!(const Selfobj)const{return _n ! obj._n;}bool operator(const Self obj){return !(*this ! obj);}
};operator-()的作用是什么
为了实现 当节点中存储的数据是自定义类型的变量时可以直接使用 迭代器-访问自定义类型中的成员 【原来访问需要调用两次-为了可读性省略了一个-】
例 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kD0EkJ8j-1720663070800)(https://i-blog.csdnimg.cn/direct/68c293cf351f423fb9a05da5b82d6196.png#pic_center)] const迭代器
const迭代器与普通迭代器的区别是什么 区别就只有不能通过const迭代器改变节点中存储的数据
转换一下就是
不能使用迭代器的operator*()改变节点中存储的数据即把operator*()的返回值改成const T就可以了不能使用迭代器的operator-()改变节点中存储的数据的成员即把operator-()的返回值改成const T*就可以了
所以const迭代器与普通迭代器的区别就只有两个函数的返回值类型不同所以增加两个模板参数R和F
普通迭代器实例化时:R就是TF就是T* const迭代器实例化R就是const TF就是const T* 反向迭代器
反向迭代器与普通迭代器的实现上的区别就是 普通迭代器是指向下一个节点 反向迭代器是指向上一个节点 普通迭代器- -是指向上一个节点 反向迭代器- -是指向下一个节点
templateclass T, class R, class F
struct Reverse_iterator
{把自己的类型重命名一下typedef Reverse_iteratorT, R, F Self;成员变量的类型是 双向带头循环链表的节点类型listnodeT* _n;Reverse_iterator(listnodeT* l) 构造函数{_n l;}Self operator(){反向迭代器是移动到 前 一个节点_n _n-_prev;return *this;}Self operator(int){Self tmp *this;_n _n-_prev;return tmp;}Self operator--(){反向迭代器--是移动到 后 一个节点_n _n-_next;return *this;}Self operator--(int){Self tmp *this;_n _n-_next;return tmp;}R operator*()const{return _n-_data;}F operator-()const{return (_n-_data) ;}bool operator!(const Self obj)const{return _n!obj._n;}bool operator(const Self obj)const{return !(*this ! obj);}
};迭代器的获取
iterator begin()
{头节点的下一个节点 才是第一个节点return _head-_next;
}const修饰的对象只能调用const修饰的成员函数
const_iterator begin()const
{头节点的下一个节点 才是第一个节点return _head-_next;
}iterator end()
{最后一个节点的下一个节点是 头节点因为是循环链表return _head;
}const修饰的对象只能调用const修饰的成员函数
const_iterator end()const
{return _head;
}reverse_iterator rend()
{反向迭代器的rend返回的是第一个节点的 前一个节点return _head;
}const修饰的对象只能调用const修饰的成员函数
const_reverse_iterator rend()const
{return _head;
}
reverse_iterator rbegin()
{反向迭代器的rbegin()返回的是 最后一个节点最后一个节点是 头节点的前一个因为是循环链表return _head-_prev;
}const_reverse_iterator rbegin()const
{return _head-_prev;
}构造函数
默认构造
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1GgtecBB-1720663070800)(https://i-blog.csdnimg.cn/direct/90c95c5207f2461193a7424ceaff1e9a.png#pic_center)] 使用n个val构造
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wtIPk0if-1720663070801)(https://i-blog.csdnimg.cn/direct/e72aeab61a5e4eac938b0b20fb9645f4.png#pic_center)] 迭代器区间构造
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Xfp8vYpy-1720663070802)(https://i-blog.csdnimg.cn/direct/9c03aa701d1e4067bf92b0fa220e0918.png#pic_center)] 解决迭代器区间构造 和 用n个val构造的冲突
当重载了迭代器区间构造和使用n个val构造的时候 如果传入的两个参数都是int类型的话就会报错
为什么 因为在模板函数构成重载时编译器会调用更合适的那一个 什么叫更合适 就是不会类型转
如果传入的两个参数都是int类型那么调用的应该是使用n个值构造因为没有int类型的迭代器
但是使用n个值构造的第一个参数是size_t , int传进去要隐式类型转换 而调用迭代器区间构造两个int的实参传进去就会直接把InputIterator推导成int不会发生类型转换所以编译器会调用迭代器区间构造
解决方法 再重载一个使用n个值构造的函数把第一个参数改成int这样根据模板偏特化就会在都不类型转换时优先调用第一个参数特化成int的那个构造函数 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qYHmqtjL-1720663070802)(https://i-blog.csdnimg.cn/direct/1dd1ac43d7e7464c9d36b43f26922525.png#pic_center)] initializer_list构造
写了这个构造函数就可以支持直接使用{}初始化了 例 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nzwhbmge-1720663070803)(https://i-blog.csdnimg.cn/direct/d80c8432dcf048999e714c96ff24d94b.png#pic_center)]
initializer_list是iostream库里面的自定义类型它可以直接接收{ }里面的值 进行初始化而且有迭代器
所以可以直接使用迭代器循环尾插进行对list的构造 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jMz3wcLb-1720663070803)(https://i-blog.csdnimg.cn/direct/a4069ab1989e43528048b1a7e1aec98f.png#pic_center)] 拷贝构造
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-et0I5RLp-1720663070804)(https://i-blog.csdnimg.cn/direct/dbb9b340399c400f8081c14424aabfb6.png#pic_center)] 析构函数
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ymsiGjft-1720663070804)(https://i-blog.csdnimg.cn/direct/5d56f67c54924a40b357464baeb17539.png#pic_center)] swap
只需要交两个list对象的头指针中存储的地址就可以了
因为两个list对象都有头结点交换了头指针中存储的地址就相当于把这两个对象的头指针的指向交换了 而链表的所有节点都是由头节点出发去找到的
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jY0TYhg6-1720663070805)(https://i-blog.csdnimg.cn/direct/f2a37ed2853348448b1ceb75e46d787d.png#pic_center)]
void swap(list obj)
{调用库里面的swap交换头指针std::swap(_head, obj._head);
}赋值运算符重载
list operator (list obj)
{swap(obj);return *this;
}为什么上面的两句代码就可以完成深拷贝呢 这是因为
使用了传值传参会在传参之前调用拷贝构造再把拷贝构造出的临时对象作为参数传递进去
赋值运算符的左操作数*this再与传入的临时对象obj交换就直接完成了拷贝
在函数结束之后存储在栈区的obj再函数结束之后obj生命周期结束
obj调用析构函数把指向的从*this那里交换来的不需要的空间销毁 erase
删除pos迭代器指向的节点
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lEoZYbB4-1720663070805)(https://i-blog.csdnimg.cn/direct/52c9e57f560f4af8b67d46f3bd0c7f4c.png#pic_center)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-L3ji5vVM-1720663070808)(https://i-blog.csdnimg.cn/direct/cf348bb14b83422f9bb24da46f5d11a1.png#pic_center)]
为什么要返回next
因为使用了erase之后的迭代器会失效需要提供更新的方法
为什么使用了erase之后的迭代器会失效
因为pos指向的节点erase之后节点被释放了
stl库里面规定erase的返回值是指向删除数据的下一个数据的迭代器下一个数据就是next指向的数据所以返回next【没有接收返回值的迭代器在检测较严格的编译器中不管指向的位置是否正确都会禁止使用使用了就报错】 删除迭代器区间
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WQ0tx5C9-1720663070809)(https://i-blog.csdnimg.cn/direct/af38f109bbbf4a578c86b6cba3001a80.png#pic_center)] insert
在迭代器pos之前插入一个节点
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SyriqhUO-1720663070810)(https://i-blog.csdnimg.cn/direct/66a804199ba14c179a1dd878db168ea8.png#pic_center)] [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BFOPpreV-1720663070810)(https://i-blog.csdnimg.cn/direct/600ce34d9a304e4286959dbba11c880c.png#pic_center)]
为什么要返回newnode?
list的迭代器pos在使用完insert之后其实是不会失效的
但是为了与其他容器的nsert的返回值进行统一所以也返回了指向新插入的节点的迭代器 在迭代器pos之前插入一个迭代器区间的数据
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-R7FlTK7F-1720663070811)(https://i-blog.csdnimg.cn/direct/d2549108a9314de4a9c74e4bdedb5ab2.png#pic_center)] push_back
复用insert即可
void push_back(const Tval)
{insert(end(), val);
}push_front
复用insert即可
void push_front(const T val)
{insert(begin(), val);
}pop_front
复用erese即可
void pop_front()
{erase(begin());
}pop_back
复用erese即可
void pop_back()
{erase(--end());
}size
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3YbqziMa-1720663070811)(https://i-blog.csdnimg.cn/direct/0b7f0e559d16473ea5dbccc5c14e1730.png#pic_center)] empty
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-59VtLmPm-1720663070811)(https://i-blog.csdnimg.cn/direct/e2df88fd61c74ca0b90abe613cdd9e6a.png#pic_center)] back
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-N7sLJXsd-1720663070812)(https://i-blog.csdnimg.cn/direct/3774472c4f38438db90590472b159be5.png#pic_center)] front
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Jarz2two-1720663070812)(https://i-blog.csdnimg.cn/direct/3f74f58427864bf0bac0e5a93d555454.png#pic_center)] assign
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9gevGVoC-1720663070814)(https://i-blog.csdnimg.cn/direct/4620fd900e984ce3900311a61ab68762.png#pic_center)] resize
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-69kXAjpz-1720663070814)(https://i-blog.csdnimg.cn/direct/d199dc1abebb4b17b161006eea102d00.png#pic_center)] clear
复用erase
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NdJzlJjt-1720663070815)(https://i-blog.csdnimg.cn/direct/154c04d0e7504bc684e9d2ab98667ae0.png#pic_center)] 全部代码
#includeiostream
#includeassert.husing namespace std;namespace mylist
{templateclass Tstruct listnode//双向带头循环链表的节点类{T _data;//节点存储的数据listnode* _next;//指向下一个节点的指针listnode* _prev;//指向前一个节点的指针};templateclass T, class R, class Fstruct Iterator{//把自己的类型重命名一下typedef IteratorT, R, F Self;//成员变量的类型是 双向带头循环链表的节点类型listnodeT* _n;Iterator(listnodeT*lnullptr)//构造函数{_n l;}Self operator()//前置{//就是指向下一个节点_n _n-_next;return *this;}Self operator(int)//后置{Self tmp *this;//先记录一下之前的值_n _n-_next;//再return tmp;}Self operator--()//前置--{//--就是指向上一个节点_n _n-_prev;return *this;}Self operator--(int)//后置--{Self tmp *this;//先记录一下--之前的值_n _n-_prev;//再--return tmp;}R operator*()const{//类比指针//*就是获取 节点中存储的数据return _n-_data;}F operator-()const{//返回 节点中 存储数据的成员变量的 地址return (_n-_data);}bool operator!(const Selfobj)const{return _n ! obj._n;}bool operator(const Self obj){return !(*this ! obj);}};templateclass T, class R, class Fstruct Reverse_iterator{//把自己的类型重命名一下typedef Reverse_iteratorT, R, F Self;//成员变量的类型是 双向带头循环链表的节点类型listnodeT* _n;Reverse_iterator(listnodeT* l)//构造函数{_n l;}Self operator(){//反向迭代器是移动到 前 一个节点_n _n-_prev;return *this;}Self operator(int){Self tmp *this;_n _n-_prev;return tmp;}Self operator--(){//反向迭代器--是移动到 后 一个节点_n _n-_next;return *this;}Self operator--(int){Self tmp *this;_n _n-_next;return tmp;}R operator*()const{return _n-_data;}F operator-()const{return (_n-_data) ;}bool operator!(const Self obj)const{return _n!obj._n;}bool operator(const Self obj)const{return !(*this ! obj);}};templateclass Tclass list{//把双向带头循环链表的节点类型重命名成nodetypedef listnodeT node;private:node* _head;//唯一的成员变量//获取初始头结点node* get_head_node(){//申请一个节点大小的空间node* tmp new node;//最开始的头节点的prev和next都指向自己tmp-_next tmp;tmp-_prev tmp;return tmp;}public:typedef IteratorT, T, T* iterator;//普通迭代器typedef IteratorT, const T, const T* const_iterator;//const迭代器typedef Reverse_iteratorT, T, T* reverse_iterator;//反向迭代器typedef Reverse_iteratorT, const T, const T* const_reverse_iterator;//const反向迭代器list(){//获取头结点//为之后的插入操作做准备_headget_head_node();}list(size_t n, const T valT()){//必须先获取头节点才能进行插入数据_head get_head_node();for (int i 0; i n; i){push_back(val);//尾插n次}}template class InputIteratorlist(InputIterator first, InputIterator last){//必须先获取头节点才能进行插入数据_head get_head_node();while (first ! last){//把解引用之后的值一个一个尾插进去push_back(*first);first;}}list(int n, const T val T()){//必须先获取头节点才能进行插入数据_head get_head_node();for (int i 0; i n; i){push_back(val);}}list(initializer_listT il){//必须先获取头节点才能进行插入数据_head get_head_node();auto it il.begin();while (it ! il.end()){//把解引用之后的值一个一个尾插进去push_back(*it);it;}}list(const list obj){//必须先获取头节点才能进行插入数据_head get_head_node();//使用const迭代器接收 const修饰的对象的迭代器const_iterator it obj.begin();while (it ! obj.end()){//把解引用之后的获得的值一个一个尾插进去push_back(*it);it;}}~list(){//先把list里面除了头结点//以外的节点全部删除clear();//再把头结点申请的空间释放delete _head;_head nullptr;}list operator (list obj){swap(obj);return *this;}void swap(list obj){//调用库里面的swap交换头指针std::swap(_head, obj._head);}iterator begin(){//头节点的下一个节点 才是第一个节点return _head-_next;}//const修饰的对象只能调用const修饰的成员函数const_iterator begin()const{//头节点的下一个节点 才是第一个节点return _head-_next;}iterator end(){//最后一个节点的下一个节点是 头节点//因为是循环链表return _head;}//const修饰的对象只能调用const修饰的成员函数const_iterator end()const{return _head;}reverse_iterator rend(){//反向迭代器的rend返回的是第一个节点的 前一个节点return _head;}//const修饰的对象只能调用const修饰的成员函数const_reverse_iterator rend()const{return _head;}reverse_iterator rbegin(){//反向迭代器的rbegin()返回的是 最后一个节点//最后一个节点是 头节点的前一个//因为是循环链表return _head-_prev;}const_reverse_iterator rbegin()const{return _head-_prev;}void push_back(const Tval){/*node* tail _head-_prev;node* newnode new node;newnode-_data val;newnode-_next _head;newnode-_prev tail;tail-_next newnode;_head-_prev newnode;*/insert(end(), val);}iterator erase(iterator pos){//不能 把 头节点 给删了assert(pos!end());//记录pos的前一个节点prev // 和后一个节点nextnode* prev pos._n-_prev;node* next pos._n-_next;//让prev的下一个节点变成nextprev-_next next;//让prev的上一个节点变成nextnext-_prev prev;//释放pos指向的节点delete pos._n;//返回被删除的节点的下一个节点//用于更新迭代器return next;}iterator erase(iterator first, iterator last){iterator it first;while (it ! last){//删除it指向的节点//删除后让it接收返回值进行更新it erase(it);}//返回被删除的 最后一个节点 的下一个节点//用于更新迭代器return last;}bool empty() const{//size0就 是空 返回true//size!0就 不是空 返回falsereturn size() 0 ;}size_t size()const {//用count记录节点个数size_t count 0;//使用const迭代器接收 const修饰的对象的迭代器const_iterator it begin();//遍历链表while (it ! end()){count;it;}return count;}T back(){//list不能为空为空就报错assert(!empty());//end返回的迭代器指向 头结点//头结点的上一个节点就是最后一个节点//因为是循环链表return *(--end());}//const修饰的成员只能调用const修饰的成员函数const T back() const{assert(!empty());return *(--end());}T front(){//list不能为空为空就报错assert(!empty());//begin()返回的迭代器 就指向第一个节点return *begin();}//const修饰的成员只能调用const修饰的成员函数const T front()const{assert(!empty());return *begin();}template class InputIteratorvoid assign(InputIterator first, InputIterator last){//先把数据现有的节点(除了头结点)都删除clear();//再循环把数据一个一个尾插进去while (first ! last){//尾插push_back(*first);first;}}void assign(size_t n, const T val){clear();for (int i 0; i n; i){push_back(val);}}void assign(int n, const T val){clear();for (int i 0; i n; i){push_back(val);}}iterator insert(iterator pos, const T val){//记录指向 pos 前一个节点的指针node* prev pos._n-_prev;//申请新节点的空间node* newnode new node;//存储数据newnode-_data val;newnode-_next pos._n;newnode-_prev prev;prev-_next newnode;pos._n-_prev newnode;//返回指向新插入的节点的迭代器//用于更新迭代器return newnode;}template class InputIteratorvoid insert(iterator pos, InputIterator first, InputIterator last){while (first!last){//循环插入即可//因为list的迭代器使用完insert之后 不会失效//所以不用接收返回值 也可以insert(pos,*first);first;}}void push_front(const T val){insert(begin(), val);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void resize(size_t n, const T val T()){//获取一下size加快后续比较效率//因为获取size()的时间复杂度为 O(N)size_t size this-size();if (n size){//缺失的数据用val填上//填到size()n为止while (size n){push_back(val);size;}}else {//把多出来的数据节点删除//删除到nsize()为止while (n size){pop_back();n;}}}void clear(){//[begin(),end())之间的数据//就是所有的有效数据(节点)//复用erase删除即可erase(begin(), end());}};
}
