官网和网站的区别,济宁网络,下载爱南宁乘车,南昌网站开发培训学校目录
一、list的概念引入
1、vector与list的对比 2、关于struct和class的使用
3、list的迭代器失效问题 二、list的模拟实现
1、list三个基本函数类
2、list的结点类的实现
3、list的迭代器类的实现
3.1 基本框架
3.2构造函数
3.3 operator*
3.4 operator-
3…
目录
一、list的概念引入
1、vector与list的对比 2、关于struct和class的使用
3、list的迭代器失效问题 二、list的模拟实现
1、list三个基本函数类
2、list的结点类的实现
3、list的迭代器类的实现
3.1 基本框架
3.2构造函数
3.3 operator*
3.4 operator-
3.5 operator前置和--与后置和--
3.5 operator与operator!
4、list类的实现 4.1 基本框架
4.2 构造函数
4.2 begin()和end()
4.3 拷贝构造
4.4 clear
4.5 operator
4.6 析构函数 4.7 insert
4.8 push_back 和 push_front
4.9 erase
4.10 pop_back 和 pop_front
三、完整源代码
list.h: test.cpp: 一、list的概念引入
1、vector与list的对比 两者的区别十分类似于顺序表和链表的区别 2、关于struct和class的使用 C中的struct和class的唯一区别在于默认访问限定符即你不写public、private这种访问限定符不同struct默认为公有public而class默认为私有private一般情况成员部分私有部分共有就用class所有成员都开放或共有就用struct 所以下文写的节点和迭代器类都用struct是因为struct中的成员函数默认为公有了也不用写public了但是你用class就要写个public 3、list的迭代器失效问题 list本质带头双向循环链表 支持操作接口的角度分迭代器的类型单向forward_list、双向list、随机vector 从使用场景的角度分迭代器的类型正向迭代器反向迭代器const迭代器 迭代器失效本质是内存空间的问题失效原因 1、增容完还指向旧空间 2、节点已经被释放list里面 list的erase迭代器失效 注意删除不会报错迭代器失效也不会报错是删除以后迭代器失效了是去访问失效的迭代器才会报错 插入知识点库里面的find实现可不看 二、list的模拟实现
1、list三个基本函数类 list本质是一个带头双向循环链表 模拟实现list要实现下列三个类 ①、模拟实现结点类 ②、模拟实现迭代器的类 ③、模拟list主要功能的类 list的类的模拟实现其基本功能增删等操作要建立在迭代器类和结点类均已实现好的情况下才得以完成。 2、list的结点类的实现 因为list的本质为带头双向循环链表所以其每个结点都要确保有下列成员 前驱指针后继指针data值存放数据 而结点类的内部只需要实现一个构造函数即可。 //1、结点类
templateclass T
struct __list_node//前面加__是命名习惯,一般这么写表示是给别人用的
{//前驱指针和后驱指针__list_nodeT* _next;//C中可不写struct直接用名定义但注意这里还要加类型__list_nodeT* _prev;T _data;//存节点的值//构造函数__list_node(const T val T())//给一个缺省值T():_next(nullptr), _prev(nullptr), _data(val){}
}; ①、为什么是__list_nodeT 首先C中用struct定义时可不加struct重点是这里用了一个类模板类模板的类名不是真正的类型即__list_node不是真正的类型定义变量时__list_nodeT这种才是真正的类型也就是用类模板定义变量时必须 指定对应的类型 3、list的迭代器类的实现 因为list其本质是带头双向循环链表而链表的物理空间是不连续的是通过结点的指针顺次链接我们不能像先前的string和vector一样直接解引用去访问其数据结点的指针解引用还是结点结点指针还是结点指针而string和vector的物理空间是连续的所以这俩不需要实现迭代器类可以直接使用。 为了能让list像vector一样解引用后访问对应节点中的值访问到下一个数据我们需要单独写一个迭代器类的接口实现在其内部进行封装补齐相应的功能而这就要借助运算符重载来完成。 注迭代器封装后是想模拟指针的行为 3.1 基本框架 templateclass T,class Ref,class Ptr
struct __list_iterator
{typedef __list_nodeT Node;typedef __list_iteratorT, Ref, Ptr Self;Node* _node;
} ①、迭代器类模板为什么要三个参数 若只有普通迭代器的话一个class T参数就够了但因为有const迭代器原因需要加两个参数两个参数名Refreference:引用和Ptrpointer:指针名字怎么起都行但这种有意义的名字是很推荐的即这两个参数一个让你传引用一个让你传指针具体等下文讲到const迭代器再说 ②、迭代器类到底是什么 迭代器类就一个节点的指针变量_node但是因为我们要运算符重载等一系列操作不得不把list的迭代器写成类完成那些操作list的迭代器才能正确的到下一位置解引用访问节点的值 ③、节点指针和迭代器的区别 3.2构造函数 //迭代器的构造函数只需要一个指针构造__list_iterator (Node* node):_node(node){ }3.3 operator* //*it调用的是函数返回节点中的值Ref operator*(){//出了作用域还在引用返回return _node-_data;}①、 返回值为什么是Ref Ref是模板参数因为迭代器类的模板参数Ref传入的要么是T要么是const T就是为了const迭代器和普通迭代器的同时实现底层就是这么实现的意义就是一个只读一个可读可写 注比如之前讲的vector的迭代器*it假设it是迭代器变量就是拿到对应的值那么list的迭代器也要同理解引用迭代器就是为了访问对应位置的值那么list只要通过迭代器返回对应节点的值就好了*it我们是就想要对应的值 3.4 operator- Ptr operator-(){return _node-_data;} ①、为什么需要operator- 本质因为自定义类型需要那需从list存的类型是个自定义类型说起以Date类型为例 若list存了个自定义类型的Date类程序错误因为我们并没有重载Date类的operator若是内置类型的话才可以正常输出那写一个operator重载吗不因为你无法确定要用哪些类也不能每个类都写operator那怎么办我们访问Date类本质是想访问它内置类型int的_year、_month和_day吧那我们不妨写个专属于自定义类型的operator-因为内置类型只需要*it就可以直接输出了但自定义类型不可以直接输出利用operator-直接访问类的成员变量而内置类型可以直接输出 故从根源上解决问题 在迭代器中实现个operator- Ptr是迭代器的模板参数我们用来作为T*或const T*的 3.5 operator前置和--与后置和-- //it;迭代器本质就是指针往后移加完后还应是个迭代器Self operator(){_node _node-_next;return *this;}//it;Self operator(int)//加参数以便于区分前置{Self tmp(*this);//拷贝构造tmp_node _node-_next;//直接让自己指向下一个结点即可实现return tmp;//注意返回tmp才是后置}//--it;Self operator--(){_node _node-_prev;//让_node指向上一个结点即可实现--return *this;}//it--;Self operator--(int)//记得传缺省值以区分前置--{Self tmp(*this);//拷贝构造tmp_node _node-_prev;return tmp;} ①、迭代器对于list是什么意思 迭代器的意思就是想让其指向下一个节点--正好相反为了区分前置和后置--我们会用函数重载也就是多一个“没用的”参数int这个参数没什么用只是为了区分与-- 3.5 operator与operator! //it ! end() bool operator!(const Self it){//迭代器是否相等只要判断对应节点地址是否相等即可return _node ! it._node;}bool operator(const Self it){return _node it._node;} ①、两个迭代器怎么比较的 迭代器中就一个成员变量_node节点指针只要比较当前的节点指针是否相同即可个人认为这个操作意义不大 4、list类的实现 在结点类和迭代器类都实现的前提下就可实现list主要功能增删等操作的实现 4.1 基本框架 //3、链表类
templateclass T
class list
{typedef __list_nodeT Node;
public:typedef __list_iteratorT,T,T* iterator;typedef __list_iteratorT,const T,const T* const_iterator;private:Node* _head;//头结点
}①、const_iterator(const迭代器的介绍) 我们知道const_iterator在begin()和end()中的返回值是需要用到的其主要作用就是当迭代器只读时使用 因为普通迭代器和const迭代器的实现区别仅仅在于内部成员函数的返回值不同难道重写一遍吗不用我们模板参数多两个就好了一个是引用class RefT或const T一个是指针class PtrT*或const T*当Ref时const T就是const迭代器的调用当Ref时T 时就是普通迭代器的调用这就利用模板实现了两个迭代器的同时实现 4.2 构造函数 //带头双向循环链表的构造函数
list()
{_head new Node;_head-_next _head;_head-_prev _head;
} 解释我们开辟一个头结点然后使其处于一个对应的初始状态即可 4.2 begin()和end() iterator begin()
{//第一个位置应该是头结点的下一个节点return iterator(_head-_next);//用匿名对象构造iterator类型的
}
iterator end()
{//最后一个数据的下一个位置应该是第一个节点即头结点return iterator(_head);
}const_iterator begin()const
{return const_iterator(_head-_next);
}
const_iterator end()const
{return const_iterator(_head);
} ①、关于匿名构造的理解 比如 iterator(_head-_next); iterator是个类模板类型它被typedef过的那不应该实例化一个对象再构造吗这里没有用是因为这里是匿名对象的构造这里这么用比较方便 4.3 拷贝构造 //拷贝构造传统写法
list(const listT lt)
{_head new Node;//开辟一样的头结点_head-_next _head;_head-_prev _head;//1、用迭代器遍历/*const_iterator it lt.begin();while (it ! lt.end()){push_back(*it);it;}*///2、范围for遍历//遍历lt1把lt1的元素push_back到lt2里头for (auto e : lt){push_back(e);//自动开辟新空间完成深拷贝}
} 解释list的拷贝构造跟vector不同它的拷贝是拷贝一个个节点因为不连续的物理空间 那么我们可以用迭代器拿到list的一个个节点 ①、为什么有的拷贝构造需初始化operator不需要 以string的模拟实现为例 这里为什么s2要初始化 是因为string的模拟实现有交换操作而list的传统写法无需交换开辟一个头结点即可 因为s2是要被拷贝构造出来的没被拷贝构造前还没存在然后s2要跟tmp交换如果也就是tmp得到s2的数据如果s2之前没初始化析构销毁就出问题了因为没初始化是随机值 但是赋值不一样赋值是两个对象都存在不存在随机值问题所以不用一上来就初始化 还有一种现代写法先不介绍 4.4 clear void clear()
{//clear不删除头结点因为万一删除了头结点你还想插入数据怎么办iterator it begin();while (it ! end()){it erase(it);}
} ①、 it erase(it)什么意思? 防止迭代器失效因为erase返回的是被删除位置的下一位置比如删除pos位置的pos位置被删除后it都不用动erase算自动指向下一位置了故用it接收若不接收迭代器失效 4.5 operator //赋值运算符重载传统写法//lt1 lt3//listT operator(const listT lt)//{// if (this ! lt)// {// clear();//先释放lt1// for (auto e : lt)// push_back(e);// }// return *this;//}//赋值运算符重载现代写法//lt1 lt3listT operator(listT lt)//套用传值传参去拷贝构造完成深拷贝{swap(_head,lt._head);//交换两个list的头结点即可//lt出了作用域析构函数销毁lt1原来的链表一举两得//swap(lt);return *this;}注传统写法要先把被赋值的对象先释放然后利用push_bak尾插push_back在下文说明 4.6 析构函数 //析构函数~list(){clear();//删除除头结点以外的节点delete _head;//删去哨兵位头结点_head nullptr;} 4.7 insert //insert插入pos位置之前
iterator insert(iterator pos, const T x)
{Node* newnode new Node(x);//创建新的结点Node* cur pos._node; //迭代器pos处的结点指针Node* prev cur-_prev;//prev newnode cur//链接prev和newnodeprev-_next newnode;newnode-_prev prev;//链接newnode和curnewnode-_next cur;cur-_prev newnode;//返回新插入元素的迭代器位置return iterator(newnode);
} ①、返回参数为什么是iterator 本质是为了防止迭代器失效问题 注insert指的是插入到指定位置的前面 4.8 push_back 和 push_front //尾插
void push_back(const T x)
{Node* tail _head-_prev;//找尾Node* newnode new Node(x);//创建一个新的结点//_head tail newnode//使tail和newnode构成循环tail-_next newnode;newnode-_prev tail;//使newnode和头结点_head构成循环newnode-_next _head;_head-_prev newnode;}
//头插
void push_front(const T x)
{insert(begin(), x);
} 4.9 erase //erase
iterator erase(iterator pos)
{assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;//prev cur next//链接prev和nextprev-_next next;next-_prev prev;//delete删去结点,因为每一个节点都是动态开辟出来的delete cur;//返回被删除元素后一个元素的迭代器位置//return next;return iterator(next);
} ①、 返回值问题 erase的返回值返回的是被删除位置的下一位置 4.10 pop_back 和 pop_front //尾删
void pop_back()
{erase(--end());//erase(iterator(_head-prev));//构造个匿名对象
}
//头删
void pop_front()
{erase(begin());
} 最后 list的排序意义不大因为实际生活中我们都是对数组等排序
三、完整源代码
list.h:
#pragma oncenamespace mz
{//1、结点类templateclass Tstruct __list_node//前面加__是命名习惯,一般这么写表示是给别人用的{//前驱指针和后驱指针__list_nodeT* _next;//C中可不写struct直接用名定义但注意这里还要加类型__list_nodeT* _prev;T _data;//存节点的值//构造函数__list_node(const T val T())//给一个缺省值T():_next(nullptr), _prev(nullptr), _data(val){}};//2、迭代器类//__list_iteratorT,T,T* - iterator//__list_iteratorT,const T,const T* - const_iteratortemplateclass T,class Ref,class Ptrstruct __list_iterator{typedef __list_nodeT Node;typedef __list_iteratorT, Ref, Ptr Self;Node* _node;//迭代器的构造函数只需要一个指针构造__list_iterator (Node* node):_node(node){ }//*it调用的是函数返回节点中的值Ref operator*(){//出了作用域还在引用返回return _node-_data;}Ptr operator-(){return _node-_data;}//it;迭代器本质就是指针往后移加完后还应是个迭代器Self operator(){_node _node-_next;return *this;}//it;Self operator(int)//加参数以便于区分前置{Self tmp(*this);//拷贝构造tmp_node _node-_next;//直接让自己指向下一个结点即可实现return tmp;//注意返回tmp才是后置}//--it;Self operator--(){_node _node-_prev;//让_node指向上一个结点即可实现--return *this;}//it--;Self operator--(int)//记得传缺省值以区分前置--{Self tmp(*this);//拷贝构造tmp_node _node-_prev;return tmp;}//it ! end() bool operator!(const Self it){//迭代器是否相等只要判断对应节点地址是否相等即可return _node ! it._node;}bool operator(const Self it){return _node it._node;}};//3、链表类templateclass Tclass list{typedef __list_nodeT Node;public:typedef __list_iteratorT,T,T* iterator;typedef __list_iteratorT,const T,const T* const_iterator;iterator begin(){//第一个位置应该是头结点的下一个节点return iterator(_head-_next);//用匿名对象构造iterator类型的}iterator end(){//最后一个数据的下一个位置应该是第一个节点即头结点return iterator(_head);}const_iterator begin()const{return const_iterator(_head-_next);}const_iterator end()const{return const_iterator(_head);}//带头双向循环链表的构造函数list(){_head new Node;_head-_next _head;_head-_prev _head;}//拷贝构造传统写法list(const listT lt){_head new Node;//开辟一样的头结点_head-_next _head;_head-_prev _head;//1、用迭代器遍历/*const_iterator it lt.begin();while (it ! lt.end()){push_back(*it);it;}*///2、范围for遍历//遍历lt1把lt1的元素push_back到lt2里头for (auto e : lt){push_back(e);//自动开辟新空间完成深拷贝}}//赋值运算符重载传统写法//lt1 lt3//listT operator(const listT lt)//{// if (this ! lt)// {// clear();//先释放lt1// for (auto e : lt)// push_back(e);// }// return *this;//}//赋值运算符重载现代写法//lt1 lt3listT operator(listT lt)//套用传值传参去拷贝构造完成深拷贝{swap(_head,lt._head);//交换两个list的头结点即可//lt出了作用域析构函数销毁lt1原来的链表一举两得//swap(lt);return *this;}//析构函数~list(){clear();//删除除头结点以外的节点delete _head;//删去哨兵位头结点_head nullptr;}void clear(){//clear不删除头结点因为万一删除了头结点你还想插入数据怎么办iterator it begin();while (it ! end()){it erase(it);}}//尾插void push_back(const T x){Node* tail _head-_prev;//找尾Node* newnode new Node(x);//创建一个新的结点//_head tail newnode//使tail和newnode构成循环tail-_next newnode;newnode-_prev tail;//使newnode和头结点_head构成循环newnode-_next _head;_head-_prev newnode;}//头插void push_front(const T x){insert(begin(), x);}//insert插入pos位置之前iterator insert(iterator pos, const T x){Node* newnode new Node(x);//创建新的结点Node* cur pos._node; //迭代器pos处的结点指针Node* prev cur-_prev;//prev newnode cur//链接prev和newnodeprev-_next newnode;newnode-_prev prev;//链接newnode和curnewnode-_next cur;cur-_prev newnode;//返回新插入元素的迭代器位置return iterator(newnode);}//eraseiterator erase(iterator pos){assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;//prev cur next//链接prev和nextprev-_next next;next-_prev prev;//delete删去结点,因为每一个节点都是动态开辟出来的delete cur;//返回被删除元素后一个元素的迭代器位置//return next;return iterator(next);}//尾删void pop_back(){erase(--end());//erase(iterator(_head-prev));//构造个匿名对象}//头删void pop_front(){erase(begin());}private:Node* _head;//头结点};void test1(){listintlt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);//类外访问迭代器需要指定类域类内访问可直接访问listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;}struct Date{int _year 0;int _month 1;int _day 1;};void test2(){Date* p2 new Date;*p2;//取到的是Datep2-_year;//取到的是Date类中的成员变量listDatelt;lt.push_back(Date());lt.push_back(Date());//list存了个日期类(自定义类型)的类型listDate::iterator it lt.begin();while (it ! lt.end()){//cout *it ;cout it-_year - it-_month - it-_day endl;it;}cout endl;}void print_list(const listint lt){listint::const_iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;}void test3(){listintlt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);listint lt2(lt1);print_list(lt2);listintlt3;lt3.push_back(10);lt3.push_back(20);lt3.push_back(30);lt3.push_back(40);lt1 lt3;print_list(lt1);}
} test.cpp:
#includeiostream
#includeassert.h
using namespace std;
#includelist.hint main()
{//mz::test1();mz::test3();return 0;
}
