文章目录list基本框架实现list的介绍1.结点的创建2.list的创建3.迭代器的实现(难点)介绍常见的迭代器list的迭代器实现list基本框架实现list的介绍它是带头的双向链表1.结点的创建相较于我们C语言初阶的链表的结点我们创建结点都是用个函数来做单独创建结点的操作现在我们学了类与对象和内存管理之后我们可以用类去封装结点templateclassTstruct_list_node{T data;_list_node*_prev;_list_node*_next;_list_node(constTvalT()):data(val),_prev(nullptr),_next(nullptr){}};用struct的原因是struct在c里面也能作为类去使用它与class的区别是当没有访问限定符时class是默认是私有成员而里面的成员变量默认为公有也就是有默认的public:去修饰,方便我们在其他类里面直接访问它的成员变量并且把结点写成类以后我们也可以用 new _list_node 去创建结点因为用new去扩容会调用类类型的构造函数注意我们现在写的类都需要是函数模板因为链表中可以存不同内置类型甚至是类类型2.list的创建templateclassTclasslist{public:typedef_list_node node;voidempty_init(){_headnewnode;_head-prev_head;_head-next_head;}list(){empty_init();}......//其他成员函数private:node*_head//头结点};list的基本框架就是存个头结点就行了后续增加结点直接在头结点尾插或头插就行代码剖析:为了节省精力可以把结点的类名改为 node typedef后的名字后既能用 _list_node也能用 node表示。 构造函数为什么拿一个函数接受创造头结点 因为后面在实现其他构造函数时避免频繁的写头结点的初始化因为其他的构造函数对要实例化的对象初始化时需要走初始化列表或者在成员变量给的缺省值对_head给缺省值行不通因为还要让头结点的两个指针开始指向自己其次每个构造函数写初始化列表的代码也很重复所以不如直接把头结点的初始化写在函数里面后续的其他构造函数能直接调用函数就行3.迭代器的实现(难点)介绍常见的迭代器回顾我们以前写的vector和string我们封装的迭代器都是用原生指针来完成的简单看一下迭代器的类型意思是我们不管说明类型的容器我们都能像指针一样实现 与* 解引用和判断是否相等在我们前面学的string和vector中我们自己实现的迭代器可以用原生指针来表示迭代器的行为因为它们储存数据是连续的地址天生就适合用指针封装成迭代器 指针的满足走向下一个位置对指针的解引用也能拿到数据所以可以用指针直接封装成iterator 迭代器vectorint::iterator itv.begin();while(it!v.end()){cout*it ;it;}但是list的指针指向的是一个个结点并且是不连续的地址无法做到对指针就到下一个结点解引用就是数据这里解引用是结点所以list不能对node* 进行简单的typedef就能实现迭代器所以我们需要对node* 进行类的封装在类里对** * 和 和!**还有其他的运算符进行重载将它们的行为改变成像vector和string一样的访问。list的迭代器实现一.迭代器框架实现templateclassTstruct__list_iterator{typedef_list_node node;node*_node;__list_iterator(node*Node):_node(Node){}}:代码剖析:首先目前的基本框架是这样的后面逐步会变化listint::iterator itl1.begin();首先迭代器的构建成员变量肯定要是结点指针因为后面的操作返回的肯定是结点这里没写的begin返回的是首结点所以构造函数的参数接受也要是结点指针类型二. 重载运算符的实现Toperator*(){return_node-data;}代码剖析:因为_node指向的是结点所以对*it得到的是里面的数据,所以对 *的重载函数就直接返回结点里的数据就行__list_iteratorToperator(){_node_node-_next;return*this;}代码剖析:操作是指向下一个结点所以通过next指针就可以找到下一个结点booloperator!(const__list_iteratorTit)const{return_node!it._node;}代码剖析:我们实现的操作是while(it!v.end()){cout*it ;it;}我们要遍历完链表故我们的终止条件就是迭代器走到_head的时候就停止end()里的函数就是返回头结点的三. 迭代器的基本构成与list的代码完善templateclassTstruct__list_iterator{typedef_list_node node;node*_node;__list_iterator(node*Node):_node(Node){}Toperator*(){return_node-data;}__list_iteratorToperator(){_node_node-_next;return*this;}while(it!v.end()){cout*it ;it;}}:templateclassTclasslist{public:typedef_list_nodeTnode;typedef__list_iteratorTiterator;iteratorbegin(){returniterator(_head-_next);}iteratorend(){returniterator(_head);}这里消化完就要开始进一步完善迭代器了这里已经是最基本的功能四.const_iterator和类类型参数一const_iterator我们知道一般打印数据是用const的迭代器那我们接下来一步步完善误区讲解有些人肯定想我直接这样不就行了listint::constiterator itl1.begin();可是这样写是修改const的本身为什么呢他不是在const的前面吗 typedef __list_iterator iterator; iterator是被typedef后的名称在在它前面加const其实是在后面的就相当于 node* const这是不能修改本身因为const的迭代器是它指向的内容不可以改但是它本身是可以移动的所以就不行Toperator*(){return_node-data;}我们本质是改这个函数 把T变为 const T 这样它的数据就不能改变其他函数是一样的功能。那我们不就可以增加个模板参数代表它就行了templateclassTclassRefstruct__list_iterator{typedef_list_node node;node*_node;__list_iterator(node*Node):_node(Node){}Refoperator*(){return_node-data;}templateclassTclasslist{public:typedef_list_nodeTnode;typedef__list_iteratorT,Titerator;typedef__list_iteratorT,constTconst_iterator;增加的def就表示T 和constT 两个不同的类型去让编译器自行生成不同函数模板参数形成的类主要两个不同的类的区别就是重载*的这个函数二类类型参数那如果我的list是数据类型是类类型呢比如下面这个structpos{int_x;int_y;pos(intx,inty):_x(x),_y(y){}listposl1;//假设已实现push_back;push_back({11}) listpos::iterator itl1.begin():while(it!v.end()){cout*it ;it;}:如果直接这样打印的话会直接报错因为你*it的数据是 pos的一个类类型并不是具体数据就会报错我们其实要的是pos里的_x和_y,所以我们的一种方法是直接改while(it!v.end()){cout*it._x(*it)._yendl;;it;}:但我们it是迭代器是结点的地址我们可能更习惯用 - 用这个去访问那我们就要去重载-这个并且返回的是pos的地址才能用-去访问数据所以增加个模板参数因为类类型很多templateclassTclassRefclassPtrPtroperator-(){return_node-data;这样写就可以直接 it--_x 访问数据但是这些会报错要省略掉最后一个-可能是为了好看编译器就自动省略掉,实际 it-_x,这样写就能打印pos的_x,但你要知道-这里的-是重载的并且还省略了一个-所以完整迭代器的代码就是templateclassT,classRef,classPtrstruct__list_iterator{typedef_list_nodeTnode;typedef__list_iteratorT,Ref,Ptrself;node*_node;self(node*Node):_node(Node){}Refoperator*(){return_node-data;}selfoperator(){_node_node-_next;return*this;}selfoperator(int){selftmp(*this);_node_node-_next;returntmp;}booloperator!(constselfit)const{return_node!it._node;}selfoperator--(){_node_node-_prev;return*this;}selfoperator--(int){selftmp(*this);_node_node-_prev;returntmp;}Ptroperator-(){return_node-data;}};templateclassTclasslist{public:typedef_list_nodeTnode;typedef__list_iteratorT,T,T*iterator;typedef__list_iteratorT,constT,constT*const_iterator;iteratorbegin(){returniterator(_head-_next);}iteratorend(){returniterator(_head);}const_iteratorbegin()const{returnconst_iterator(_head-_next);}const_iteratorend()const{returnconst_iterator(_head);}voidempty_init(){_headnewnode;_head-_prev_head;_head-_next_head;}list(){empty_init();}注意typedef __list_iteratorT,Ref,Ptr self; 在自己的类里面也可以对自己 取名 方便是返回迭代器的时候频繁写__list_iteratorT,Ref,Ptr 胆识好像在类里面返回自己的话可以省略T,Ref,Ptr 这个模板但是初学者比如我自己我还是愿意加上,在在里面改个简单的名字就行。 里面的重载-- 和后置和–都是类似的就不再介绍。后面的增删查改在有了迭代器的基础上就很快就能写出来持续更新中…