广西建设网站在线服务,wordpress首页显示友情链接,也可以用,seo就业前景怎么样深入篇【C】手搓模拟实现list类(详细剖析底层实现原理#xff09; 模拟实现正反向迭代器【容器适配器模式】 Ⅰ.迭代器实现1.一个模板参数2.两个模板参数3.三个模板参数 Ⅱ.反向迭代器实现1.容器适配器模式 Ⅲ.list模拟实现1.定义结点2.封装结点3.构造/拷贝4.迭代器… 深入篇【C】手搓模拟实现list类(详细剖析底层实现原理 模拟实现正反向迭代器【容器适配器模式】 Ⅰ.迭代器实现1.一个模板参数2.两个模板参数3.三个模板参数 Ⅱ.反向迭代器实现1.容器适配器模式 Ⅲ.list模拟实现1.定义结点2.封装结点3.构造/拷贝4.迭代器5.插入/头尾插6.删除/头尾删7.析构/清理 Ⅳ.整代码 Ⅰ.迭代器实现
1.一个模板参数
在模拟实现list之前我们要理解list中的迭代器是如何实现的。 在vector中迭代器可以看成一个指针指向vector中的数据。它的解引用会访问到具体的数据本身会移动到下一个数据位置上去这些都是因为vector具有天生的优势空间上是连续的数组这样指针就是一个天生完美的迭代器。而list与vector不同list在空间上并不连续指针解引用访问到的也不是具体的数据而是结点本身指针也不会移动到下一个结点位置这些问题都说明list的迭代器不能简单是只是原生指针就可以完成。 正确的实现方法是 将指向结点的原生指针封装起来构造出一个自定义类型的迭代器。在这个迭代器里我们通过运算符重载来改变原生指针的一些行为比如解引用运算符重载运算符重载。这样我们就可以构造出一个满足预期的迭代器了。 使用原生指针作为迭代器不符合需求迭代器的解引用和都不符合list迭代器的要求 所以这里将原生指针进行封装然后使用运算符重载达到我们想要的效果 所以list的迭代器是一个自定义类型这个自定义类型里存着原生指针 template class T//将这个迭代器搞成模板适用于各种类型struct _list_iterator{typedef listNodeT Node;//因为结点类被搞成了模板所以名字很长我们这里将其重命名为Node_list_iterator( Node* node)//用原生指针初始化:_node(node){}T operator*()//重载*运算符因为原生指针中的解引用不符合list迭代要求{return _node-val;//要求解引用要访问到结点的的数据而不是结点}_list_iteratorT operator()//重载运算符{_node _node-next;//要求要挪动到下一个结点的位置上去return *this;}T* operator-(){return _node-val;}bool operator!(const _list_iteratorT it){return _node ! it._node;//用原生指针比较即可}Node* _node;//底层封装的是原生指针};2.两个模板参数
迭代器基本上已经完成可以正常使用了。不过list中的迭代器实现并没有这么简单它的模板参数实现给了三个参数这里我们才有一个参数接下来我会一一增加上去。第二个模板参数是什么呢 第二个模板参数是为了实现const迭代器而设计的const迭代器要求指向的内容不能被修改而迭代器本身是可以进行修改的。那如何做到呢 解引用访问到的就是数据本身而const迭代器要求指向的数据不能被修改所以直接让解引用运算符重载函数的返回值加上const修饰即可。
template class T//将这个迭代器搞成模板适用于各种类型struct _list_iterator{typedef listNodeT Node;_list_iterator( Node* node)//用原生指针初始化:_node(node){}const T operator*()//const迭代器访问时返回的是const修饰的数据无法被修改。{return _node-val;}_list_iteratorT operator()//重载运算符{_node _node-next;return *this;}T* operator-(){return _node-val;}bool operator!(const _list_iteratorT it){return _node ! it._node;}Node* _node;//底层封装的是原生指针};有的人会选择拷贝一份封装的迭代器然后其他都相同就解引用运算符重载函数返回类型不同普通迭代器返回值是T,const迭代器返回类型是constT.但这样做实在太冗余了大佬是再添加一个模板参数来控制这里的迭代器返回类型的。 所以第二个模板参数是为了控制解引用运算符重载函数的返回值类型的。 有的人会这样做直接给迭代器前面加上const这样的做法是不对的 我们要求的const迭代器是1.迭代器指向的内容不能被修改2.迭代器本身可以修改 1.const T* iterator 2.T* const iterator 这两种情况应该是第一种情况满足要求。 typedef const _list_iterator const_iterator;这种情况是第二种情况const修饰的是这个封装的迭代器说明是这个迭代器不能被修改而不是它指向的内容不能修改 template class T,class Ref//定义两个模板参数第二个Ref是为了控制*运算符重载函数的返回值以达到传使用const迭代器返回const T 使用正常迭代器返回Tstruct _list_iterator{typedef listNodeT Node;//将结点重命名typedef _list_iteratorT, Ref Self;//将迭代器重命名为Self//为什么要重命名因为加上模板后太长了重命名一个简洁的名字_list_iterator(Node* node):_node(node){}Ref operator*()//将这里的返回值改成模板Ref这样就可以通过模板参数来控制返回值不同了{return _node-val;}T* operator-(){return _node-val;}Self operator()//重载运算符//这里的Self就是迭代器_list_iteratorT, Ref{_node _node-next;return *this;}Self operator(int)//后置运算符//这里的Self就是迭代器_list_iteratorT, Ref{Node* temp(this);_node _node-next;return *temp;}bool operator!(const Self it)//这里的Self就是迭代器_list_iteratorT, Ref{return _node ! it._node;}Node* _node;//原生指针};3.三个模板参数
迭代器的第三个模板参数是什么呢它又是干什么的呢我们首先要模拟一个场景一个类的成员变量是允许我们访问的(公有的)那迭代器类似一个指针指针就可以通过-来访问到指针指向的内容。那这样我们就可以通过迭代器的-访问到数据而不是解引用。 T* operator-(){return _node-val;}不过这里的箭头运算符重载就有点奇怪了it-val 就是等于it.operator-().返回的是T* ,T*是怎么访问到val的呢这里明显少了一个箭头正确的写法应该是这样it--val但编译器觉得太挫了将一个箭头省略了编译器为了简洁好看会自动忽略这个问题。
listint::iterator it lt.begin();while (it ! lt.end()){cout (it-val) ;it;//因为it是自定义类型自定义类型就会去调用它的运算符重载}cout endl;第三个模板参数也是为了应对const迭代器而设计的只不过这个模板参数控制的是箭头运算符重载函数的返回值类型因为const迭代器使用-运算符后返回的应该是const T类型而正常迭代器使用-运算符后返回的应该是T。
template class T, class Ref,class Ptr//三个模板参数第二个控制解引用运算符重载函数的返回值类型
//第三个参数用来控制箭头运算符重载函数的返回值类型。这样就可以通过用户传什么类型的迭代器模板自动生成什么样子的迭代器给他使用。struct _list_iterator{typedef listNodeT Node;//将结点重命名typedef _list_iteratorT, Ref,Ptr Self;//将迭代器重命名不重命名的话加上模板太长了。_list_iterator(Node* node):_node(node){}Ref operator*()//重载*运算符因为原生指针中的解引用不符合list迭代要求{return _node-val;}Ptr operator-() //const对象使用 返回的应该是const T * 正常对象使用返回的是T*{return _node-val;}Self operator()//重载运算符//Self就是迭代器_list_iteratorT, Ref,Ptr{_node _node-next;return *this;}Self operator(int)//后置运算符{Self* temp(this);_node _node-next;return *temp;}Self operator--()//重载--运算符{_node _node-prev;return *this;}Self operator--(int)//后置--运算符{Self* temp(this);_node _node-prev;return *temp;}bool operator!(const Self it){return _node ! it._node;}Node* _node;//原生指针};Ⅱ.反向迭代器实现
1.容器适配器模式
反向迭代是如何实现的呢设计的原理就是适配器模式将正向迭代器封装起来然后通过函数重载来完成反向迭代器的一系列操作这个模式牛逼之处就在于你传任何一个类型的正向迭代器它都会给你适配出它的反向迭代器就这么牛。反向迭代器的一些操作与正向迭代器相反比如反向迭代器的就是调用正向迭代器的–反向迭代器的–就是调用正向迭代器的。而解引用应该是一样的都是访问具体的数据。 不过要注意的是反向迭代器的解引用操作与正向迭代不同这是因为标准库里采用了一种镜像对称的方案。 什么意思呢 正常来说begin()是指向第一个位置的迭代器end()是指向最后一个数据下一个位置的迭代器。 rbegin()指向的是最后一个数据位置的迭代器rend()是指向第一个数据前面的位置的迭代器。 而镜像对称就是要让正迭代器和反迭代器的位置是对称的。 这样反向迭代器的rbegin()就可以直接用正向迭代器的end()初始化rend()就可以直接用正向迭代器begin()初始化。而弄成这样的代价就是让解引用运算符重载函数来承担了解引用的不是当前位置的数据而是前一个位置上的数据的这样就可以让反向迭代器正确的解引用到数据了。 template class Iterator,class Ref,class Ptrstruct ReserveIterator
{typedef ReserveIteratorIterator, Ref, Ptr Self;ReserveIterator(Iterator it):_it(it){}//用正向迭代器初始化Ref operator*()//解引用解的是前一个位置保持对称{Iterator tmp _it;return *(--tmp);//正向迭代器的模板类型是 classT ,T ,T*}Self operator(){--_it;return *this;}Self operator--(){_it;return *this;}bool operator!(Self it){return _it ! it._it;}Iterator _it;//底层封装一个正向迭代器};Ⅲ.list模拟实现
首先先搭出一个简易的list类模型再一步一步完善。
1.定义结点
链表是由一个个的结点连接而成所以第一步先构造出一个结点类。 这个结点包含前后指针和对应的数据。
template class Tstruct listNode{listNodeT* next;listNodeT* prev;T val;listNode(const T val T()):next(nullptr), prev(nullptr), val(val){}};2.封装结点
接下来就是将结点封装到list类里面用一个个结点来实现list的各个功能了。 我们实现的list是一个带头双向循环链表所以第一步链表的构造就必须是双向循环的模式。 因为封装的结点是一个类模板所以我们习惯给它用typedef重命名为一个简洁的名字。
3.构造/拷贝
template class Tclass list//带头双向循环列表{public:typedef listNodeT Node;list()//构造函数{_head new Node;//首先给头结点开辟空间_head-prev _head;//让这个头结点的前后指针都指向自己构造出一个循环链表_head-next _head;sz 0;}list(const listT lt1)//拷贝构造---深拷贝{_head new Node;//首先还是构造出一个循环链表模型_head-prev _head;_head-next _head;sz 0;for (auto e : lt1)//然后将要拷贝的对象的一个个数据全部尾插进来{push_back(e);//push_back这里还没有实现在下面会实现知道原理即可}}void swap( listT lt1){std::swap(_head, lt1._head);std::swap(sz, lt1.sz);}listT operator( listTlt1)//赋值运算符重载---现代写法{swap(lt1);return *this;}private:Node* _head;//封装的是一个指向结点的指针//封装的是指向头结点的指针size_t sz;//大小
};4.迭代器
迭代器我们上面已经实现完毕这里就可以直接使用了。 typedef _list_iteratorT, T,T* iterator;//普通迭代器 typedef _list_iteratorT, const T,const T* const_iterator;//const迭代器typedef ReserveIteratoriterator, T, T* reserve_iterator;//反向迭代器typedef ReserveIteratorconst_iterator, T, T* reserve_iterator;//反向const迭代器reserve_iterator rbegin()//反向迭代器要保持镜像对称用正向迭代器的end()构造rbegin(){return reserve_iterator(end());}reserve_iterator rend()//用正向迭代器的begin()构造rend(){return reserve_iterator(begin());}reserve_iterator rbegin()const{return reserve_iterator(end());}reserve_iterator rend()const {return reserve_iterator(begin());}iterator begin(){return _head-next;//return _list_iterator(_head-next)//单参数的构造支持隐式类型转化}iterator end(){return _head;}const_iterator begin()const{return _head-next;//return _list_iterator(_head-next)//单参数的构造支持隐式类型转化}const_iterator end()const{return _head;}5.插入/头尾插 iterator insert(iterator pos,const T x){//最好还是转化成结点的指针这里访问迭代器不方便,这里就体现了为什么要用struct来定义迭代器让其成员共有Node* cur pos._node;Node* prev cur-prev;Node* newnode new Node(x);prev-next newnode;newnode-prev prev;newnode-next cur;cur-prev newnode;sz;return newnode;//返回新插入结点的位置}void push_back(const T x){尾插首先需要找到尾//Node* tail _head-prev;找到尾部后将新结点连接//Node* newnode new Node(x);//tail-next newnode;//newnode-prev tail;//_head-prev newnode;//newnode-next _head;insert(end(), x);//可以直接复用insert}void push_front(const T x){insert(begin(),x);//可以直接复用insert}6.删除/头尾删 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;sz--;return next;}void pop_back(){erase(--end());//直接复用erase删除尾部位置}void pop_front()//直接复用erase删除第一个数据{erase(begin());}7.析构/清理 void clear()//清空数据但不清哨兵位{iterator it begin();while (it ! end()){iterase(it);//删除完后会返回下一个位置的迭代器}sz 0;}~list()//析构全部清除{clear();delete _head;_head nullptr;}Ⅳ.整代码
#pragma once
#includeiostream
#include stdio.h
#include assert.h
#include ReserveIterator.h
using namespace std;
namespace tao
{template class Tstruct listNode{listNodeT* next;listNodeT* prev;T val;listNode(const T val T()):next(nullptr), prev(nullptr), val(val){}};template class T, class Ref,class Ptrstruct _list_iterator{typedef listNodeT Node;typedef _list_iteratorT, Ref,Ptr Self;_list_iterator(Node* node):_node(node){}Ref operator*()//重载*运算符因为原生指针中的解引用不符合list迭代要求{return _node-val;}Ptr operator-() //const对象使用 返回的应该是const T *{return _node-val;}Self operator()//重载运算符{_node _node-next;return *this;}Self operator(int)//后置运算符{Self* temp(this);_node _node-next;return *temp;}Self operator--()//重载--运算符{_node _node-prev;return *this;}Self operator--(int)//后置--运算符{Self* temp(this);_node _node-prev;return *temp;}bool operator!(const Self it){return _node ! it._node;}Node* _node;//原生指针};template class Iterator,class Ref,class Ptr
//反向迭代器struct ReserveIterator{typedef ReserveIteratorIterator, Ref, Ptr Self;ReserveIterator(Iterator it):_it(it){}//用正向迭代器初始化Ref operator*()//解引用解的是前一个位置保持对称{Iterator tmp _it;return *(--tmp);//正向迭代器的模板类型是 classT ,T ,T*}Self operator(){--_it;return *this;}Self operator--(){_it;return *this;}bool operator!(Self it){return _it ! it._it;}Iterator _it;//底层封装一个正向迭代器};//容器适配器模式 ---反向迭代器--给我正向迭代器我给你适配出反向迭代器针对任何容器都可以只要给我正向迭代器就可以适配出反向迭起template class Tclass list//带头双向循环列表{public:typedef listNodeT Node;//typedef _list_iteratorT iterator;//将自定义的迭代器名字统一命名为iterator//typedef _list_iteratorT,T iterator;//普通迭代器typedef _list_iteratorT, T,T* iterator;//普通迭代器//typedef _list_iteratorT, const T const_iterator;//const迭代器typedef _list_iteratorT, const T,const T* const_iterator;//const迭代器//const迭代器如何设计//我们要求的const迭代器是1.迭代器指向的内容不能被修改2.迭代器本身可以修改//1.const T* iterator 2.T* const iterator//typedef const _list_iteratorT const_iterator;这种情况是第二种情况const修饰的是这个封装的迭代器说明是这个迭代器不能被修改而不是它指向的内容不能修改//正确的做法是解引用时访问到数据返回时返回const T类型的数据这样返回回来的数据就无法再被修改//有的人会选择拷贝一份封装的迭代器然后其他都相同就解引用运算符重载函数返回类型不同普通迭代器返回值是T,const迭代器返回类型是constT.//但这样做实在太冗余了大佬是再添加一个模板参数来控制这里的迭代器返回类型的。typedef ReserveIteratoriterator, T, T* reserve_iterator;reserve_iterator rbegin(){return reserve_iterator(end());}reserve_iterator rend(){return reserve_iterator(begin());}iterator begin(){return _head-next;//return _list_iterator(_head-next)//单参数的构造支持隐式类型转化}iterator end(){return _head;}const_iterator begin()const{return _head-next;//return _list_iterator(_head-next)//单参数的构造支持隐式类型转化}const_iterator end()const{return _head;}list(){_head new Node;_head-prev _head;_head-next _head;sz 0;}list(const listT lt1){_head new Node;_head-prev _head;_head-next _head;sz 0;for (auto e : lt1){push_back(e);}}void swap( listT lt1){std::swap(_head, lt1._head);std::swap(sz, lt1.sz);}listT operator( listTlt1){swap(lt1);return *this;}void push_front(const T x){insert(begin(),x);}void pop_front(){erase(begin());}void push_back(const T x){尾插首先需要找到尾//Node* tail _head-prev;找到尾部后将新结点连接//Node* newnode new Node(x);//tail-next newnode;//newnode-prev tail;//_head-prev newnode;//newnode-next _head;insert(end(), x);}void pop_back(){erase(--end());}iterator insert(iterator pos,const T x){//最好还是转化成结点的指针这里访问迭代器不方便,这里就体现了为什么要用struct来定义迭代器让其成员共有Node* cur pos._node;Node* prev cur-prev;Node* newnode new Node(x);prev-next newnode;newnode-prev prev;newnode-next cur;cur-prev newnode;sz;return newnode;//返回新插入结点的位置}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;sz--;return next;}size_t size(){return sz;}~list(){clear();delete _head;_head nullptr;}void clear()//清空数据但不清哨兵位{iterator it begin();while (it ! end()){iterase(it);}sz 0;}private:Node* _head;//封装的是一个指向结点的指针size_t sz;};};
