个人网站设计与制作源代码,安卓apk开发,网站开发api平台,营销型网站知识STL---list 一、list 的介绍二、list 的模拟实现1. list 节点类2. list 迭代器类#xff08;1#xff09;前置#xff08;2#xff09;后置#xff08;3#xff09;前置- -、后置- -#xff08;4#xff09;! 和 运算符重载#xff08;5#xff09;* 解引用重载 和 … STL---list 一、list 的介绍二、list 的模拟实现1. list 节点类2. list 迭代器类1前置2后置3前置- -、后置- -4! 和 运算符重载5* 解引用重载 和 - 重载 3. list 类1迭代器2修改相关的接口swap()insert()erase()push_back、push_front、pop_back、pop_frontclear() 3空链表初始化4构造函数5拷贝构造函数6赋值运算符重载7析构函数 4. 打印容器的接口1打印链表整型的接口2打印 list 的接口3打印容器的接口 一、list 的介绍
list 是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。list 的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。list 与 forward_list 非常相似最主要的不同在于 forward_list 是单链表只能朝前迭代已让其更简单高效。与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。与其他序列式容器相比list 和 forward_list 最大的缺陷是不支持任意位置的随机访问比如要访问 list 的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list 还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大 list 来说这可能是一个重要的因素)。
二、list 的模拟实现
list 学习时也要学会查看文档list 文档介绍在实际中我们熟悉常见的接口就可以下面我们直接开始模拟实现在模拟实现中我们实现的是常见的接口并且会在实现中讲解它们的使用以及注意事项。
首先跟以往不一样的是list 是一个个节点连接起来的所以它不是连续的物理空间这也就意味着它不用扩容每次插入的时候只需要申请一个节点然后连接起来即可
其次list 底层的迭代器实现也跟 string和 vector 不一样它们两个的迭代器可以说是原生指针但是 list 的迭代器是要让节点指向下一个节点所以底层实现也不一样例如我们想让迭代器 it往后迭代就是 it但是底层的实现却不是真的让节点因为它们的空间不是连续的所以我们要把 list 迭代器封装成一个类。
首先我们先创建一个自己的命名空间把 list 节点的类list 迭代器的类list 类都放进去
1. list 节点类
list 节点类如下因为是双向链表所以应该有一个数据两个指针 namespace Young{// list 节点类template class Tstruct list_node{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T x T()):_data(x),_next(nullptr),_prev(nullptr){}};}2. list 迭代器类
首先我们先定义一个类模板其参数有三个分别是类型、类型的引用(const 和 非const) 、类型的指针(const 和 非const)
为什么要定义三个模板参数呢因为考虑到 const 迭代器const 迭代器和普通迭代器不是同一个类不能直接在 iterator 前直接加 const如 const iterator 这不是 const 迭代器因为这里的 const 修饰的是迭代器本身就是迭代器本身不能修改但是我们期望的是迭代器本身可以被修改如 it、it只是期望迭代器指向的内容不能被修改如 *it 10、it-10
这就类比 const T* 和 T* const const T* 中 const 是修饰指向的内容不能被修改而 T* const 中 const 修饰的是指针本身不能被修改而我们需要实现的 const 迭代器 是要满足第一种的所以 list 中普通迭代器和 const 迭代器 是两个完全不一样的类应该写成两个类但是我们可以通过增加两个模板参数 类型的引用(const 和 非const) 、类型的指针(const 和 非const) 来复用普通迭代器具体实现如下 // list 迭代器类template class T,class Ref,class Ptrstruct __list_iterator{typedef list_nodeT Node;typedef __list_iteratorT, Ref, Ptr self;Node* _node;// 迭代器构造函数__list_iterator(Node* node):_node(node){}}首先我们先将节点类起别名为 Node再将自己的类起别名为 self迭代器本身也是一个指针只是它内部实现不一样所以我们需要一个 _node 节点的指针构造函数实例化一个节点的指针比如说 listint::iterator it lt.begin();这里的 it 就会调构造函数实例化一个 lt.begin() 节点的指针其实 lt.begin() 就是指向头节点的指针。
接着我们重载一些迭代器常用的运算符
1前置
就是让迭代器往后迭代具体的实现就是让节点的指针指向下一个节点 // 前置 self operator(){_node _node-_next;return *this;}2后置
跟前置的区别就是后置需要拷贝返回以前的迭代器所以一般都不用后置 // 后置 self operator(int){self tmp(*this);_node _node-_next;return tmp;}3前置- -、后置- -
前置- -、后置- - 与 的区别就是 - -返回上一个节点的迭代器 // 前置 --self operator--(){_node _node-_prev;return *this;}// 后置--self operator--(int){self tmp(*this);_node _node-_prev;return tmp;}4! 和 运算符重载
! 运算符重载就是比较它们的节点是否相等 运算符就相反 // ! 运算符重载 iterator it ! lt.begin();bool operator!(const self s){return s._node ! _node;}// 运算符重载 iterator it lt.begin();bool operator(const self s) {return s._node _node;}5* 解引用重载 和 - 重载
解引用重载 和 - 重载 就是改变迭代器指向内容的两个运算符所以我们定义的三个模板参数就在这里起作用了比如我们实例化的模板参数是 const 迭代器 的 __list_iteratorT, const T, const T*这里的 const T 就是 Refconst T* 就是 Ptr这里就可以直接用 Ref 解引用重载和 Ptr箭头重载 作返回值
如果是 非const 迭代器的 __list_iteratorT, T, T*T 就是 RefT* 就是 Ptr所以就可以根据它们的类型返回对应的迭代器类型就不需要我们自己写两个迭代器的类了。 // * 解引用重载Ref operator*(){return _node-_data;}// - 重载Ptr operator-(){return _node-_data;}解引用 和 - 重载的使用
假设 list 里面存的类型是一个自定义类型这个自定义类型中有两个成员变量那么我们在使用 解引用 和 - 重载的时候应该访问哪一个呢这时候就需要我们指定访问了如下代码 struct AA{AA(int a1 0, int a2 0):_a1(a1), _a2(a2){}int _a1;int _a2;};void test4(){Young::listAA lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));Young::listAA::iterator it lt.begin();while (it ! lt.end()){// 使用解引用//cout (*it)._a1 (*it)._a2 endl;//使用 -cout it-_a1 it-_a2 endl;it;}cout endl;}上面的 cout it-_a1 it-_a2 endl; 调用了-重载实际上是 cout it.operator-()-_a1 it.operator-()-_a2 endl;本来应该是有两个 - 的即 it--_a1 但是这样写可读性不好所以编译器特殊处理省略了一个 -。
3. list 类
list 类首先将 const 迭代器和非 const 迭代器类型起别名为 const_iterator 和 iterator 成员变量有 _head 哨兵位节点和 _size 记录链表的长度如下 // list 类template class Tclass list{public:typedef list_nodeT Node;typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;private:Node* _head;size_t _size;};1迭代器
注意begin() 是哨兵位的下一个节点end() 是哨兵位节点。
begin() 和 end() 返回的类型也是一个迭代器这里 iterator(_head-_next) 是调用迭代器类的构造函数构造一个节点的指针返回也可以写成 _head-_next因为支持隐式类型的转换 // 非 const 迭代器iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}// const 迭代器const const_iterator begin() const{return const_iterator(_head-_next);}const const_iterator end() const{return const_iterator(_head);}2修改相关的接口
swap()
交换链表数据需要借助标准库的 swap 函数实现 // 交换链表数据void swap(listT lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}insert()
在 pos 迭代器插入节点新开一个节点然后插入指定迭代器的位置连接好 prev 和 cur 的位置即可因为 list 的底层结构为带头结点的双向循环链表因此在 list 中进行插入时是不会导致 list 的迭代器失效的 // 插入节点iterator insert(iterator pos, const T x){Node* newnode new Node(x);Node* cur pos._node;Node* prev cur-_prev;prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;return newnode;}erase()
删除 pos 迭代器位置的节点在删除时迭代器会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响所以 erase() 函数执行后it 所指向的节点已被删除因此 it 无效在下一次使用 it 时必须先给其赋值 // 删除节点iterator erase(iterator pos){Node* prev pos._node-_prev;Node* next pos._node-_next;prev-_next next;next-_prev prev;delete pos._node;pos._node-_next pos._node-_prev nullptr;--_size;return next;}push_back、push_front、pop_back、pop_front
只需要复用 insert() 和 erase() 即可实现如下 // 尾插void push_back(const T x){insert(end(), x);}// 头插void push_front(const T x){insert(begin(), x);}// 尾删void pop_back(){erase(--end());}// 头删void pop_front(){erase(begin());}clear()
清空链表数据删除除了哨兵位的节点即可 // 清空链表数据void clear(){iterator it begin();while (it ! end()){it erase(it);}} 以上修改接口配合迭代器的使用如下图 3空链表初始化 // 空链表初始化void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;_size 0;}4构造函数
构造函数只需要创建一个哨兵位即可 // 构造函数list(){empty_init();}5拷贝构造函数
拷贝构造函数直接初始化然后插入数据即可 // 拷贝构造函数 -- lt2(lt1)list(const listT lt){empty_init();for (auto e : lt){push_back(e);}}6赋值运算符重载
现代写法传参的时候调用拷贝构造然后交换数据即可 // 赋值运算符重载 -- lt2 lt1listT operator(listT lt){swap(lt);return *this;}7析构函数
清空链表数据之后再释放哨兵位的节点即可 // 析构函数~list(){clear();delete _head;_head nullptr;}4. 打印容器的接口
1打印链表整型的接口
像 vector、list 这些容器都没有重载流插入运算符所以我们可以自己实现一个打印的接口函数我们先来实现一下打印链表整型的接口 // 打印链表 -- 只能针对 int 类型void print_list(const listint lt){listint::const_iterator it lt.begin();while (it ! lt.end()){//*it 10; errorcout *it ;it;}cout endl;}此接口可以打印链表的数据但是只能针对 int 类型我们可以对它进行改造一下使用模板。
2打印 list 的接口
我们学了模板就可以利用模板实现泛型编程将类型改为模板的泛型即可打印 list 中的不同类型如下 // 打印链表 -- 只能打印 list 容器templatetypename Tvoid print_list(const listT lt){typename listT::const_iterator it lt.begin();while (it ! lt.end()){//*it 10; errorcout *it ;it;}cout endl;}这里的模板参数使用了 typedef 关键字这里必须使用 typedef 关键字而且在指定类域前还要加上 typedef 关键字如 typename listT::const_iterator it lt.begin();因为在模板还没有进行实例化的时候 const_iterator 就到 listT 的类域中寻找类型此时类中还没有实例化参数 T所以编译器分不清它是类型还是静态变量不能去 listT 里面找所以在前面加 typedef 关键字就说明它是个类型编译器在等 listT 实例化后再去类里面去取根据类型去取类型。
但是上面的接口还是不够完美要是我想打印 vector 呢那还是不能打印出来所以我们可以实现一个专门打印容器的接口
3打印容器的接口
我们使用模板参数代表容器让编译器到指定容器去取它的迭代器即可 // 打印容器 -- 能打印各种容器templatetypename containervoid print_container(const container con){typename container::const_iterator cit con.begin();while (cit ! con.end()){cout *cit ;cit;}cout endl;}使用如下图
文章转载自： http://www.morning.mslhq.cn.gov.cn.mslhq.cn http://www.morning.qkkmd.cn.gov.cn.qkkmd.cn http://www.morning.mlpch.cn.gov.cn.mlpch.cn http://www.morning.lwlnw.cn.gov.cn.lwlnw.cn http://www.morning.qmsbr.cn.gov.cn.qmsbr.cn http://www.morning.jpydf.cn.gov.cn.jpydf.cn http://www.morning.wclxm.cn.gov.cn.wclxm.cn http://www.morning.drmbh.cn.gov.cn.drmbh.cn http://www.morning.wnxqf.cn.gov.cn.wnxqf.cn http://www.morning.cnlmp.cn.gov.cn.cnlmp.cn http://www.morning.xltwg.cn.gov.cn.xltwg.cn http://www.morning.mqxrx.cn.gov.cn.mqxrx.cn http://www.morning.hhkzl.cn.gov.cn.hhkzl.cn http://www.morning.lhytw.cn.gov.cn.lhytw.cn http://www.morning.rqjxc.cn.gov.cn.rqjxc.cn http://www.morning.ztqj.cn.gov.cn.ztqj.cn http://www.morning.lffrh.cn.gov.cn.lffrh.cn http://www.morning.pnmnl.cn.gov.cn.pnmnl.cn http://www.morning.ykmkz.cn.gov.cn.ykmkz.cn http://www.morning.wzdjl.cn.gov.cn.wzdjl.cn http://www.morning.qmwzz.cn.gov.cn.qmwzz.cn http://www.morning.hwnnh.cn.gov.cn.hwnnh.cn http://www.morning.wjqbr.cn.gov.cn.wjqbr.cn http://www.morning.bssjp.cn.gov.cn.bssjp.cn http://www.morning.mfxcg.cn.gov.cn.mfxcg.cn http://www.morning.qtqjx.cn.gov.cn.qtqjx.cn http://www.morning.rngyq.cn.gov.cn.rngyq.cn http://www.morning.yggwn.cn.gov.cn.yggwn.cn http://www.morning.fjtnh.cn.gov.cn.fjtnh.cn http://www.morning.khpx.cn.gov.cn.khpx.cn http://www.morning.qrgfw.cn.gov.cn.qrgfw.cn http://www.morning.lgpzq.cn.gov.cn.lgpzq.cn http://www.morning.wnhml.cn.gov.cn.wnhml.cn http://www.morning.dbbcq.cn.gov.cn.dbbcq.cn http://www.morning.ranglue.com.gov.cn.ranglue.com http://www.morning.qdsmile.cn.gov.cn.qdsmile.cn http://www.morning.cbnlg.cn.gov.cn.cbnlg.cn http://www.morning.tmrjb.cn.gov.cn.tmrjb.cn http://www.morning.zrwlz.cn.gov.cn.zrwlz.cn http://www.morning.hxwrs.cn.gov.cn.hxwrs.cn http://www.morning.hcxhz.cn.gov.cn.hcxhz.cn http://www.morning.zdkzj.cn.gov.cn.zdkzj.cn http://www.morning.ttfh.cn.gov.cn.ttfh.cn http://www.morning.bxhch.cn.gov.cn.bxhch.cn http://www.morning.dcdhj.cn.gov.cn.dcdhj.cn http://www.morning.chrbp.cn.gov.cn.chrbp.cn http://www.morning.bwhcl.cn.gov.cn.bwhcl.cn http://www.morning.ffrys.cn.gov.cn.ffrys.cn http://www.morning.qczpf.cn.gov.cn.qczpf.cn http://www.morning.mdpcz.cn.gov.cn.mdpcz.cn http://www.morning.mstbbs.com.gov.cn.mstbbs.com http://www.morning.kwksj.cn.gov.cn.kwksj.cn http://www.morning.sggzr.cn.gov.cn.sggzr.cn http://www.morning.qnbzs.cn.gov.cn.qnbzs.cn http://www.morning.kzxlc.cn.gov.cn.kzxlc.cn http://www.morning.jgcxh.cn.gov.cn.jgcxh.cn http://www.morning.krqhw.cn.gov.cn.krqhw.cn http://www.morning.gassnw.com.gov.cn.gassnw.com http://www.morning.xkyqq.cn.gov.cn.xkyqq.cn http://www.morning.dcdhj.cn.gov.cn.dcdhj.cn http://www.morning.jqwpw.cn.gov.cn.jqwpw.cn http://www.morning.dfdhx.cn.gov.cn.dfdhx.cn http://www.morning.lqljj.cn.gov.cn.lqljj.cn http://www.morning.cykqg.cn.gov.cn.cykqg.cn http://www.morning.mzhgf.cn.gov.cn.mzhgf.cn http://www.morning.yrpd.cn.gov.cn.yrpd.cn http://www.morning.zlgth.cn.gov.cn.zlgth.cn http://www.morning.rgrz.cn.gov.cn.rgrz.cn http://www.morning.zffps.cn.gov.cn.zffps.cn http://www.morning.bxqry.cn.gov.cn.bxqry.cn http://www.morning.zdfrg.cn.gov.cn.zdfrg.cn http://www.morning.w58hje.cn.gov.cn.w58hje.cn http://www.morning.sypby.cn.gov.cn.sypby.cn http://www.morning.bkxnp.cn.gov.cn.bkxnp.cn http://www.morning.srgnd.cn.gov.cn.srgnd.cn http://www.morning.zdzgf.cn.gov.cn.zdzgf.cn http://www.morning.ryxdf.cn.gov.cn.ryxdf.cn http://www.morning.c7624.cn.gov.cn.c7624.cn http://www.morning.xbzfz.cn.gov.cn.xbzfz.cn http://www.morning.fgppj.cn.gov.cn.fgppj.cn
