建设银行网站收款怎么打明细,北京++网站建设咨询顾问公司,网站建设哪个平台最好,常州哪些网站公司做的好本篇博客详细介绍list的实现细节讲解#xff0c;并且在文章末对list和vector#xff0c;string进行区分和复习 list的基本结构就是双向带头循环链表#xff0c;链表和顺序表的差别我们在前面数据结构的时候早就学过了#xff0c;不再赘述 在使用stl库里面list时细节讲解并且在文章末对list和vectorstring进行区分和复习 list的基本结构就是双向带头循环链表链表和顺序表的差别我们在前面数据结构的时候早就学过了不再赘述 在使用stl库里面list时要加上头文件 快速高效编辑查找元素 用vector 大批量增删数据 用list 目录 1.基本框架的实现
2.很细节的函数实现
3.vector和list对比
4.迭代器失效 1.基本框架的实现
定义模板T 还是表示每个节点data的类型
首先我们需要思考
这个链表的每个节点的类型是什么_list_nodeT
节点里面包含什么当然 不要忘记构造函数 list的成员类型基本上都是迭代器当然链表都是在用指针在玩这里的迭代器和我们之前写顺序表就很不一样因为之前是连续存储的结构可以用[ ]的方式所以迭代器是原生指针数组的结构正好支持迭代器行为
但是这里原生指针的类型是node* 不能满足迭代器的行为
但是我们可以用封装运算符重载搞定 我们实现最基本的push——back()功能之后基本上的框架就搭好了
void push_back(const T x){node* newnode new node(x);node* tail head-_prev;//head tail newnodetail-_next newnode;newnode-_next head;newnode-_prev tail;head-_prev newnode;} 目前的代码
namespace wrt
{template typename Tstruct _list_node{_list_nodeT* _prev;_list_nodeT* _next;T data;_list_node(const T x) //用x初始化节点:_prev(nullptr),_next(nullptr),data(x){}};template class Tstruct __list_iterator{typedef _list_nodeT node;node* _pnode;__list_iterator(node* p):_pnode(p){}T operator*(){return _pnode-data;}__list_iteratorT operator(){_pnode _pnode-_next;return *this;}bool operator!(const __list_iteratorT it){return _pnode ! it._pnode;}};template typename Tclass list{typedef _list_nodeT node;public:typedef __list_iteratorT iterator;iterator begin(){return iterator(head-_next);}iterator end(){return iterator(head);}list(){head new node(T());head-_next head;head-_prev head;}void push_back(const T x){node* newnode new node(x);node* tail head-_prev;//head tail newnodetail-_next newnode;newnode-_next head;newnode-_prev tail;head-_prev newnode;}private :node* head;};void test(){listint lt;lt.push_back(1);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);lt.push_back(7);listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;}
}
2.值得注意的函数
list为什么要支持sort不可以使用algorithm文件里面的吗 算法库里面使用了first-last 但是很显然list是不支持节点相减的 2.很细节的函数实现
一个合格的list是支持增删查改的
push_back已经实现过了
下面看insert() 注意到它是有返回值的 返回迭代器在头部增加数据当然是可以的
iterator insert(iterator pos, const T x){node* newnode new node(x);node* cur pos._pnode;node* prev cur-_prev;//prev newnode curprev-_next newnode;newnode-_next cur;newnode-_prev prev;cur-_prev newnode;return iterator(newnode);} 对应的erase 也是有返回值并且不能在头结点位置删除哨兵位不能动
iterator erase(iterator pos){assert(pos ! end());node* cur pos._pnode;node* prev cur-_prev;node* next cur-_next;//prev cur nextprev-_next next;next-_prev prev;delete cur;return iterator(next);}
那么头尾的增删就可以复用啦
void pop_back(){erase(--end());}
void pop_front(){erase(begin());}
void push_back(const T x){//node* newnode new node(x);//node* tail head-_prev;head tail newnode//tail-_next newnode;//newnode-_next head;//newnode-_prev tail;//head-_prev newnode;insert(end(), x);}
void push_front(const T x){insert(begin(), x);}
然后就是clear注意头结点不能删 void clear(){iterator it begin();while(it!end()){iterase(it);}//头节点不能删除}
析构函数
~list(){clear();//此时需要把头节点也删除delete head;head nullptr;}
下面是拷贝构造
//拷贝构造
//l2l1listT operator(const listT l){if (*this ! l){clear();for (const autoe :l){push_back(e);}}return *this;}
为了写着更方便把头结点的开辟封装成函数
void empty_initialize(){head new node(T());head-_next head;head-_prev head;}
//l2(l1)list(const list T l){empty_initialize();for (const auto e : l){push_back(e);}}
迭代器还有const版本怎么实现
最简单想到的就是直接在iterator类里面加上一个const修饰*运算符重载 template class Tstruct __list_iterator{typedef _list_nodeT node;node* _pnode;__list_iterator(node* p):_pnode(p){}T operator*(){return _pnode-data;}//在同一个类里面实现就是不行因为const——iterator只能遍历不能/* const T operator*() const {return _pnode-data;}*/__list_iteratorT operator(){_pnode _pnode-_next;return *this;}bool operator!(const __list_iteratorT it){return _pnode ! it._pnode;}};
但是这个真的对么很显然不对因为iterator可以遍历 但是const_iterator只能遍历无法
所以很自然想到写在两个类里面
template class Tstruct __list_iterator{typedef _list_nodeT node;node* _pnode;__list_iterator(node* p):_pnode(p){}T operator*(){return _pnode-data;}//在同一个类里面实现就是不行因为const——iterator只能遍历不能/* const T operator*() const {return _pnode-data;}*/__list_iteratorT operator(){_pnode _pnode-_next;return *this;}bool operator!(const __list_iteratorT it){return _pnode ! it._pnode;}};template class Tstruct __list_const_iterator{typedef _list_nodeT node;node* _pnode;__list_const_iterator(node* p):_pnode(p){}const T operator*() const {return _pnode-data;}__list_const_iteratorT operator(){_pnode _pnode-_next;return *this;}bool operator!(const __list_const_iteratorT it){return _pnode ! it._pnode;}}; 这两个类只在*运算符重载 还有名称上有区别
但是这是我们的想法看一下源码就知道大佬果然是大佬
直接用两个模板参数解决问题 template typename T, typename Refstruct __list_iterator{typedef _list_nodeT node;typedef __list_iteratorT, Ref Self;node* _pnode;__list_iterator(node* p):_pnode(p){}Ref operator*(){return _pnode-data;}//在同一个类里面实现就是不行因为const——iterator只能遍历不能/* const T operator*() const {return _pnode-data;}*/Self operator(){_pnode _pnode-_next;return *this;}Self operator--(){_pnode _pnode-_prev;return *this;}bool operator!(const Self it){return _pnode ! it._pnode;}};
拷贝构造可有现代写法哦此时同样需要一个构造函数用迭代器初始化的 l2l1相比较来说现代写法就是多一个工具人帮助复刻l1然后把数据交换给l2最后他自己牺牲....
首先是构造函数用迭代器实现的
template class InputIteratorlist(InputIterator first, InputIterator last){empty_initialize();while(first ! last){push_back(*first);first;}} 然后是swap void swap(const listT l){std::swap(head, l.head); //两个链表交换只需交换头结点}
现代写法
//l2(l1)list(const listT l){empty_initialize();listT tmp(l.begin(), l.end());swap(tmp); //tmp出作用域销毁} l2l1 这是对于一个已经存在的对象l1无需构造头结点
//l2l1 这是对于一个已经存在的对象l1无需构造头结点list T operator(const listT l){swap(l);return *this;} 想象一个场景你需要统计size当然这种操作不能频繁进行因为每一次都要从头开始遍历有很多消耗那么最简单的办法是什么成员变量加上size 现在凸显出复用的好处了我虽然实现到一半开始想加上size也只需要改动几个函数就可以完成功能 其他全是复用爽歪歪 可以用size实现两个函数 size_t _size(){return size;}bool rmpty(){//return head-nexthead;return size0;} C兼容c是有前置和后置的区分于有些语言觉得前置后置很麻烦就删去后置
完善一下前面对于迭代器的运算符操作 //前置Self operator(){_pnode _pnode-_next;return *this;}//后置Self operator(int){Self tmp(*this);_pnode _pnode-_next;return tmp;}//前置Self operator--(){_pnode _pnode-_prev;return *this;}//后置Self operator--(int ){Self tmp(*this);_pnode _pnode-_prev;return tmp;} 看起来写成这样是不是很完美但是看一个问题
struct Pos{size_t _row;size_t _col;Pos(size_t row0,size_t col0) //一定要时刻记着写一个默认构造:_row(row),_col(col){}};void test(){listPos lt;Pos p1(1, 1);lt.push_back(p1);lt.push_back(p1);lt.push_back(p1);lt.push_back(Pos(2, 2)); //匿名函数lt.push_back(Pos(3, 3));listPos::iterator it lt.begin();while (it ! lt.end()){//it-_row;cout *it ;}}
思考一下有什么问题 这很尴尬首先我们思考一下为什么C支持cout因为可以对内置类型可以直接识别然后输出但是这里的it是个迭代器 其实这样就可以啦只需要重载一个-这个运算符
但是我们只有T这个模板类型没有T* 然后运算符-重载这样写
Ptr operator-(){return _pnode-data;}
注意脑子一定要清醒我们提供类T是为了list每个节点的数据类型Ref是T当然还有一个const TPtr是T*(还有const T*
这里面也体现出我们typedef的智慧 这个模板我们改了很多次但是我typedef之后直接修改类型不需要改名字都是Self 所以直接-访问就可以啦
他的原理就是 3.vector和list对比 4.迭代器失效
vectorinsert和erase都有失效问题
lsiterase会失效
那么string会有失效问题吗当然insert和erase都有和vecor类似但是一般不关注string失效因为string的insert和erase常用接口都是下标支持的迭代器用的少 最后我们的list实现总代码
.h文件
#pragma once
namespace wrt
{template typename Tstruct _list_node{_list_nodeT* _prev;_list_nodeT* _next;T data;_list_node(const T x) //用x初始化节点:_prev(nullptr),_next(nullptr),data(x){}};template typename T, typename Ref,class Ptrstruct __list_iterator{typedef _list_nodeT node;typedef __list_iteratorT, Ref,Ptr Self;node* _pnode;__list_iterator(node* p):_pnode(p){}Ref operator*(){return _pnode-data;}Ptr operator-(){return _pnode-data;}//在同一个类里面实现就是不行因为const——iterator只能遍历不能/* const T operator*() const {return _pnode-data;}*///前置Self operator(){_pnode _pnode-_next;return *this;}//后置Self operator(int){Self tmp(*this);_pnode _pnode-_next;return tmp;}//前置Self operator--(){_pnode _pnode-_prev;return *this;}//后置Self operator--(int ){Self tmp(*this);_pnode _pnode-_prev;return tmp;}bool operator!(const Self it){return _pnode ! it._pnode;}};/* template class Tstruct __list_const_iterator{typedef _list_nodeT node;node* _pnode;__list_const_iterator(node* p):_pnode(p){}const T operator*() const {return _pnode-data;}__list_const_iteratorT operator(){_pnode _pnode-_next;return *this;}bool operator!(const __list_const_iteratorT it){return _pnode ! it._pnode;}};*/template typename Tclass list{typedef _list_nodeT node;public://typedef __list_iteratorT iterator;//typedef __list_const_iteratorT const_iterator;typedef __list_iteratorT,T,T* iterator;typedef __list_iteratorT,const T,T* const_iterator;size_t _size(){return size;}bool rmpty(){//return head-nexthead?return size 0 ;}iterator begin(){return iterator(head-_next);}iterator end(){return iterator(head);}const_iterator begin() const {return iterator(head-_next);}const_iterator end() const {return iterator(head);}void push_back(const T x){//node* newnode new node(x);//node* tail head-_prev;head tail newnode//tail-_next newnode;//newnode-_next head;//newnode-_prev tail;//head-_prev newnode;insert(end(), x);}void push_front(const T x){insert(begin(), x);}~list(){clear();//此时需要把头节点也删除delete head;head nullptr;size 0;}//拷贝构造//l2l1/*listT operator(const listT l){if (*this ! l){clear();for (const autoe :l){push_back(e);}}return *this;}*/void empty_initialize(){head new node(T());head-_next head;head-_prev head;size 0;}list(){empty_initialize();}//l2(l1)/* list(const list T l){empty_initialize();for (const auto e : l){push_back(e);}}*///拷贝构造的现代写法template class InputIteratorlist(InputIterator first, InputIterator last){empty_initialize();while (first ! last){push_back(*first);first;}}void swap(const listT l){std::swap(head, l.head); //两个链表交换只需交换头结点}//l2(l1)list( listT l){empty_initialize();listT tmp(l.begin(), l.end());swap(tmp); //tmp出作用域销毁}//l2l1 这是对于一个已经存在的对象l1无需构造头结点list T operator(const listT l){swap(l);return *this;}void clear(){iterator it begin();while(it!end()){iterase(it);}//头节点不能删除size 0;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator insert(iterator pos, const T x){node* newnode new node(x);node* cur pos._pnode;node* prev cur-_prev;//prev newnode curprev-_next newnode;newnode-_next cur;newnode-_prev prev;cur-_prev newnode;size;return iterator(newnode);}iterator erase(iterator pos){assert(pos ! end());node* cur pos._pnode;node* prev cur-_prev;node* next cur-_next;//prev cur nextprev-_next next;next-_prev prev;delete cur;--size;return iterator(next);}private :node* head;size_t size;};struct Pos{size_t _row;size_t _col;Pos(size_t row0,size_t col0) //一定要时刻记着写一个默认构造:_row(row),_col(col){}};void test(){listPos lt;Pos p1(1, 1);lt.push_back(p1);lt.push_back(p1);lt.push_back(p1);lt.push_back(Pos(2, 2)); //匿名函数lt.push_back(Pos(3, 3));listPos::iterator it lt.begin();while (it ! lt.end()){// cout *it ;//cout it.operator-()-_row : it-_col endl;cout it-_row : it-_col : endl;}}/*void test(){listint lt;lt.push_back(1);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);lt.push_back(7);lt.insert(lt.begin(), 5);lt.erase(lt.begin());lt.push_back(40);listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;cout lt._size() endl;}*/
} .cpp文件
#define _CRT_SECURE_NO_WARNINGS
#include iostream
#include list
#include assert.h
using namespace std;
#include 标头.h
int main()
{wrt::test();return 0;
}
