学做网站的书哪些好,电子商务网站设计包括哪些内容,wordpress 导入 媒体,规划一个电子商务网站本期我们来讲解list#xff0c;有了string和vector的基础#xff0c;我们学习起来会快很多
目录
list介绍
编辑
list常用接口 insert
erase
reverse
sort
merge unique
remove
splice 模拟实现
基础框架
构造函数 push_back
迭代器 常见问题
const迭代器
…本期我们来讲解list有了string和vector的基础我们学习起来会快很多
目录
list介绍
编辑
list常用接口 insert
erase
reverse
sort
merge unique
remove
splice 模拟实现
基础框架
构造函数 push_back
迭代器 常见问题
const迭代器
insert
erase
push和pop
size
析构和clear
拷贝构造
赋值
全部代码 本期内容需要比较扎实的基础
list介绍 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。 2. list 的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。 3. list 与 forward_list 非常相似最主要的不同在于 forward_list 是单链表只能朝前迭代已让其更简单高效。 4. 与其他的序列式容器相比 (array vector deque) list 通常在任意位置进行插入、移除元素的执行效率更好。 5. 与其他序列式容器相比 list 和 forward_list 最大的缺陷是不支持任意位置的随机访问比如要访问 list的第6 个元素必须从已知的位置 ( 比如头部或者尾部 ) 迭代到该位置在这段位置上迭代需要线性的时间开销list 还需要一些额外的空间以保存每个节点的相关联信息 ( 对于存储类型较小元素的大 list 来说这可能是一个重要的因素) 简单来说list就是带头双向循环列表 我们先简单看看如何使用
list常用接口
list的迭代器啦构造函数析构函数这些跟我们前面学的都是一样的大家稍微看看文档即可这里就不细讲了 不过list不一样的是它有头插头删尾插尾删这些和我们以前用C语言实现的是一样的 insert 我们从vector开始insert里的参数都不是pos而是迭代器了 我们之前使用vector时是可以使用迭代器一个数的而list是不行的因为vector是数组是连续的空间而list是链表 是一个个节点 我们想在5的位置插入是需要手动让迭代器走的然后再插入
我们上面插入了12345如果我们想在数字3前面插入数据是需要使用find的但是我们看文档list是没有提供find的我们在vector里说过find属于算法通过迭代器来和算法联系起来我们通过统一的方法而不用关注容器底层是如何实现的 我们来看find的查找它的循环条件是firstlast而不是小于我们用while来进行遍历也使用的是begin!end而不是小于因为后面节点的地址不一定比前面小
通过迭代器不止是vectorlist即使是树也是可以查找的因为都是迭代器区间范围是左闭右开 比如我们在3前面插入30
并且由于是带头双向循环的原因insert是不存在迭代器失效问题的
erase 虽然insert没有迭代器失效问题但是erase是有的 节点都不存在了 insert以后it不失效erase以后it会失效
如果我们要删掉所有的偶数呢
是需要使用返回值的和vector是一样的 返回的是刚刚被删除的元素的后一个
reverse reverse是链表的逆置其实有点多余了因为算法库里也有 意义其实不大
sort sort在库里面也有那是否也是多余的呢 这里编译报错了 sort编译报错了原因是sort底层是快排快排是需要三叔数取中的会取到这个数的位置链表是不适应这个场景的 我们仔细看算法库里sortfindreverse这些都是模板我们仔细看参数名字sort的是randomreverse的是bidirection一个是随机的意思一个是双向的意思这些都是暗示这些名字都不是随便起的
这里就和迭代器有关了迭代器分为单向迭代器双向迭代器和随机迭代器单向迭代器只能双向可以也可以- -而随机不仅可以和- -还可以和-
单链表的迭代器就是单向迭代器双向链表也就是list就是双向迭代器还有map和set也是vector和string是随机迭代器 find的迭代器是input是所有迭代器都可以使用这里涉及到继承我们后面会讲
那我们该如何知道一个容器的迭代器属于什么呢 其实文档里都有说明 比如list的迭代器是双向的
但迭代器的使用不是定死的比如stringvector都可以使用reverse因为随机迭代器可以看作特殊的双向迭代器是可以兼容的比如双向可以使用单向的
我们再回过头来看list的sort还有意义吗有一点但不多
如果要排序的话我们应该使用vector而不是list在500w的数据量时vector能比list快10倍
list的排序底层使用的是归并排序所以list的sort的意义就是方便
我们要排序的话 可以这样做把list的数据拷贝到vector然后再拷贝回来
所以各位以后在排序时尤其是数据量大时不要用list的sort
merge merge是两个链表的归并 不过归并前先排序一下 unique unique去重的意思不过去重前也是需要先排序的不然效率太低了
remove remove就是find加erase 找不到的话就什么也不做找到就删除
splice splice是转移可以将a链表的节点拿下来转移到b链表
我们看第一个接口是把x链表的所有值转移到当前链表position之前第二个是转移x链表的i第三个是转移一个区间 这里是调用第一个接口 是全部转移此时mylist2是空的 这里调用第二个接口我们把第二个链表的第二个数转移到第一个链表 这是第三个接口 我们把第二个链表的第二个位置开始全部转移
还可以自己转移自己 我们把第二个位置转移到第一个位置的前面 还有不要有重叠像这样就死循环了 模拟实现
下面我们来进行模拟实现
首先我们先看看源代码 我们看到有一个void*类型 我们还找到了链表 还找到了成员变量 它的本质是这样的 我们还看到了无参的构造函数 初始化了一个节点 getnode是哨兵位节点 putnode下面我们发现了熟人construct 这些我们了解一下即可 我们还可以找到pushback 我们发现它调用了insert
我们就不再深入各位感兴趣的话可以自己再看看下面我们进入正题
基础框架 我们使用struct定义节点使用class也可以不过需要使用public节点不是公有的使用起来会非常麻烦 补全一下最后写成这样看框住的地方有人可能直接在private里写list_node* _head这样是错误的因为 忘记了T
构造函数 list(){_head new Node;_head-_prev _head;_head-_next _head;} 除了list里要写构造函数节点里也要写一个因为我们在插入节点时是需要创建的而创建时调用构造函数即可 push_back void push_back(const T x){Node* tail _head-_prev;Node* newnode new Node(x);tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;}
其实写起来和我们以前用C实现的是一样的
迭代器 首先大家想一想我们的迭代器用Node*可以吗
大家想一想数组是连续的我们解引用后就可以直接用就可以到下一个位置但是链表不行它不是连续的即使当前是连续的我们插入一个值也会变成不连续的 我们当时日期对象是如何到下一天的是调用了一个函数是需要运算符重载 我们看库里面是这样实现的 我们要的话就是让nodenode-next
深入看库对于现在的我们来说还是有点难度的我们就不再往下看 所以我们最后迭代器是这样一个东西
现在需要写begin和end 我们遍历是这样写的 begin是第一个数据end是最后一个数据的下一个位置 我们看库里面库里面的node是我们的headend返回了nodebegin返回了node的next和我们是一样的
迭代器是自定义类型是节点指针但因为底层原因不是连续的我们不能用原生的不像之前的vector等等C可以用一个类来封装内置类型然后重载运算符比如就是调operator就变成我们来控制了就像C里面指针是不符合我们行为的我们可以把它写的和指针一样但是底层不一样 就像这样再想想我们要写list的遍历也是这样写但是*it看起来一样实际不一样一个数组一个链表甚至一棵树遍历都可以这样写封装和运算符重载的力量是非常强大的
我们从应用的角度来实现即从遍历这里开始写怎么写迭代器 我们补全一下__list_iterator再看 begin这里为什么可以这样返回呢因为单参数的构造函数支持隐式类型转换就像const char*可以转换为string一样 还可以这样写本质是一样的 我们再想想解引用该怎么办 转换为调用operator*返回节点里的值因为出了作用域节点还在val也还在所以我们返回引用 同样的我们还要写我们让nodenode-next即可 我们还要写不等于 此时我们进行测试发现报错了报错的是!
原因是在我们的循环条件里去调用operator! 然后我们的operator!的参数我们给的是引用调用了endend返回的是iterator是传值返回传值返回的是head的拷贝是临时对象具有常性所以我们在!要加const 也就是这样 此时就没有问题了 我们上面实现了我们有前置还有后置下面是后置的实现 同样的我们实现了不等于也要实现等于 常见问题
下面再解释一下第一次学习的同学一些常见问题
为什么两个typedef不在一块iterator是对外用的所以放在public里而Node是对内用的我们不希望别人访问我们的节点别人使用迭代器就可以了所以不在一块
还有为什么我们起名是list_node而不是node迭代器也是因为除了list还有vector树等等各种结构他们都在std这个命名空间里面 就像我写的这个namespace bai官方的std它所有的都在这里面所以不这样取名会存在命名冲突问题
还有一个疑惑迭代器的本质是通过自定义类型封装改变了原生指针的行为达到我们的目的 再看一个问题这里调用beginbegin的值是如何给it的 是拷贝构造这里不是赋值
我们现在的迭代器没有写拷贝构造默认生成的拷贝构造对内置类型完成值拷贝也就是浅拷贝但是没有问题我们要的就是浅拷贝 begin返回这个位置的迭代器给it我们就期望it里面的节点指针也是指向这个位置
但是两个对象指向同一个节点为什么这里没有崩溃
崩溃的核心原因在于析构函数多次释放但是迭代器对象我们没写析构函数原因是节点不是属于迭代器的不需要迭代器来进行释放我们只是借助迭代器来访问容器不论数组链表树我们都可以用同样的方式来访问容器而不是管理容器节点是由链表释放的
const迭代器 大家先想想这样设计const迭代器对吗 迭代器模拟的是指针指针有两种const指针 const迭代器模拟的是第一种指针的行为第二个指针是不能的const在*后面修饰的是指针本身而第一个是修饰指向的内容不能修改const迭代器是期望指向的内容不能修改
此时我们再看我们上面设计的是不行的我们模拟的是上面的ptr2这样写出来的是const迭代器本身不能修改我们就不能遍历不能了因为是非constconst是不能调用非const的同样我们也不能把变为const因为里要改变成员变量
我们怎么写才能控制指向的内容不能修改 我们控制解引用即可 这样返回的就是const引用
此时就会有人把上面迭代器整个拷贝一份然后改改名什么的那样设计太冗余了 我们再看库里面它加了两个模板参数 我们先在自己的迭代器这里加一个Ref然后修改operator*的返回值类型 接着我们在list里就可以typedef const迭代器了
其实这样写也相当于我们写了两个类大家想一想vectorint和vectordouble是两个类是两个相似的类有编译器通过模板生成
而我们这样写通过模板参数给T引用的时候operator*返回的就是T引用给const T引用时返回的就是const T引用但是他们两个是两个类给不同的模板参数就是不同的类
这样写的话我们还要修改一些东西 我们要在迭代器类里写这样一个我们习惯叫做self就是自己的意思 接着我们把这些修改为self即可 还有别忘记写const的begin和end 我们继续看源码发现除了重载operator*之外还重装了这样一个并且库里面是三个模板参数我们现在只有两个
我们知道指针除了*解引用还有-解引用*是取指针指向的数据指向的对象那-呢
如果是一个结构体的指针就需要-迭代器是模拟指针的行为什么时候模拟结构体指针呢 operator-默认返回的是T* 我们先看这样一段代码我们下面*it解引用是什么 这段代码为什么不能运行
因为*it是取里面的数据TT是A而A是自定义类型这里是需要重载流插入的这是第一种方法如果我们不想重载A里的成员变量a1a2都不是私有的 我们是可以这样写的
此时迭代器是模拟的指向结构体的指针如果这里类型是int我们直接解引用如果是自定义类型是需要用箭头的 是可以这样写的
但是这里有个非常诡异的问题 首先我们把operator-屏蔽掉的话这里是会报错的 但是这个箭头调用是非常奇怪的operator*是没问题的 如果是*it这里就是it.operator*() 然后operator*返回AA.a1A.a2是没有问题的
而箭头是it.operator-()返回的是A*A*怎么去访问呢
所以这里严格来说严格是it--_a1才是符合语法的是两个箭头第一个箭头的运算符重载调用operator-返回A*A*再加一个箭头才能访问
因为运算符重载要求可读性所以编译器在这里是特殊处理的省略了一个箭头
如果是const迭代器operator-应该返回const T* 所以我们需要加第三个模板参数Ptr 然后用Ptr代替T* 普通迭代器传T*const传const T* 我们上面实现的思路大家也发现了我们要从核心的东西开始看如果一上来我们就看到迭代器有三个参数人都是懵的是看不明白的所以看不懂的东西我们可以先暂时放下先看后面的看它的核心看它的功能慢慢就可以知道了我们看不懂的原因是当前站的高度太低了很多东西是需要看好几遍的 另外这些不修改的我们最好再加上const self operator--(){_node _node-_prev;return *this;}self operator--(int){self tmp(*this);_node _node-_prev;return tmp;}
再补充一下--
insert void insert(iterator pos, const T x){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);prev-_next newnode;newnode-_next cur;cur-_prev newnode;newnode-_prev prev;}
insert非常简单这里是可以体先出为什么我们节点使用的是结构体而不是类如果是类的话会变得麻烦一点我们是和库保持一致的库里面也使用的是结构体而且我们不用担心有人会写it._node这种代码因为官方只规定了迭代器可以这些而没有规定底层我们不确定这里是_node还是Node或者是_Node即使我们去查了源码也只是针对当前平台换一个平台可能就不同了 库里面和我们是差不多的
erase void 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;}
erase是需要先检查一下的end是哨兵位不能删除另外我们可以发现这里是存在迭代器失效问题的所以我们需要返回下一个位置另外我们上面还看到了insert其实也有返回值我们一块补充一下 iterator insert(iterator pos, const T x){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);prev-_next newnode;newnode-_next cur;cur-_prev newnode;newnode-_prev prev;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;return next;}
push和pop void push_back(const T x){/*Node* tail _head-_prev;Node* newnode new Node(x);tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;*/insert(end(),x);}void push_front(const T x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}
这些都没什么说的有了insert和insert我们都是可以复用的
size size_t size(){size_t sz 0;iterator it begin();while (it ! end()){sz;it;}return sz;}
我们可以这样遍历一遍如果感觉这样不好也可以加一个成员变量_size 这样写我们要修改一下insert和erase 一下即可其他地方不用变 同理erase里--一下即可 还有初始化也要修改一下
析构和clear ~list(){clear();delete _head;_head nullptr;}void clear(){iterator it begin();while (it ! end()){it erase(it);}_size 0;}
clear和析构是不一样的clear是清理数据清理还要释放空间不过哨兵位是不清的所以我们需要接受一下it刚好接受下一个位置最后处理一下size即可析构直接复用即可 我们简单测试一下没有问题
拷贝构造 list(const listT lt)//拷贝构造{_head new Node;_head-_prev _head;_head-_next _head;_size 0;for (auto e : lt){push_back(e);}}
我们把数据一个一个的放进去即可 这里是有点冗余我们提取一下公共部分库里面也是这样写的
赋值 void swap(listT lt){std::swap(_head,lt._head);std::swap(_size, lt._size);}listT operator(listT lt)//赋值{swap(lt);return *this;}
和vector一样我们直接用现代写法 测试一下也没有问题 仔细看我们和库里面的区别库里面最开始是list我们是listT 我们写的是类型它写的是类名 对于拷贝构造和赋值写类名是允许的不过这样写有点降低可读性我们这里不推荐和库一样
类模板在类里面使用既可以写类名也可以写类型虽然语法上允许不过我们最好保持统一写类型
全部代码
#includeiostream
#includelist
#includealgorithm
#includeassert.h
using namespace std;
namespace bai
{templateclass Tstruct list_node{list_nodeT* _next;list_nodeT* _prev;T _val;list_node(const T val T()):_next(nullptr),_prev(nullptr),_val(val){}};templateclass 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){}Ref operator*(){return _node-_val;}Ptr operator-(){return _node-_val;}self operator(){_node _node-_next;return *this;}self operator(int){self tmp(*this);_node _node-_next;return tmp;}self operator--(){_node _node-_prev;return *this;}self operator--(int){self tmp(*this);_node _node-_prev;return tmp;}bool operator!(const self it) const{return _node ! it._node;}bool operator(const self it) const{return _node it._node;}};templateclass Tclass list{typedef list_nodeT Node;public:typedef __list_iteratorT,T,T* iterator;typedef __list_iteratorT,const T,const T* const_iterator;//typedef const __list_iteratorT const_iterator;//错误的iterator begin(){//return _head-_next;return iterator(_head-_next);}iterator end(){return _head;//return iterator(_head);}const_iterator begin() const{//return _head-_next;return const_iterator(_head-_next);}const_iterator end() const{return _head;//return const_iterator(_head);}void empty_init(){_head new Node;_head-_prev _head;_head-_next _head;_size 0;}list(){empty_init();}//list(const list lt)//拷贝构造list(const listT lt)//拷贝构造{empty_init();for (auto e : lt){push_back(e);}}void swap(listT lt){std::swap(_head,lt._head);std::swap(_size, lt._size);}//list operator(list lt)//赋值listT operator(listT lt)//赋值{swap(lt);return *this;}~list(){clear();delete _head;_head nullptr;}void clear(){iterator it begin();while (it ! end()){it erase(it);}_size 0;}void push_back(const T x){/*Node* tail _head-_prev;Node* newnode new Node(x);tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;*/insert(end(),x);}void push_front(const T x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator insert(iterator pos, const T x){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);prev-_next newnode;newnode-_next cur;cur-_prev newnode;newnode-_prev prev;_size;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;--_size;return next;}size_t size(){/*size_t sz 0;iterator it begin();while (it ! end()){sz;it;}return sz;*/return _size;}private:Node* _head;size_t _size;};
}
以上即为本期全部内容希望大家可以有所收获
如有错误还请指正
