开源外贸网站,微信推广广告在哪里做,html网站免费模板下载,湛江本地做网站前言#xff1a;这篇文章我们继续进行C容器类的分享——list#xff0c;也就是数据结构中的链表#xff0c;而且是带头双向循环链表。 一.基本框架
namespace Mylist
{templateclass T//定义节点struct ListNode{ListNodeT* _next;ListNodeT* _pre…前言这篇文章我们继续进行C容器类的分享——list也就是数据结构中的链表而且是带头双向循环链表。 一.基本框架
namespace Mylist
{templateclass T//定义节点struct ListNode{ListNodeT* _next;ListNodeT* _prev;T _data;ListNode(const T x T()):_next(nullptr) ,_prev(nullptr),_data(x){}};templateclass Tclass list{typedef ListNodeT Node;public://构造函数list(){_head new Node;_head-_next _head;_head-_prev _head;}//析构函数~list(){iterator it begin();while (it ! end()){it erase(it);}delete _head;_head nullptr;}//数据个数size_t size(){iterator it begin();size_t Size 0;while (it ! end()){Size;it;}return Size;}private:Node* _head;};
}
由于要满足存储任意类型的数据所以我们必须要使用模版来进行定义。 迭代器
关于list类中的最难之处就是迭代器了。
因为迭代器的原理即为指针对于string和vector这种创建的对象的物理空间是连续的类来说我们可以直接对迭代器进行“”、“--”等数学运算。
而对于本质为链表的list来说由于每个节点的物理空间都是随机创建各个节点的地址并不连续所以我们没法直接进行迭代器的数学运算而需要对迭代器的各种功能进行重新定义所以我们创建一个专门为迭代器服务的类 //迭代器templateclass Tstruct ListIterator{typedef ListNodeT Node;typedef ListIteratorT Self;ListIterator(Node* node):_node(node){}//解引用T operator*(){return _node-_data;}//前置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){return _node ! it._node;}//相等bool operator(const Self it){return _node it._node;}Node* _node;};
随后在list类中将该类名重定义为iterator便可正常使用迭代器了 typedef ListIteratorT iterator;iterator begin(){return _head-_next;}iterator end(){return _head;} 这里值得注意的是因为是带头双向循环链表所以链表的开始即哨兵位的下一个而结尾就是哨兵位。 但是现在的迭代器是存在问题的它并不能实现对const修饰的数据的操作所以我们还需要一个const迭代器。因为我们的普通迭代器就是用模版来实现的所以这里可以直接通过模版来实现const迭代器 //迭代器templateclass T,class Refstruct ListIterator{typedef ListNodeT Node;typedef ListIteratorT,Ref Self;//构造函数ListIterator(Node* node):_node(node){}//解引用Ref operator*(){return _node-_data;}//前置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){return _node ! it._node;}//相等bool operator(const Self it){return _node it._node;}Node* _node;}; typedef ListIteratorTT iterator;typedef ListIteratorT,const T const_iterator;
这里有一个细节因为T同时还要服务于Node类所以不能直接对其进行修改而是另用一个模版参数。 因为const对象与非const对象最大的不同之处在于对数据的访问所以定义一个名为Ref引用的模版参数来对解引用运算符重载函数进行改造。 二.常用操作
1.插入
先来看任意位置的插入需要传入某个位置的指针pos //pos前插入void insert(iterator pos, const T val){Node* cur pos._node;Node* newnode new Node(val);Node* prev cur-_prev;prev-_next newnode;newnode-_next cur;cur-_prev newnode;newnode-_prev prev;} 现在对于我们来说就是非常简单测试如下 这里有一个小细节如果我们插入的位置是第一个节点之前由于it迭代器的指向并未改变所以如果进行遍历他就不会遍历出我们新插入的数据所以需要更新一下it。 有了pos位置的插入之后就可以用它来扩展头插和尾插 //尾插void push_back(const T x){insert(end(), x);}//头插void push_front(const T x){insert(begin, x);} 2.删除
我们同样先写出pos位置的删除 //pos删除iterator erase(iterator pos){Node* cur pos._node;Node* next cur-_next;Node* prev cur-_prev;next-_prev prev;prev-_next next;delete cur;return iterator(next);}
由于删除会导致迭代器成为野指针所以我们要对其进行更新 测试如下 同样由其扩展出头删和尾删 //头删void pop_front(){erase(begin());}//尾删void pop_back(){erase(--end());} 3.拷贝
和string和vector一样list的拷贝也需要使用深拷贝那么它的拷贝构造函数该怎么写
同样是要开辟新的空间需要一个自己的头结点随后按照被拷贝的链表的数据进行尾插即可 //拷贝构造list(const listT lt){_head new Node;_head-_next _head;_head-_prev _head;for (auto e : lt){push_back(e);}}
测试如下 此外还有“”运算符重载的方法 //交换void swap(listT it){std::swap(_head, it._head);}//运算符重载listT operator(listT lt){swap(lt);return *this;}
这里仍然是巧妙的运用swap函数因为lt是一个临时拷贝有自己的空间和地址所以直接让两者进行交换lt在退出函数时即被销毁而拷贝者则继承了它的地址空间测试如下 总结
关于list类的基本知识就分享到这里啦。
因为与string和vector都存在很多相似之处所以建议将这三者放在一起学习。
喜欢本篇文章记得一键三连下期再见
