社群电商的运营模式,sem优化是什么,太阳宫网站建设,早晨设计 做网站设计吗目录
一、模拟实现list
1、list的基本结构
2、迭代器封装
2.1 正向迭代器
2.2 反向迭代器
3、指定位置插入
4、指定位置删除
5、结语 前言#xff1a; list是STL(标准模板库)中的八大容器之一#xff0c;而STL属于C标准库的一部分#xff0c;因此在C中可以直接使用…目录
一、模拟实现list
1、list的基本结构
2、迭代器封装
2.1 正向迭代器
2.2 反向迭代器
3、指定位置插入
4、指定位置删除
5、结语 前言 list是STL(标准模板库)中的八大容器之一而STL属于C标准库的一部分因此在C中可以直接使用list容器存储数据。list实质上是一个带头双向循环链表这也使得他能够在常数的时间复杂度范围内插入和删除数据缺点是不能像数组那样进行元素下标的随机访问。 一、模拟实现list 在C中可以直接调用库里的list并且使用起来非常的简便和使用vector、string相差无几但是为了能够更好的了解list和其底层原理下文会对lsit的常用接口进行模拟实现以便对list有更深入的理解并且list的底层实现逻辑完美的表现了面向对象的思想。
1、list的基本结构 与实现vector和string不一样list可以分成两个整体链表本身、节点本身因此需要两个类链表类、节点类完成list的基本实现并且把节点类看作是一个普通的节点而实现链表的具体功能函数都放在链表类中。 list基本功能代码如下
#define _CRT_SECURE_NO_WARNINGS 1#includeiostream
using namespace std;namespace ZH
{template class Tstruct list_node//节点类{list_nodeT* prev;list_nodeT* next;T val;list_node(const T t):prev(nullptr), next(nullptr), val(t){}};template class Tclass list//链表类{public:typedef list_nodeT node;//让节点类看起来像一个普通的节点list()//构造函数、目的是创建哨兵位头节点:_node(new node(-1)){_node-next _node;_node-prev _node;}void push_front(const T t)//头插{node* newnode new node(t);node* cur _node-next;_node-next newnode;newnode-prev _node;newnode-next cur;cur-prev newnode;}void Print()//打印数据{node* cur _node-next;while (cur ! _node){cout cur-val ;cur cur-next;}}~list()//析构{node* cur _node-next;node* dest cur-next;while (cur ! _node){delete cur;cur dest;dest dest-next;}delete _node;_node nullptr;}private:node* _node;};
}int main()
{ZH::listint lt;lt.push_front(1);lt.push_front(2);lt.push_front(3);lt.push_front(4);lt.Print();return 0;
} 运行结果 从上面的代码可以发现 list的底层实现和之前c语言中实现双向循环链表的逻辑一模一样只不过用C的方式将其进行了封装。 这里节点类里的成员变量要放在公有域struct定义类默认为公有域因为在list中会改变节点前后指针的指向因此节点的指针要设为外部可见。
2、迭代器封装
2.1 正向迭代器 在调用库里面的list会发现库里面list的迭代器用起来像是一个指针因为可以对迭代器进行解引用操作以及操作。所以在模拟实现迭代器时我们也用一个指针来模拟迭代器的行为不同的是指针进行操作时会指向该地址的下一个地址而我们期望的迭代器可以指向下一个节点。 示意图如下 因此如果单单的把指针看成迭代器则无法实现遍历链表的功能所以要实现迭代器必须对指针进行又一层的封装也就是把迭代器写成一个类但是该类的底层还是一个节点指针只是对该指针的操作有了新的规定。 正向迭代器代码实现如下
#define _CRT_SECURE_NO_WARNINGS 1#includeiostream
using namespace std;namespace ZH
{template class Tstruct list_node//节点类{list_nodeT* prev;list_nodeT* next;T val;list_node(const T t):prev(nullptr), next(nullptr), val(t){}};templateclass Tstruct list_iterator//迭代器类{typedef list_nodeT node;typedef list_iteratorT self;node* _node;// 成员变量list_iterator(node* node):_node(node){}bool operator!(const self s)//重载{return _node ! s._node;}self operator()//重载前置{_node _node-next;return *this;}T operator*()//重载解引用{return _node-val;}};template class Tclass list//链表类{public:typedef list_nodeT node;//让节点类看起来像一个普通的节点typedef list_iteratorT iterator;//让迭代器类看起来像一个迭代器list()//构造函数、目的是创建哨兵位头节点:_node(new node(-1)){_node-next _node;_node-prev _node;}void push_front(const T t)//头插{node* newnode new node(t);node* cur _node-next;_node-next newnode;newnode-prev _node;newnode-next cur;cur-prev newnode;}iterator begin(){//begin返回的是一个指向头节点的下一个节点的迭代器对象return iterator(_node-next);//匿名对象创建并返回}iterator end(){//begin返回的是一个指向头节点的迭代器对象return iterator(_node);//匿名对象创建并返回}~list()//析构{node* cur _node-next;node* dest cur-next;while (cur ! _node){delete cur;cur dest;dest dest-next;}delete _node;_node nullptr;}private:node* _node;//指向哨兵位的头节点};
}int main()
{ZH::listint lt;lt.push_front(1);lt.push_front(2);lt.push_front(3);lt.push_front(4);ZH::listint::iterator it lt.begin();while (it!lt.end()){cout *it ;it;}return 0;
} 运行结果 注意这里的it要看成是一个对象他的类型是 listint::iterator。ZH::listint::iterator it lt.begin();这句代码实际上是调用了拷贝构造用begin的返回对象构造了一个新的对象it。
2.2 反向迭代器 反向迭代器与正向迭代器的区别在于反向迭代器是从链表的最后一个节点开始往前遍历的并且他的逻辑和正向迭代器的逻辑是相反的可以确定的一点是反向迭代器也是通过一个类来实现的。 反向迭代器实现代码如下
#define _CRT_SECURE_NO_WARNINGS 1#includeiostream
using namespace std;namespace ZH
{template class Tstruct list_node//节点类{list_nodeT* prev;list_nodeT* next;T val;list_node(const T t):prev(nullptr), next(nullptr), val(t){}};templateclass Tstruct list_iterator//迭代器类{typedef list_nodeT node;typedef list_iteratorT self;node* _node;// 成员变量list_iterator(node* node):_node(node){}bool operator!(const self s)//重载{return _node ! s._node;}self operator()//重载前置{_node _node-next;return *this;}self operator--()//重载前置--{_node _node-prev;return *this;}T operator*()//重载解引用{return _node-val;}};templateclass Tclass list_reverse_iterator{public:typedef list_iteratorT iterator;typedef list_reverse_iteratorT rself;list_reverse_iterator(iterator it):rit(it){}bool operator!(const rself s)//重载{return rit! s.rit;//复用正向迭代器的重载}rself operator()//重载前置{--rit;//复用正向迭代器的return *this;}T operator*()//重载解引用{return *rit;//复用正向迭代器的解引用}private:iterator rit;};template class Tclass list//链表类{public:typedef list_nodeT node;//让节点类看起来像一个普通的节点typedef list_iteratorT iterator;//让迭代器类看起来像一个迭代器typedef list_reverse_iteratorT reverse_iterator;list()//构造函数、目的是创建哨兵位头节点:_node(new node(-1)){_node-next _node;_node-prev _node;}void push_front(const T t)//头插{node* newnode new node(t);node* cur _node-next;_node-next newnode;newnode-prev _node;newnode-next cur;cur-prev newnode;}reverse_iterator rbegin(){return reverse_iterator(iterator(_node-prev));//返回最后一个节点}reverse_iterator rend(){return reverse_iterator(iterator(_node));//返回头节点}~list()//析构{node* cur _node-next;node* dest cur-next;while (cur ! _node){delete cur;cur dest;dest dest-next;}delete _node;_node nullptr;}private:node* _node;//指向哨兵位的头节点};
}int main()
{ZH::listint lt;lt.push_front(1);lt.push_front(2);lt.push_front(3);lt.push_front(4);ZH::listint::reverse_iterator rit lt.rbegin();while (rit ! lt.rend()){cout *rit ;rit;}return 0;
} 运行结果 从上述代码中可以发现反向迭代器是复用正向迭代器的成员函数达到实现的只不过在反向迭代器类里进行又一层包装。
3、指定位置插入 有了迭代器就可以实现从指定位置插入了指定位置插入代码如下
void Insert(iterator pos, const T val)//插入{node* newnode new node(val);node* cur pos._node;node* prev cur-prev;prev-next newnode;newnode-prev prev;newnode-next cur;cur-prev newnode;} 值得注意的是list的插入不会导致迭代器失效因为即使在该迭代器指向节点的前面插入一个数据则该迭代器还是指向该节点的。 4、指定位置删除 指定位置删除代码如下
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;} 删除逻辑示意图 删除与插入不同在于删除之后迭代器会失效因为此时it指向的是一块被回收的区域不能直接访问it所指向的区域会导致野指针问题。
5、结语 以上就是关于list如何实现的讲解list的模拟实现完全体现了面向对象的思想链表本身、节点以及迭代器都被封装成一个类从用户的角度看是在对象的层面上直接进行操作的但是底层却是各种复用依旧是通过操作内置类型来实现上层的对象之间的操作。 最后希望本文可以给你带来更多的收获如果本文对你起到了帮助希望可以动动小指头帮忙点赞关注收藏如果有遗漏或者有误的地方欢迎大家在评论区补充谢谢大家
