建设网站平台滴滴车,设计感网站有哪些方面,云服务器有哪些,wordpress小程序直播文章目录 前言
一、List源码阅读
二、List常用接口模拟实现
1.定义一个list节点
2.实现一个迭代器
2.2const迭代器
3.定义一个链表#xff0c;以及实现链表的常用接口
三、List和Vector
总结 前言
本文中出现的模拟实现经过本地vs测试无误#xff0c;文件已上传gite… 文章目录 前言
一、List源码阅读
二、List常用接口模拟实现
1.定义一个list节点
2.实现一个迭代器
2.2const迭代器
3.定义一个链表以及实现链表的常用接口
三、List和Vector
总结 前言
本文中出现的模拟实现经过本地vs测试无误文件已上传gitee地址:list: 模仿实现stl的list - Gitee.com 一、List源码阅读 首先我们阅读源码阅读源码我按照如下方式先找到单个节点的定义再找到list里面的主要成员函数。 list_node链表节点的定义如下有三个成员prev,next指针数据域。 实现链表的接口增删改查回想我们用C语言实现的顺序表的时候使用指针去实现。使用C的时候模拟实现string也是使用迭代器。迭代器就是模拟指针的行为但是链表直接使用指针不一定能访问到下一个节点所以我们要封装一下原生指针--迭代器去实现对list的访问。 阅读源码_list_iterator这个迭代器有三个模板参数猜测T应该是类型Ref是引用Ptr是指针为什么有三个模板参数后续再分析。这个迭代器里实现了一个原生迭代器一个const迭代器const调用const对象然后还有一个self暂时不明白什么意思。继续往下。 阅读到这里重定义了一些参数。注意这里 typedef _list_nodeT * link_type; link_type node;_list_iterator(link type x):node(x){} 和C语言一样这里定义了一个节点的指针作为实现迭代器的最小单元 继续往下阅读这里有一些运算符重载的函数比较节点是否相等以及引用注意这里引用的返回值使用了reference上面看出来将Ref重定义成了reference所以这里可以猜测ref就是返回引用的值 这里实现了运算符重载函数使用迭代器去访问前后的节点。注意这里的返回值是self前面读到self就是_list_iterator的一个模板参数。对比之前实现日期类的时候日期类,返回的就是一个日期类对象。这里使用迭代器进行,猜测这里返回的就是一个迭代器。 继续查看迭代器的使用在list的成员函数中查看到begin指向头节点的下一个end指向头节点。rbegin指向头节点rend指向头节点的下一个。 判断链表是否为空判断头节点的下一个是否指向头节点 计算链表的size:根据begin,end去计算 以及链表中最重要的插入insert,通过迭代器找到pos的位置根据T去构建一个Node再进行插入。头插尾插都可以复用Insert。头插头删的时候先保留现在的指针指向情况再进行修改修改完了之后再删除这个节点 往下阅读到了list的主体部分有两个模板参数。alloc暂时不明白是什么 这里实现了一种创建节点的成员函数create_node通过T类型的参数x创建一个节点. empty_initialize 空的初始化只创建一个节点 二、List常用接口模拟实现
通过上面阅读源码我们来模仿实现list的一些常用接口。
1.定义一个list节点
templateclass T
struct list_node
{T _data;list_nodeT * _next;list_nodeT * _prev;
}
2.实现一个迭代器 迭代器要么就是原生指针要么就是自定义类型对原生指针的封装模拟指针的行为。 list用一个节点的指针去构造一个迭代器 templateclass T
struct _list_iterator
{typedef list_nodeT node;typedef _list_iteratorT self;//定义一个指针指向链表node * _node;//构造函数 用一个节点指针去构造迭代器_list_iterator(node * n):_node(n){}//实现迭代器的功能//指针向后遍历就如日期类返回的还是一个日期类对象;迭代器,返回一个迭代器对象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;}T operator*(){return _ndoe-data;}bool operator (const self s){return _node s._node;}bool operator !(const self s){return _node ! s._node;}
2.2const迭代器 假设我们传了一个const对象 void print_list(const listintlt)。对象的类型是一个const listint * 调用不了普通迭代器,是一个经典的权限放大所以我们要对this加一个const。此时变成了const* _head,指针本身不能改变但是指向的内容可以改变。即我们还是可以对对象进行改变。在stl库中它使用const修饰*this,返回值也是一个const_iterator。但是对于所有的成员函数都使用const修饰*this和返回值类型很冗余所以我们这里增加了一个模板参数class Ref。 templateclass Tstruct __list_const_iterator{typedef list_nodeT node;typedef __list_const_iteratorT self;node* _node;__list_const_iterator(node* n):_node(n){}//保护返回的值不能被修改const T operator*(){return _node-_data;}//... 其他成员函数都相同};templateclass T,class Ref, class Ptrstruct _list_iterator
{typedef list_nodeT node;typedef _list_iteratorT,Ref,Ptr self;node * _node;_list_iterator(node * n):_node(n){}Ref operator*(){return _ndoe-data;}//注意这里 如果我定义了一个AA类型的链表通过迭代器去访问,指针类型为AA*// 现在要访问它的成员 可以这样 *(it)._a1; //也可以it--a1 一个是运算符重载调用it是自定义类型无法直接使用箭头it- 就相当于运算符重载operator- AA*//一个是找成员 //这里为了增强可读性 省略了一个箭头 it-_a1;Ptr operator-(){return _node-data;}self operator--(){}//其余运算符操作类似
}templateclass T
class list
{//注意这里模板参数 调用普通迭代器 T传给ref, 调用const迭代器 const T 传给ref typedef _list_iteratorT,T,T* iterator;typedef _list_iteratorT,const T, const T* const_iterator;iterator begin(){return iterator(_head-_next);}const iterator begin(){return const_iterator(_head-_next);}//..其余类似
}
3.定义一个链表以及实现链表的常用接口
templateclass T
struct _list
{typedef list_nodeT node;typedef _list_iteratorT iterator;//list的成员node* _head;//list的构造 初始只有一个头节点list(){_head new node;_head-_next _head;_head-_prev _head;}//list的一些成员函数 //通过迭代器定位begin和enditerator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}//通过迭代器对指定pos位置进行增删改查void insert(iterator pos, const T x){node new_node new node(x);//iterator cur pos;//这里是要通过pos的指针找到这个节点 对pos进行解引用node * cur pos._node;node * prev cur-_prev;prev-_next new_node;new_node-_prev prev;new_node-_next cur;cur-_prev new_node;}void push_back(){insert(end(),x);}void push_front(){insert(begin(),x);}void 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;}void pop_back(){erase(end());}void pop_front(){erase(begin());}//打印void print_list(const listT lt){iterator it lt.begin();while(it ! lt.end()){cout*it;it;}coutendl;}}
三、List和Vector对比 vector与list都是stl中非常重要的序列容器由于两个容器的底层结构不同导致特性以及应用场景不同 vectorlist底层结构动态顺序表一段连续的空间带头节点的双向循环链表随机访问支持随机访问访问某个元素效率O(1不支持随机访问访问某个元素效率O(N)插入和删除在任意位置插入删除元素效率较低时间复杂度O(N),插入可能需要扩容开辟新空间拷贝元素释放旧空间任意位置插入和删除效率高不需要搬移元素。时间复杂度O(1)空间利用率底层为连续空间不容易造成内存碎片空间利用率高缓存利用率高底层节点动态开辟小节点容易造成内存碎片空间利用率低缓存利用率低迭代器原生指针对原生指针节点指针进行封装迭代器失效在插入元素时要给所有的迭代器重新赋值因为插入元素有可能导致扩容导致原来迭代器失效删除时也可能失效。需要重新给迭代器赋值插入元素不会导致迭代器失效删除元素时只会导致当前迭代器失效因为那个节点已经被删除。其他迭代器不受影响使用场景需要高效存储支持随机访问不关心插入删除效率大量插入和删除操作不关心随机访问 总结
本文主要对stl源码中list内容进行阅读并模拟实现。技术有限如有错误请指正。
