哪些网站做舆情分析,中国网站访问量排行,建e网室内设计网官网vr全景,常德seo优化list的模拟真的很震撼#xff0c;第一次学习时给我幼小的心灵留下了极大地冲击 接下来我们一起看看list模拟究竟是怎样一回事 目录 节点的封装#xff1a;list类的实现#xff1a;私有成员变量#xff1a;构造函数#xff1a;push_back pop_back: 迭代器类的实…list的模拟真的很震撼第一次学习时给我幼小的心灵留下了极大地冲击 接下来我们一起看看list模拟究竟是怎样一回事 目录 节点的封装list类的实现私有成员变量构造函数push_back pop_back: 迭代器类的实现begin end不可被const对象调用begin end可被const对象调用 继续list类的实现insert erase:带参构造函数迭代器区间构造拷贝构造赋值运算符重载析构函数 节点的封装
我们在之前没用CPP实现list时是定义了一个struct node的结构体
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;那我们现在当然也需要定义一个结构体 templateclass Tstruct list_node{T _val;list_nodeT* _prev;list_nodeT* _next;list_node(const T data T()){_val data;_prev _next nullptr;}};但是要写一个默认构造函数因为未来我们会new节点就像我们在C阶段malloc的一样。
那么为什么要使用sruct而不是class呢因为我们希望这个节点结构体有了他的地址可以直接访问成员变量而设置为class时除非进行public否则不是很方便。
list类的实现
私有成员变量
由于我们会使用模版因此在写类型是比较不方便于是可以define一下typedef list_nodeT node; private:node* _head;注意我们的stl库中的list是有哨兵位的故私有成员设为_head。
构造函数 list(){empty_init();}为什么要先写个空初始化呢因为后边的成员函数有一些也需要进行初始化因此写成一个函数进行复用。 void empty_init(){_head new node();_head-_next _head;_head-_prev _head;}push_back pop_back:
我们先搭一个架子出来随后在进行细节的填补。
push_back() void push_back(const T val){node* newnode new node(val);node* tail _head-_prev;tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;}pop_back void pop_back(){node* prev (it._node)-_prev;node* next (it._node)-_next;delete it._node;prev-_next next;next-_prev prev;}有了节点之后我们怎样进行访问 没错就是使用迭代器。
迭代器类的实现
我们的list的迭代器为什么要封装成一个类 因为在vector那种底层虚拟地址是连续的当我们有一个指定位置的指针直接对指针进行、--、*…都是没问题的因为我们的迭代器本质就是一个模仿指针行为的一个东西
但是我们的链表节点的底层并不是连续的是一个一个new出来的并不能保证底层虚拟地址的连续性所以要对链表节点的指针进行封装进行重载操作符进而可以模拟指针的行为 templateclass Tstruct list_iterator{typedef list_nodeT node;typedef list_iteratorT self;node* _node;list_iterator(node* Node){_node Node;}self operator(){_node _node-_next;return *this;}self operator--(int){self tmp *this;_node _node-_prev;return tmp;}self operator--(){_node _node-_prev;return *this;}self operator(int){self tmp *this;_node _node-_next;return tmp;}bool operator!(self it){return it._node ! _node;}T operator*(){return _node-_val;}};
对需要进行相关运算符重载的都进行一遍。
如此我们一个最简单的list框架就已经搭建成功了。 不要忘记在list类中进行将list_iteratortypedef为iterator因为这样我们的代码才具有跨平台性。
同时要在list类中写上begin与end这两个获取迭代器的函数。
begin end不可被const对象调用 iterator begin(){return _head-_next;}iterator end(){return _head;}我们为啥可以这么写_head的类型不是node*原生的类型显示为list_nodeT*可是迭代器的类型是list_iterator 完全不一样啊这是因为我们C支持单参数的构造函数隐式类型转换直接对_head这个指针利用iterator的构造函数构造成迭代器
但是我们这个list目前对于const对象是很难遍历的所以当然要实现const迭代器。
我们有两种方式第一种是将普通迭代器的复制一份改为const迭代器对*这个操作符重载返回const对象这样就不怕const对象被修改了。
但是这样的代码是在是冗余不要忘记我们还有模版的存在 我们如果将迭代器的模版参数多设计一个T的引用在list类中将这个迭代器类进行typedef
typedef list_iteratorT, T iterator;
typedef list_iteratorT, const T const_iterator;那么我们这样就可以很好解决当前代码重复度高比较冗余的缺点。 templateclass T, class Ref//多传递的模版参数struct list_iterator{typedef list_nodeT node;typedef list_iteratorT, Ref self;node* _node;list_iterator(node* Node){_node Node;}self operator(){_node _node-_next;return *this;}self operator--(int){self tmp *this;_node _node-_prev;return tmp;}self operator--(){_node _node-_prev;return *this;}self operator(int){self tmp *this;_node _node-_next;return tmp;}bool operator!(self it){return it._node ! _node;}Ref operator*(){return _node-_val;}};这样就可以根据是否为const对象而生成不同的迭代器类了
begin end可被const对象调用 iterator begin(){return _head-_next;}iterator end(){return _head;}const_iterator begin() const{return _head-_next;}const_iterator end() const{return _head;}继续list类的实现
有了迭代器我们就可以写inserterase等等函数进而对push_back/front…等等函数的复用
insert erase: void insert(iterator pos, const T val){node* newnode new node(val);node* prev pos._node-_prev;node* cur pos._node;prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;}iterator erase(iterator pos){node* prev pos._node-_prev;node* next pos._node-_next;delete pos._node;prev-_next next;next-_prev prev;return next;}带参构造函数 list(int n, const T val T()){empty_init();while (n--){push_back(val);}}直接复用push_back
迭代器区间构造 template class Iteratorlist(Iterator first, Iterator last){empty_init();while (first ! last){push_back(*first);first;}}拷贝构造 list(const listT lt){empty_init();listT::const_iterator it lt.begin();while (it ! lt.end()){push_back(*it);it;}}赋值运算符重载 void swap(listT lt){std::swap(_head, lt._head);}listT operator(listT lt){swap(lt);return *this;}析构函数 ~list(){clear();delete _head;}void clear(){iterator it begin();while (it ! end()){it erase(it);}}由此list类就模拟完毕如果有不明白的地方可以尽管来找博主
