list 1

结构上是带头双向循环列表一、list的使用1.构造list同样空间配置器const allocator_type alloc allocator_type()先不用管1默认构造函数功能创建空 list不存任何元素。 explicit作用修饰类的构造函数禁止编译器做【单参数的隐式类型转换】只允许显式调用构造。只对可以接收单个实参的构造函数生效含带默认参数最终只需要传 1 个参数的构造。2size_type n要创建n 个元素const value_type val每个元素的值缺省时调用该类型默认构造。功能生成含有n个val副本的链表。3模板接收任意输入迭代器把 [first, last)左闭右开区间内的元素复制进 list。可以把别的容器vector、数组的一段内容拷贝到 list。4拷贝构造传入另一个同类型 list x深拷贝全部元素生成新链表。2.析构3.赋值4.迭代器链表不支持 [下标]可以实现但是代价是On不支持 迭代器-数字5.容量list没有扩容的概念所以没有reserve6.元素访问返回头 尾数据 。返回头尾后还可以修改因为有reference,是引用的意思。7.修改器1emplace_back和push_back功能一样原理不一样现在阶段无法了解9107之前介绍的接口功能和之前vector的功能保持一致8.链表专属操作1.reverse在算法库中也有冗余2.sort(无论是算法库还是list自己实现的sort默认实现都是升序。算法库还是list自己实现的sort想降序就需要用到一个叫仿函数的东西会在站和队列部分讲解)lessint小于仿函数等价逻辑 a b用于升序排序默认greaterint大于仿函数等价逻辑 a b用于降序排序头文件需要#includefunctionalless、greater是标准库提供的仿函数函数对象传匿名对象也可以3.合并 merge取小的尾插前提要求这两个列表有序4.unique 去重 要求数据有序5.remove 删除一个值给一个值找到就删6..remove_if对要删除的值附加条件若有该值且达成条件就删除7.splice 裁剪并粘接相当于转移被转移的源链表x对应的元素会被搬走源容器中不再拥有这些元素。可以自己转移自己(调整当前列表的顺序)1把链表x里面全部节点移动到调用该函数的 list 的position位置之前调用完成后x变为空链表2只把源链表 x 中迭代器 i 指向那 1 个节点移动到目标 position 前面。3把源链表x中 [first, last) 区间内所有节点整体移动到目标position前面。新节点出现在 pos 所指向元素的左边pos 指向的旧元素向后挪。插在pos 迭代器的前面不是覆盖 pos8.swap测试 迭代器在迭代器代码后添加下图范围for代码验证迭代器的旧用法原因list的迭代器不是原生指针。之前stringvector迭代器是原生指针原因是他们底层的空间是连续的用原生指针当迭代器的查找的效率很高。但链表的空间不连续它的底层是一个个自定义类型。9.迭代器的功能性质不同容器都会对迭代器会进行性质介绍用下面三张图中的三个单词表示性质这三个性质(单词)可以表示不同类型迭代器不同容器对应这些迭代器。list.链表专属操作中有sort,算法库中也有sort。list不可以用算法库中的sort之后探究迭代器继承能力← 代表 “继承 / 包含能力”越靠右能力越强Input ← Forward ← Bidirectional ← Random Access1.Input输入迭代器只向前遍历it只能读取不能写只能遍历一遍不能回退。2.Output输出迭代器只能向前遍历it只能写入*itxxx不能读取单遍遍历。Input、Output 是能力最低的两个概念模型没有容器的迭代器类型对应它们。Forward、Bidirectional、Random‑Access都可以降级充当 Input 或者 Output 迭代器传给算法。3.Forward前向迭代器继承 Input Output 的全部能力可以反复向前读写支持it❗不能向后走不支持 --it4.Bidirectional双向迭代器图中间方框继承 Forward 的全部能力✅支持 it 向前、--it 向后双向移动❗不支持迭代器加减数字it5、it‑3、[] 下标全部不行重点考点list是双向迭代器不能用全局算法std::sort()std::sort 强制要求随机访问迭代器list 只能调用自己的成员函数 .sort()。5.Random Access随机访问迭代器最右侧继承 Bidirectional 全部能力能力最强。可it、--it支持 itn、it‑n、it[]下标、迭代器比较 层级逻辑靠右的迭代器拥有左边全部功能可以降级当作左边类型使用左边不能当作右边。Random‑Access ⊃ Bidirectional ⊃ Forward ⊃ Input Output 是独立类别只负责写。探究之前“list.链表专属操作中有sort,算法库中也有sort。list不可以用算法库中的sort”算法库全局 std::sort(first,last)头文件algorithm这个算法强制要求【随机访问迭代器 Random‑AccessIterator】list 成员函数 lt.sort()链表专属成员函数只要求【双向迭代器 BidirectionalIterator】。图中将算法库全局 std::sort(first,last)要传的随机访问迭代器传成了【双向迭代器 】。所以报错emplace_back浅解没看二、使用接口现在写一个列表在第三个位置插入值为30的节点。由于链表不支持 [下标]可以实现但是代价是On不支持 迭代器-数字的原因只能用循环的方式找到目标位置,再调用insert函数的方式实现运行成功输入某值若存在删除它二、了解源码先看list源码 源码中节点叫_list_node1双向链表的节点的指针为什么要用void*去typedef?.2.链表难度就在迭代器 如下图官方源码3.核心成员变量 链表节点指针变量 nodelink_type node就是结点指针变量 link_type来源如下图4.链表的无参初始化即开始时申请一个哨兵位的头节点让这个哨兵位的头节点自己指向自己STL容器用的都是内存池后面讲。上图头节点不是new出来的而是调了一个get_node的函数(如下图红色线)即用内存池有点像malloc申请没有初始化的内存哨兵位头节点不需要初始化。当插入节点时调用的是下图函数create_node ,它有点像buy node。也是用内存池申请空间申请后用construct(相当于定位new在已经分配好的内存上操作)5.push_backinsert(end(), x)把新节点插入到哨兵节点的前面。end()返回哨兵节点迭代器不是最后一个有效元素。哨兵的前一个节点就是链表原来的最后一个节点等价于链表尾部新增节点。三、模拟实现先单独给节点设计一个类模板list_node里面有1.存放数据的T类型变量 2.T类型的list_node类模板指针变量 list_nodeT* _next _prev再先单独给节点设计一个类模板list将之前的类模板list_node重命名为Node,里面有类模板Node型的指针变量head 。我们这里不用内存池了用new就行了list 对象在栈上节点对象在堆上 new 出来。_head-_next _head含义哨兵节点内部的_next 指针存哨兵节点自己的堆地址不是栈上 list 容器 lt 对象。在没有虚函数、没有继承、访问权限不影响内存布局的前提下_head保存的是list_node整个对象的起始地址 对象第一个非静态成员的地址也就是说在创建这个对象时是按。两者意义不同可能会影响后续的使用方法对于普通类无虚函数、无继承成员变量在内存中的存储顺序 成员变量声明顺序初始化列表顺序。.是对象本身访问成员的运算符-是对象指针访问成员通过对象指针找到对象后访问成员的运算符。1.构造头节点 list()}2.push_back用一个指针变量tail保存头节点的prev指向的节点地址该指针变量指向最后一个节点相当于找到了最后一个节点地址3.两个模板增加成员size empty() 方便后续计算3.实现迭代器像测试上面已写的功能函数 只能用迭代器循环打印问题是怎么实现迭代器先看官方源码怎么解决如图为什么会有三个模板参数先不管源码中有这样一个类_list_node有核心成员node 如图也就是说这个类封装了一个节点指针变量源码中将解引用符* 自增运算符 重载了解引用符* 重载后功能改为 返回节点中存放的数据自增运算符 重载后功能改为 将当前节点内的next指针赋给他自己 也就是当前指针移动到了下一个节点。实现迭代器相当于返回一个指针迭代器是可以是原生指针也可以是自定义对象图纸类能干什么类 图纸不是根据图纸造出来的汽车对象图纸本身不能开但图纸1. 规定汽车对象实物身上有哪些零件成员变量2. 规定汽车对象实物具备哪些功能成员函数3. 定使用汽车守则访问规矩哪些对外可见哪些隐藏public/private注意我们用的是汽车通过使用汽车完成目的原本遍历链表要用节点指针但是节点指针不像string vector一样连续所以专门用一个迭代器类模板list_iterator封装重载运算符去搞定list迭代器的问题声明在第一个类后。这里建议前两个类用struck应为后面要大量应用两个类若他们用class用访问限定符限制一些变量还得加友元声明。类内有成员变量node,是Node型指针变量将前两个类重命名为 Node Self完成三个函数重载operator* operator 判断两个迭代器是否相等现在还需要补充 begin在迭代器类模板补充迭代器构造函数 end()下图补充构造函数继续完成begin 下两图都行完成end()测试报错因为模板类list_node没有写构造补上构造但又显示类模板list_node没有合适的默认构造分析法一法二若T()是自定义类型则调该自定义类型的默认构造推荐用法二运行成功在list模板类内再添加-- insert 功能函数完成insert后尾插push_back将原来注释如下左图 头插 push_front就可以直接复用它了添加erase功能函数尾删 pop_back 头删pop_front