当前位置: 首页> 财经> 创投人物 > 商丘企业网站建设服务_办公室布局效果图_seoul是什么品牌_网络营销推广方案策划书

商丘企业网站建设服务_办公室布局效果图_seoul是什么品牌_网络营销推广方案策划书

时间:2025/7/11 14:17:29来源:https://blog.csdn.net/X__cheng/article/details/144595363 浏览次数:0次
商丘企业网站建设服务_办公室布局效果图_seoul是什么品牌_网络营销推广方案策划书

额额额,浅学了list,老规矩,模拟实现一下list,能让我们更好的理解list。若有兴趣,不妨垂阅!

目录

1.模拟实现list 

1.1.list节点

1.2.list正向迭代器 

 1.3.list模拟实现

2. test

3.小知识 

 3.1.小知识1

3.2.小知识2

3.3. 小知识3

4.模拟实现list完整代码


 

同样的,我不可能把list所有接口都模拟实现出来,我也没有这个能力。So,模拟实现一些简单常用的接口。

本工程包括2个文件:

mylist.h:用于模拟实现list。

test.cpp:用于测试模拟实现的list接口是否达到预期。

1.模拟实现list 

以下代码均放到mylist.h文件中。 

1.1.list节点

 由于list底层是带头(哨兵位)双向循环链表。所以模拟实现的list节点需要能找到前驱节点和后继节点,这点是毋庸置疑的。那么,我们将list节点设计如下:

namespace HD
{//list节点template<typename T>struct listNode{typedef listNode node;//类里面可以将listNode<T>用listNode替代T _val;node* _prev;node* _next;};
}

_val用于存储数据,_prev用于指向前驱节点,_next用于指向后继指针。

1.2.list正向迭代器 

 好的,由于list反向迭代器较为复杂,所以我只模拟实现正向迭代器。正向迭代器分为:普通正向迭代器、const正向迭代器。一个一个来模拟实现:


1.普通正向迭代器

我们知道迭代器是模拟指针的行为,但是却不是所有的迭代器都能直接用原生指针实现。例如:

string的正向迭代器,由于其底层是字符顺序表,可以直接用原生指针来实现迭代器;

但是如list底层是链表,正向迭代器就不能直接用原生指针实现,好比如,list<int>::iterator it; ++it;,如果该list的正向迭代器是原生指针实现的,++操作能让it指向下一个节点吗?显然不能,因为链表的物理空间不是连续的。

那么我们怎么办?

别忘了操作符重载这里利器,我们可以用类封装一下原生指针来实现普通正向迭代器:

namespace HD
{//list 普通正向迭代器template <typename T>struct listIterator{typedef listNode<T>* pNode;typedef listIterator<T> self;pNode _pNode;listIterator<T>(pNode pNode = nullptr):_pNode(pNode){}T& operator*(){return (*_pNode)._val;}self operator++(int)//后置++{self it(_pNode);_pNode = _pNode->_next;return it;}self& operator++()//前置++{_pNode = _pNode->_next;return *this;}self operator--(int)//后置--{self it(_pNode);_pNode = _pNode->_prev;return it;}self& operator--()//前置--{_pNode = _pNode->_prev;return *this;}bool operator!=(const self& it){return _pNode != it._pNode;}bool operator==(const self& it){return _pNode == it._pNode;}T* operator->(){return &_pNode->_val;}};
}

其实仔细看,这个类只有一个成员变量,就是list节点的指针_pNode。把这个指针用类封装一下,提供各种运算符重载作为该类的成员函数,就成了。本质上,这个类不还是list节点指针吗?但是这个list节点指针的行为却不是原生指针的行为能达到的。。。。。好好体会!!!! 


2.const正向迭代器 

普通正向迭代器和const正向迭代器基本一样。我们想想,const正向迭代器区别于普通正向迭代器,无非就是const正向迭代器指向的节点存储的数据不能更改吗?

SO:

namespace HD
{//list const正向迭代器template <typename T>struct listConstIterator{typedef listNode<T>* pNode;typedef listConstIterator<T> self;pNode _pNode;listConstIterator<T>(pNode pNode = nullptr):_pNode(pNode){}const T& operator*(){return (*_pNode)._val;}self operator++(int)//后置++{self it(_pNode);_pNode = _pNode->_next;return it;}self& operator++()//前置++{_pNode = _pNode->_next;return *this;}self operator--(int)//后置--{self it(_pNode);_pNode = _pNode->_prev;return it;}self& operator--()//前置--{_pNode = _pNode->_prev;return *this;}bool operator!=(const self& it){return _pNode != it._pNode;}bool operator==(const self& it){return _pNode == it._pNode;}const T* operator->(){return &_pNode->_val;}};
}

仔细看,实现起来跟普通正向迭代器的区别就在于operator*和operator->这2个函数的返回值不同罢了。至于operator->这个函数到底干啥的,一会儿说的。


3.普通正向迭代器和const正向迭代器合二为一 

看到普通正向迭代器和const正向迭代器这两个类模板基本一样,那么我们完全可以写一个类模板来代替以上2个类模板:

namespace HD
{//list正向迭代器template <typename T,typename Ref,typename Ptr>struct listIterator{typedef listNode<T>* pNode;typedef listIterator<T,Ref,Ptr> self;pNode _pNode;listIterator<T,Ref,Ptr>(pNode pNode=nullptr):_pNode(pNode){}Ref operator*(){return (*_pNode)._val;}self operator++(int)//后置++{self it(_pNode);_pNode = _pNode->_next;return it;}self& operator++()//前置++{_pNode = _pNode->_next;return *this;}self operator--(int)//后置--{self it(_pNode);_pNode = _pNode->_prev;return it;}self& operator--()//前置--{_pNode = _pNode->_prev;return *this;}bool operator!=(const self& it){return _pNode != it._pNode;}bool operator==(const self& it){return _pNode == it._pNode;}Ptr operator->(){return &_pNode->_val;}};
}

通俗易懂讲,当Ref、Ptr是T&、T*的时候,不就是普通正向迭代器吗?

当Ref、Ptr是const T&、const T*的时候,不就是const正向迭代器吗?

 1.3.list模拟实现

namespace HD
{//listtemplate<typename T>class list{private:typedef listNode<T> node;typedef listNode<T>* pNode;typedef T value_type;typedef size_t size_type;private:pNode _pHead;size_t _size;public:typedef listIterator<T,T&,T*> iterator;typedef listIterator<T,const T&,const T*> const_iterator;public:void emptyInit(){_pHead = new node;_pHead->_prev = _pHead;_pHead->_next = _pHead;_size = 0;}list(){emptyInit();}list(size_type n, const value_type& val=value_type()){emptyInit();while (n--){push_back(val);}}list(const list& x){emptyInit();pNode cur = x._pHead->_next;while (cur != x._pHead){push_back(cur->_val);cur = cur->_next;}}void swap(list& x){std::swap(x._pHead, _pHead);std::swap(x._size, _size);}list& operator=(list x)  {swap(x);return *this;}void push_back(const value_type& val){/*pNode end = _pHead->_prev;pNode newNode = new node;newNode->_val = val;end->_next = newNode;newNode->_prev = end;_pHead->_prev = newNode;newNode->_next = _pHead;_size++;*/insert(_pHead, val);}void push_front(const value_type& val){insert(_pHead->_next, val);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}size_type size()const{return _size;}bool empty()const{return _size == 0;}iterator begin(){/*iterator it(_pHead->_next);return it;*//*return iterator(_pHead->_next);//匿名对象*/return _pHead->_next;}iterator end(){/*iterator it(_pHead);return it;*//*return iterator(_pHead);//匿名对象*/return _pHead;}const_iterator begin()const{return _pHead->_next;}const_iterator end()const{return _pHead;}void clear(){while (size() != 0){pop_back();}}~list(){clear();delete _pHead;_pHead = nullptr;_size = 0;}iterator insert(iterator position, const value_type& val);iterator erase(iterator position);};template <typename T>typename list<T>::iterator list<T>::insert(list<T>::iterator position, const list<T>::value_type& val){pNode cur = position._pNode;pNode prev = position._pNode->_prev;pNode newNode = new node;newNode->_val = val;newNode->_next = cur;cur->_prev = newNode;newNode->_prev = prev;prev->_next = newNode;_size++;return position--;}template<typename T>typename list<T>::iterator list<T> ::erase(list<T>::iterator position){assert(position != end());//不能erase哨兵位节点pNode prev = position._pNode->_prev;pNode next = position._pNode->_next;delete position._pNode;prev->_next = next;next->_prev = prev;_size--;return next;}
}

有点长啊。。 2个成员变量:_pHead是哨兵位的指针,_size是节点个数(不包括哨兵位)。insert和erase采用声明和定义分离,其他成员函数声明和定义不分离。

2. test

在test.cpp中测试一下list正向迭代器中的operator*和operator->这2个接口:


1.operator*

对于list的普通正向迭代器: 

#include"mylist.h"
namespace HD
{void test(){list<size_t> l(3, 10);list<size_t>::iterator it = l.begin();while (it != l.end()){(*it)++;cout << *it << ' ';it++;}cout << endl;}
}
int main()
{HD::test();return 0;
}

没什么问题吧: 

对于list的const正向迭代器:

#include"mylist.h"
namespace HD
{void test(){const list<size_t> l(3, 10);list<size_t>::const_iterator it = l.begin();while (it != l.end()){(*it)++;cout << *it << ' ';it++;}cout << endl;}
}
int main()
{HD::test();return 0;
}

运行错误了:

问题就出现在*it的类型是const size_t&,不能修改,这就区别于普通正向迭代器了。

 如果这样:

#include"mylist.h"
namespace HD
{void test(){const list<size_t> l(3, 10);list<size_t>::const_iterator it = l.begin();while (it != l.end()){cout << *it << ' ';it++;}cout << endl;}
}
int main()
{HD::test();return 0;
}

没什么问题,可以实现遍历list容器的功能:


2.operator-> 

对于操作符->,我们的使用场景一般是在于结构体指针访问其指向变量的成员,像这样子:

#include"mylist.h"
namespace HD
{struct example{int _a = 1;int _b = 2;};void test(){auto E = new example;cout << E->_a << ' ' << E->_b << endl;}
}
int main()
{HD::test();return 0;
}

我们希望迭代器也能这样子,所以重载了->操作符。 


 对于list的普通正向迭代器:

#include"mylist.h"
namespace HD
{struct example{int _a = 1;int _b = 2;};void test(){list<example> l(3);auto it = l.begin();while (it != l.end()){it->_a++; it->_b++;//奇怪*2?cout << it->_a << ' ' << it->_b << "   ";//奇怪?it++;}}
}
int main()
{HD::test();return 0;
}

先看一下运行结果:

运行成功了,但是细细分析,感觉怪怪的。看到operator->的定义:

        Ptr operator->(){return &_pNode->_val;}

返回list节点_val的地址。那么这里的_val的类型是example,返回一个自定义类型指针example*。那么it->_a翻译过来就是example*_a,这是个啥玩意?关键还运行成功了。

其实编译器对这里作了特殊处理,本来应该是2个->才合乎语法,为了可读性,省略了后1个->。其实这里编译器省略了后1个->,在编译器看来,代码是这样子的:

#include"mylist.h"
namespace HD
{struct example{int _a = 1;int _b = 2;};void test(){list<example> l(3);auto it = l.begin();while (it != l.end()){//在编译器看来,等价于it->_a++;it->_b++;it.operator->()->_a++; it.operator->()->_b++;//在编译器看来,等价于cout<<it->_a<<' '<<it->_b<<"   ";cout << it.operator->()->_a << ' ' << it.operator->()->_b << "   ";it++;}}
}
int main()
{HD::test();return 0;
}

也是可以运行成功的:

仔细体会一下,迭代器是不是在模拟指针的行为?

 对于list的const正向迭代器: 

#include"mylist.h"
namespace HD
{struct example{int _a = 1;int _b = 2;};void test(){const list<example> l(3);auto it = l.begin();while (it != l.end()){it->_a++; it->_b++;cout << it->_a << ' ' << it->_b << "   ";it++;}}
}
int main()
{HD::test();return 0;
}

运行不成功:

问题就在于it->返回值类型为const example* ,这不就区别于普通正向迭代器了吗?

 虽然不能通过list的const正向迭代器来修改list容器的值,但是用来遍历list容器是没问题的:

#include"mylist.h"
namespace HD
{struct example{int _a = 1;int _b = 2;};void test(){const list<example> l(3);auto it = l.begin();while (it != l.end()){cout << it->_a << ' ' << it->_b << "   ";it++;}}
}
int main()
{HD::test();return 0;
}

3.小知识 

 3.1.小知识1

 讨论1个问题:const迭代器为什么是单独搞了一个类型const_iterator,而不是直接用const修饰普通迭代器?

const iterator:迭代器本身不能修改,若是直接用const修饰普通迭代器当作const迭代器,那么const迭代器就不能用来遍历容器了。

const_iterator:希望指向的内容不能修改,实际上const迭代器也是这样子实现的,例如如上模拟实现。这样子的话const迭代器本身是能修改的,可以可以用来遍历容器。

3.2.小知识2

list迭代器失效问题:

 list容器迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入 时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。

例如说,erase、pop_back、pop_front等操作都会导致迭代器失效,例如在test.cpp中:

#include"mylist.h"
namespace HD
{void test(){list<int> l(3, 10);auto it = l.begin();while (it != l.end()){//erase()函数执行后,it所指向的节点已被删除,//因此it无效,在下一次使用it时,必须先给其赋值l.erase(it);it++;}}
}
int main()
{HD::test();return 0;
}

改正写法:

#include"mylist.h"
namespace HD
{void test(){list<int> l(3, 10);auto it = l.begin();while (it != l.end()){it = l.erase(it);//或者l.erase(it++);}}
}
int main()
{HD::test();return 0;
}

同样的,VS2022对std::list的erase进行了强制的检查,若erase后,没有更新迭代器就访问会报错,在test.cpp中:

#include"mylist.h"
namespace HD
{void test(){std::list<int> l(3, 10);auto it = l.begin();while (it != l.end()){l.erase(it);it++;}}
}
int main()
{HD::test();return 0;
}

所以使用std::list容器时,若是erase等删除操作后想要访问迭代器,请更新!

在list插入,如insert、push_back、push_front等操作,不会使得迭代器失效,所以VS2022对于std::list的insert等操作后也没有对其迭代器是否更新过进行检查。

3.3. 小知识3

 按需实例化:

当模板没有实例化,就算模板内有错误,也不一定会报错,对于模板内明显的错误一般会检查出来,例如缺少一个分号这些明显错误;但是一下细节的错误就不一定能检查出来。如:

在test.cpp中,写了一个函数模板用于打印模拟实现的list对象;

#include"mylist.h"
namespace HD
{template<class T>void printList(const list<T>& list){auto it = list.begin();while (it != list.end()){(*it)++;//错误cout << *it << ' ';}cout << endl;}
}
int main()
{return 0;
}

 如上代码,有细节错误:list的类型是const list<T>&,显然其值不能修改,但是*it++却想要修改。但是这个模板没有实例化,所以运行不报错:

如果让这个模板实例化一下,肯定会报错:

#include"mylist.h"
namespace HD
{template<class T>void printList(const list<T>& list){auto it = list.begin();while (it != list.end()){(*it)++;cout << *it << ' ';}cout << endl;}void test(){list<int> l(3, 5);printList(l);}
}
int main()
{HD::test();return 0;
}

且看:error C3892: “it”: 不能给常量赋值 ,并且:

4.模拟实现list完整代码

在mylist.h文件下:

#pragma once
#include<iostream>
#include<assert.h>
#include<list>
using namespace std;
namespace HD
{//list节点template<typename T>struct listNode{typedef listNode node;//类里面可以将listNode<T>用listNode替代T _val;node* _prev;node* _next;};//list正向迭代器template <typename T,typename Ref,typename Ptr>struct listIterator{typedef listNode<T>* pNode;typedef listIterator<T,Ref,Ptr> self;pNode _pNode;listIterator<T,Ref,Ptr>(pNode pNode=nullptr):_pNode(pNode){}Ref operator*(){return (*_pNode)._val;}self operator++(int)//后置++{self it(_pNode);_pNode = _pNode->_next;return it;}self& operator++()//前置++{_pNode = _pNode->_next;return *this;}self operator--(int)//后置--{self it(_pNode);_pNode = _pNode->_prev;return it;}self& operator--()//前置--{_pNode = _pNode->_prev;return *this;}bool operator!=(const self& it){return _pNode != it._pNode;}bool operator==(const self& it){return _pNode == it._pNode;}Ptr operator->(){return &_pNode->_val;}};list const正向迭代器//template <typename T>//struct listConstIterator//{//	typedef listNode<T>* pNode;//	typedef listConstIterator<T> self;//	pNode _pNode;//	listConstIterator<T>(pNode pNode = nullptr)//		:_pNode(pNode)//	{//	}//	const T& operator*()//	{//		return (*_pNode)._val;//	}//	self operator++(int)//后置++//	{//		self it(_pNode);//		_pNode = _pNode->_next;//		return it;//	}//	self& operator++()//前置++//	{//		_pNode = _pNode->_next;//		return *this;//	}//	self operator--(int)//后置--//	{//		self it(_pNode);//		_pNode = _pNode->_prev;//		return it;//	}//	self& operator--()//前置--//	{//		_pNode = _pNode->_prev;//		return *this;//	}//	bool operator!=(const self& it)//	{//		return _pNode != it._pNode;//	}//	bool operator==(const self& it)//	{//		return _pNode == it._pNode;//	}//	const T* operator->()//	{//		return &_pNode->_val;//	}//};//list 普通正向迭代器//template <typename T>//struct listIterator//{//	typedef listNode<T>* pNode;//	typedef listIterator<T> self;//	pNode _pNode;//	listIterator<T>(pNode pNode = nullptr)//		:_pNode(pNode)//	{//	}//	T& operator*()//	{//		return (*_pNode)._val;//	}//	self operator++(int)//后置++//	{//		self it(_pNode);//		_pNode = _pNode->_next;//		return it;//	}//	self& operator++()//前置++//	{//		_pNode = _pNode->_next;//		return *this;//	}//	self operator--(int)//后置--//	{//		self it(_pNode);//		_pNode = _pNode->_prev;//		return it;//	}//	self& operator--()//前置--//	{//		_pNode = _pNode->_prev;//		return *this;//	}//	bool operator!=(const self& it)//	{//		return _pNode != it._pNode;//	}//	bool operator==(const self& it)//	{//		return _pNode == it._pNode;//	}//	T* operator->()//	{//		return &_pNode->_val;//	}//};//listtemplate<typename T>class list{private:typedef listNode<T> node;typedef listNode<T>* pNode;typedef T value_type;typedef size_t size_type;private:pNode _pHead;size_t _size;public:typedef listIterator<T,T&,T*> iterator;typedef listIterator<T,const T&,const T*> const_iterator;public:void emptyInit(){_pHead = new node;_pHead->_prev = _pHead;_pHead->_next = _pHead;_size = 0;}list(){emptyInit();}list(size_type n, const value_type& val=value_type()){emptyInit();while (n--){push_back(val);}}list(const list& x){emptyInit();pNode cur = x._pHead->_next;while (cur != x._pHead){push_back(cur->_val);cur = cur->_next;}}void swap(list& x){std::swap(x._pHead, _pHead);std::swap(x._size, _size);}list& operator=(list x)  {swap(x);return *this;}void push_back(const value_type& val){/*pNode end = _pHead->_prev;pNode newNode = new node;newNode->_val = val;end->_next = newNode;newNode->_prev = end;_pHead->_prev = newNode;newNode->_next = _pHead;_size++;*/insert(_pHead, val);}void push_front(const value_type& val){insert(_pHead->_next, val);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}size_type size()const{return _size;}bool empty()const{return _size == 0;}iterator begin(){/*iterator it(_pHead->_next);return it;*//*return iterator(_pHead->_next);//匿名对象*/return _pHead->_next;}iterator end(){/*iterator it(_pHead);return it;*//*return iterator(_pHead);//匿名对象*/return _pHead;}const_iterator begin()const{return _pHead->_next;}const_iterator end()const{return _pHead;}void clear(){while (size() != 0){pop_back();}}~list(){clear();delete _pHead;_pHead = nullptr;_size = 0;}iterator insert(iterator position, const value_type& val);iterator erase(iterator position);};template <typename T>typename list<T>::iterator list<T>::insert(list<T>::iterator position, const list<T>::value_type& val){pNode cur = position._pNode;pNode prev = position._pNode->_prev;pNode newNode = new node;newNode->_val = val;newNode->_next = cur;cur->_prev = newNode;newNode->_prev = prev;prev->_next = newNode;_size++;return position--;}template<typename T>typename list<T>::iterator list<T> ::erase(list<T>::iterator position){assert(position != end());//不能erase哨兵位节点pNode prev = position._pNode->_prev;pNode next = position._pNode->_next;delete position._pNode;prev->_next = next;next->_prev = prev;_size--;return next;}
}

 感谢阅读!

关键字:商丘企业网站建设服务_办公室布局效果图_seoul是什么品牌_网络营销推广方案策划书

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: