免费做试用的网站,汕头网站推广系统,网络优化中是什么意思,何使网站的页面结构更为合理建前言#xff1a;在前面学习了STL中list的使用方法#xff0c;现在我们就进一步的讲解List的一些基本功能的模拟实现#xff0c;这一讲博主认为是最近比较难的一个地方#xff0c;各位一起加油。 #x1f496; 博主CSDN主页:卫卫卫的个人主页 #x1f49e; #x1f449; …前言在前面学习了STL中list的使用方法现在我们就进一步的讲解List的一些基本功能的模拟实现这一讲博主认为是最近比较难的一个地方各位一起加油。 博主CSDN主页:卫卫卫的个人主页 专栏分类:高质量学习 代码仓库:卫卫周大胖的学习日记 关注博主和博主一起学习!一起努力 目录标题 List的模拟实现List三个基本类结点类接口的实现list的正向迭代器类的实现 List正向迭代器的接口实现构造函数operator*运算符重载operator-运算符重载operator前置和--与后置和--operator与operator! List类的接口的实现构造函数begin()和end(尾插函数- push_back(const T x)insert(iterator pos, const T val)插入pos之前的位置push_front(const T x)头插iterator erase(iterator pos)删除pos位置的值尾删与头删clear()清空listsize_t size() 查看链表元素bool empty()查看链表元素是否为空拷贝构造函数析构函数swap函数 交换链表中的元素operator运算符重载 整体代码 List的模拟实现
List三个基本类 前面我们提到过,list本质上就是一个带头双向循环链表这里我们要实现list的功能就要实现三个类 模拟实现结点类模拟实现迭代器的类模拟list主要功能的类 结点类接口的实现
这里如果对带头双向链表不太熟悉的小伙伴可以去看看博主之前的文章带头双向循环链表
template class T
struct ListNode//链表的主体
{ListNodeT* _prev;//C中可不写struct直接用名定义ListNodeT* _next;T _data;//存节点的值ListNode(const T x T())//这个地方在讲模拟实现vector的时候也讲了需要查看的可以看看之前的博客:_next(nullptr), _prev(nullptr), _data(x){}
};看到这里很多小伙伴会有疑问为什么这里写的是ListNode* 在C中是可以省略struct不写的也就是说原本的样子应该是 struct ListNode * _prev结构体模板或类模板在定义时可以不加 T但 使用时必须加T list的正向迭代器类的实现
templateclass T, class Ref, class Ptr
struct ListIterator//迭代器
{typedef ListNodeT Node;typedef ListIteratorT, Ref, Ptr Self;//T表示基本类型, Ref表示引用返回Ptr指代指针返回Node* _node;//记录链表ListIterator(Node* node)//传过来的位置就是迭代器从哪个位置开始
}这里大部分人会有因为为什么这里迭代器的模板会有三个参数?因为如果我们只是使用普通迭代器的话确实一个参数就够了但是有的情况我们是需要使用const迭代器的难道我们还要在写一个类来专门放 const类型的迭代器嘛 而后文list类的模拟实现中我对迭代器进行了两种typedef 普通迭代器typedef ListIteratorT, T, T* iterator; const迭代器:typedef ListIteratorT, const T, const T* const_iterator; List正向迭代器的接口实现
构造函数
这里我们通过传过来的结点完成构造让迭代器指向传过来结点的位置即可
ListIterator(Node* node)//传过来的位置就是迭代器从哪个位置开始:_node(node)
{
}operator*运算符重载
前面我们说到过,Ref本质就是引用返回无非就是const还是非const的类型的区分
Ref operator*()
{return _node-_data;
}operator-运算符重载
至于为什么要写-的运算符重载就是我们在list的使用的过程中传过去的不一定就是内置类型还有可能是自定义类型(如下所示)
struct A
{int _a1;int _a2;A(int a1 0, int a2 0):_a1(a1), _a2(a2){}
};
void test_list2()
{listA lt;A aa1(1, 1);A aa2 { 1, 1 };lt.push_back(aa1);lt.push_back(aa2);lt.push_back(A(2, 2));lt.push_back({ 3, 3 });lt.push_back({ 4, 4 });listA::iterator it lt.begin();while (it ! lt.end()){cout it-_a1 : it-_a2 endl;//本质上编译器会省略一个-,所以实际上写的是it-_A-_a1cout it.operator-()-_a1 : it.operator-()-_a2 endl;it;}cout endl;
}Ptr operator-()//本质上就是重载自定义类型帮你找到内置类型然后再找到内置类型的数据
{return _node-_data;
}operator前置和–与后置和–
这里我们提一下对于前置和后置还有–等我们主要传一个int类型的数据来进行区分
Self operator()//前置
{_node _node-_next;return *this;
}Self operator(int)//后置加上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;
}operator与operator!
代码思路对于如何判断两个迭代器是否相等我们只需要判断两个迭代器所指向的位置是否相等即可。
bool operator ! (const Self it)
{return _node ! it._node;
}bool operator (const Self it)
{return _node it._node;
}List类的接口的实现
代码思路:这里我们主要是通过两个迭代器帮助我们去遍历list,然后一个const迭代器是只读的作用一个非const迭代器是即可读又可写的作用
template class T
class list//链表
{typedef ListNodeT Node;
public:typedef ListIteratorT, T, T* iterator;//正向迭代器typedef ListIteratorT, const T, const T* const_iterator;//const迭代器
private:Node* _head;size_t _size;//记录链表元素个数
};构造函数
这里我们就采用双向带头链表的思路初始化的时候让其的前驱指针和next指向他的哨兵位即可。
void empty_init()
{_head new Node;_head-_next _head;_head-_prev _head;_size 0;
}
list()//默认构造
{empty_init();
}begin()和end(
iterator begin()//begin应该是哨兵位的下一个结点
{return _head-_next;
}
iterator end()//因为是带头双向链表所以通常没有尾部的这个说法一般结束的时候就是在哨兵位这个结点就是尾结点
{return _head;
}const_iterator begin()const//只读的版本
{return _head-_next;
}const_iterator end() const
{return _head;
}尾插函数- push_back(const T x)
关于尾插这部分的内容我们在之前数据结构那部分讲的挺详细的不懂的话可以看看博主之前的博客。
void push_back(const T x)//尾插
{//insert(end(), x);Node* tail _head-_prev;//找尾Node* newnode new Node(x);//创建一个新的结点tail-_next newnode;newnode-_prev tail;//使newnode和头结点_head构成循环newnode-_next _head;
}insert(iterator pos, const T val)插入pos之前的位置
这里我们会发现使用insert会改变了底层会导致迭代器失效所以使用的时候要及时更新迭代器。
void insert(iterator pos, const T val)//插入
{Node* cur pos._node;//找到当前结点的链表Node* newnode new Node(val);Node* prev cur-_prev;prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;
}push_front(const T x)头插
这里我们可以顺带把尾插也给优化一下
void push_front(const T x)//头插
{insert(begin(), x);
}
void push_back(const T x)//尾插
{insert(end(), x);
}iterator erase(iterator pos)删除pos位置的值
这里我们也需要注意的是删除和插入数据都会导致迭代器失效因此我们需要及时的更新迭代器
iterator erase(iterator pos)//删除会导致迭代器失效故因此要返回迭代器的下一个位置
{assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;_size--;return iterator(next);
}尾删与头删
void pop_back()//尾删
{erase(end() - 1);
}void pop_front()
{erase(begin());
}clear()清空list
void clear()
{iterator it begin();//通过迭代器依次遍历清除while (it ! end()){it erase(it);}
}size_t size() 查看链表元素
size_t size() const
{return _size;
}bool empty()查看链表元素是否为空
bool empty()
{return _size 0;
}拷贝构造函数
代码思路我们只需要对链表的元素依次尾插到新的链表中即可
list(const listT lt)
{empty_init();for (auto e : lt){push_back(e);}
}析构函数
~list()//析构
{clear();delete _head;_head nullptr;
}swap函数 交换链表中的元素
void swap(listT it)//it要被修改
{std::swap(_head, it._head);std::swap(_size, it._size);
}operator运算符重载
listT operator(listT it)
{swap(*this,it);return *this;
}整体代码
#includeiostream
#include assert.h
using namespace std;namespace bit
{template class Tstruct ListNode//链表的主体{ListNode* _prev;//C中可不写struct直接用名定义ListNode* _next;T _data;ListNode(const T x T()):_next(nullptr), _prev(nullptr), _data(x){}};templateclass T, class Ref, class Ptrstruct ListIterator//迭代器{typedef ListNodeT Node;typedef ListIteratorT, Ref, Ptr Self;//T表示基本类型, Ref表示引用返回Ptr指代指针返回Node* _node;//记录链表ListIterator(Node* node)//传过来的位置就是迭代器从哪个位置开始:_node(node){}Ref operator*(){return _node-_data;}// listint::ListIterator it; it-data;//listData::ListIterator it; it-Data-data;Ptr 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;}};template class Tclass list//链表{typedef ListNodeT Node;public:typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, 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;_size 0;}list()//默认构造{empty_init();}// lt2(lt1)list(const listT lt){empty_init();for (auto e : lt){push_back(e);}}~list()//析构{clear();delete _head;_head nullptr;}void swap(listT it)//it要被修改{std::swap(_head, it._head);std::swap(_size, it._size);}listT operator(listT it){swap(*this,it);return *this;}void push_back(const T x)//尾插{//insert(end(), x);Node* tail _head-_prev;//找尾Node* newnode new Node(x);//创建一个新的结点tail-_next newnode;newnode-_prev tail;//使newnode和头结点_head构成循环newnode-_next _head;}void push_front(const T x)//头插{insert(begin(), x);}void insert(iterator pos, const T val)//插入{Node* cur pos._node;//找到当前结点的链表Node* newnode new Node(val);Node* prev cur-_prev;prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;}iterator erase(iterator pos)//删除会导致迭代器失效故因此要返回迭代器的下一个位置{assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;_size--;return iterator(next);}void pop_back()//尾删{erase(end() - 1);}void pop_front(){erase(begin());}size_t size() const{return _size;}bool empty(){return _size 0;}void clear(){iterator it begin();while (it ! end()){it erase(it);}}private:Node* _head;size_t _size;};好啦今天的内容就到这里啦下期内容预告stl中stack和queue的使用与模拟实现. 结语今天的内容就到这里吧谢谢各位的观看如果有讲的不好的地方也请各位多多指出作者每一条评论都会读的谢谢各位。 ️ 这里祝各位接下来的每一天好运连连
文章转载自： http://www.morning.knngw.cn.gov.cn.knngw.cn http://www.morning.ljbch.cn.gov.cn.ljbch.cn http://www.morning.wfspn.cn.gov.cn.wfspn.cn http://www.morning.cmfkp.cn.gov.cn.cmfkp.cn http://www.morning.yxgqr.cn.gov.cn.yxgqr.cn http://www.morning.clccg.cn.gov.cn.clccg.cn http://www.morning.fnlnp.cn.gov.cn.fnlnp.cn http://www.morning.mjbnp.cn.gov.cn.mjbnp.cn http://www.morning.bdkhl.cn.gov.cn.bdkhl.cn http://www.morning.mqghs.cn.gov.cn.mqghs.cn http://www.morning.rqnhf.cn.gov.cn.rqnhf.cn http://www.morning.ghrlx.cn.gov.cn.ghrlx.cn http://www.morning.rbkml.cn.gov.cn.rbkml.cn http://www.morning.psqs.cn.gov.cn.psqs.cn http://www.morning.bjjrtcsl.com.gov.cn.bjjrtcsl.com http://www.morning.jtkfm.cn.gov.cn.jtkfm.cn http://www.morning.fhrgk.cn.gov.cn.fhrgk.cn http://www.morning.qlry.cn.gov.cn.qlry.cn http://www.morning.hxsdh.cn.gov.cn.hxsdh.cn http://www.morning.tkqzr.cn.gov.cn.tkqzr.cn http://www.morning.cyyhy.cn.gov.cn.cyyhy.cn http://www.morning.rqgq.cn.gov.cn.rqgq.cn http://www.morning.ndlww.cn.gov.cn.ndlww.cn http://www.morning.lwmzp.cn.gov.cn.lwmzp.cn http://www.morning.bpmnc.cn.gov.cn.bpmnc.cn http://www.morning.wnqfz.cn.gov.cn.wnqfz.cn http://www.morning.lxkhx.cn.gov.cn.lxkhx.cn http://www.morning.frpb.cn.gov.cn.frpb.cn http://www.morning.blznh.cn.gov.cn.blznh.cn http://www.morning.smdnl.cn.gov.cn.smdnl.cn http://www.morning.tmbtm.cn.gov.cn.tmbtm.cn http://www.morning.cgntj.cn.gov.cn.cgntj.cn http://www.morning.mkrqh.cn.gov.cn.mkrqh.cn http://www.morning.kbdjn.cn.gov.cn.kbdjn.cn http://www.morning.tmxfn.cn.gov.cn.tmxfn.cn http://www.morning.fbjqq.cn.gov.cn.fbjqq.cn http://www.morning.wgtnz.cn.gov.cn.wgtnz.cn http://www.morning.mgbcf.cn.gov.cn.mgbcf.cn http://www.morning.jlschmy.com.gov.cn.jlschmy.com http://www.morning.smxyw.cn.gov.cn.smxyw.cn http://www.morning.cwwts.cn.gov.cn.cwwts.cn http://www.morning.sbwr.cn.gov.cn.sbwr.cn http://www.morning.hclqy.cn.gov.cn.hclqy.cn http://www.morning.qlck.cn.gov.cn.qlck.cn http://www.morning.wbxr.cn.gov.cn.wbxr.cn http://www.morning.msxhb.cn.gov.cn.msxhb.cn http://www.morning.wbhzr.cn.gov.cn.wbhzr.cn http://www.morning.dsprl.cn.gov.cn.dsprl.cn http://www.morning.hqbk.cn.gov.cn.hqbk.cn http://www.morning.cgntj.cn.gov.cn.cgntj.cn http://www.morning.yxbdl.cn.gov.cn.yxbdl.cn http://www.morning.zrlms.cn.gov.cn.zrlms.cn http://www.morning.tlpgp.cn.gov.cn.tlpgp.cn http://www.morning.jwxmn.cn.gov.cn.jwxmn.cn http://www.morning.hnrdtz.com.gov.cn.hnrdtz.com http://www.morning.lbcfj.cn.gov.cn.lbcfj.cn http://www.morning.pznqt.cn.gov.cn.pznqt.cn http://www.morning.rrwgh.cn.gov.cn.rrwgh.cn http://www.morning.supera.com.cn.gov.cn.supera.com.cn http://www.morning.zztmk.cn.gov.cn.zztmk.cn http://www.morning.lbjdx.cn.gov.cn.lbjdx.cn http://www.morning.rgrdd.cn.gov.cn.rgrdd.cn http://www.morning.zpzys.cn.gov.cn.zpzys.cn http://www.morning.cttgj.cn.gov.cn.cttgj.cn http://www.morning.pqqhl.cn.gov.cn.pqqhl.cn http://www.morning.wyrkp.cn.gov.cn.wyrkp.cn http://www.morning.qrsm.cn.gov.cn.qrsm.cn http://www.morning.hrdx.cn.gov.cn.hrdx.cn http://www.morning.kphsp.cn.gov.cn.kphsp.cn http://www.morning.tdqhs.cn.gov.cn.tdqhs.cn http://www.morning.nzfyx.cn.gov.cn.nzfyx.cn http://www.morning.rggky.cn.gov.cn.rggky.cn http://www.morning.tnbsh.cn.gov.cn.tnbsh.cn http://www.morning.fylsz.cn.gov.cn.fylsz.cn http://www.morning.qpqwb.cn.gov.cn.qpqwb.cn http://www.morning.wtcbl.cn.gov.cn.wtcbl.cn http://www.morning.sbrrf.cn.gov.cn.sbrrf.cn http://www.morning.ydrn.cn.gov.cn.ydrn.cn http://www.morning.sskhm.cn.gov.cn.sskhm.cn http://www.morning.kqbjy.cn.gov.cn.kqbjy.cn
