C++STL泛型编程1(长望班课件20140525) (1).ppt

1 C STL泛型编程 GenericProgramming 南京信息工程大学计算机与软件学院 长望程序设计竞赛班 2 为什么要采用泛型编程 ACM竞赛中 需要用到数组 链表 字符串 栈 队列 平衡二叉树等数据结构 以及排序 搜索等算法 若全部自行编写比较麻烦 ANSIC 中包含了C STL StandardTemplateLibrary 标准模板库 又称C 泛型库 定义了常用的数据结构和算法 使用十分方便 有了STL 不必再从头写大多的标准数据结构和算法 并且可获得非常高的性能 但这不意味着我们不需要掌握基本数据结构与算法 相反 只有透彻理解了 才能更好的使用泛型 泛型程序设计 由AlexanderStepanov和DavidMusser创立 于1998年被添加进C 标准 含义 编写不依赖于具体数据类型的程序 目标 将程序写得尽可能通用 将算法从特定的数据结构中抽象出来 成为通用的 C 的模板为泛型程序设计奠定了关键的基础 STL 标准模板库 StandardTemplateLibrary 是泛型程序设计的一个范例 代码重用 reuse 函数模板简介 4 引例 交换2个整数和交换2个浮点数的C 程序 交换2个整数voidSwap int intmain inta 10 b 20 floatc 1 2 d 2 4 cout a a b b cout c c d c Swap a b cout a a b b Swap c d cout c c d c return0 两个Swap函数实现的功能相同 只是参数类型不同 但为了实现不同类型的数据交换必须分别编写函数 造成了重复劳动 函数重载 5 能否提供一种方法将两个函数合并 以节省开发成本 引例 typedefintDataType voidSwap DataType 当需要交换两个浮点数时可以将DataType定义成float型数据即可 typedeffloatDateType 存在问题 更改一种数据类型时 需要修改程序源代码 必须重新编译程序 如果程序中需要交换多种数据类型数据 怎么办 6 引例 includeusingnamespacestd templatevoidSwap T 模板声明 定义函数模板 通用的Swap 能否将Swap函数的形式参数 作为一种无类型的参数 当使用它的时候再将它用具体的参数实现 模板机制 模板的概念 模板是一种使用无类型参数来产生一系列函数或类的机制 模板是以一种完全通用的方法来设计函数或类而不必预先说明将被使用的每个对象的类型 通过模板可以产生类或函数的集合 使它们操作不同的数据类型 从而避免需要为每一种数据类型产生一个单独的类或函数 7 模板分类 函数模板 functiontemplate 是独立于类型的函数可产生函数的特定版本类模板 classtemplate 与类相关的模板 如vector可产生类对特定类型的版本 如vector 8 模板工作方式 模板只是说明 需要实例化后才能执行或使用 9 函数模板 functiontemplate 定义格式 template类型名函数名 参数表 函数体 templatevoidSwap T 10 template 函数模板定义关键字 中是函数的模板参数 参数可有一个或多个 逗号隔开 不能为空 模板参数常用形式 class标识符或者typename标识符模板参数表明函数可以接收的类型参数 可以是内部类型 也可以是自定义类型 templatevoidSwap T 例1 简单函数模板定义和应用 includeusingnamespacestd templateTMax Ta Tb returna b a b intmain cout Max 3 5 is Max 3 5 endl cout Max y e is Max y e endl cout Max 9 3 0 5 is Max 9 3 0 5 endl return0 函数模板 intMax inta intb returna b a b 由实参类型实例化 charMax chara charb returna b a b doubleMax doublea doubleb returna b a b 编译器生成的模板函数 函数模板实例化 函数模板的原理分析 函数模板中声明了类型参数T 表示了一种抽象类型 编译器检测到程序调用函数模板Max时 用其第一个实参类型替换掉模板中的T 同时建立一个完整的函数Max 并编译该新建的函数 本例中 针对三种数据类型 生成了三种函数 练习1 编写一个对具有n个元素的数组a 求最小值的程序 要求将求最小值的函数设计成函数模板 includeusingnamespacestd templateTMinArray Ta intn inti Tmina a 0 for i 1 ia i mina a i returnmina intmain intarr1 1 3 0 2 7 6 4 5 2 doublearr2 1 2 3 4 6 8 9 8 cout arr1数组的最小值为 MinArray arr1 9 endl cout arr2数组的最小值为 MinArray arr2 4 endl return0 注意点1 实参类型与形参类型必须严格匹配 includeusingnamespacestd templateTMax Ta Tb returna b a b intmain inta 3 floatb 1 5 cout Max a b is Max a b endl return0 错误 模板类型不能提供类型的隐式转换 注意点2 在函数模板中允许使用多个类型参数 在template定义部分的每个模板形参前必须有关键字class或typename includeusingnamespacestd templatevoidmyfunc T1x T2y cout x y endl intmain myfunc 100 hao myfunc 3 14 10L return0 注意点3 在template语句与函数模板定义语句之间不允许有别的语句 Templateinti 错误 不允许有别的语句TMax Tx Ty return x y x y 8 模板优缺点 优点 函数模板方法克服了C语言用大量不同函数名表示相似功能的弊端 克服了宏定义不能进行参数类型检查的弊端 克服了C 函数重载用相同函数名字重写几个函数的繁琐 缺点 调试比较困难 一般先写一个特殊版本的函数运行正确后 改成模板函数 16 17 练习2 编写一个函数模板 它返回两个值中的较小者 同时要求能正确处理字符串 分析 由于C 字符串比较的方法与字符型 数值型都不同 因此函数模板不适用于字符串比较 这里设计一个函数模板templateTmin Ta Tb 可以处理int float和char等数据类型 为了能正确处理字符串 添加一个重载函数专门处理字符串比较 即char min char a char b include includetemplateTmin Ta Tb return a b a b char min char a char b return strcmp a b 0 a b voidmain doublea 3 14 b 8 28 chars1 Bad s2 Good cout 输出结果 endl cout min a b endl cout min s1 s2 endl 函数模板 函数重载 C STL 一 STL概述 STL是一个具有工业强度的 高效的C 程序库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法STL主要包含了容器 算法 迭代器库 library 是一系列程序组件的集合 它们可以在不同的程序中重复使用 21 引例 阅读以下程序 include includeusingnamespacestd intmain vectorv inti for i 0 i iteratorit v begin it v end it cout it cout endl return0 Vector容器 声明一个整型Vector容器 尾部元素追加 用迭代器配合循环访问向量元素 22 STL中的基本概念 容器 可容纳各种数据类型的数据结构迭代器 可访问容器中元素的特殊指针算法 用来操作容器中元素的函数模板函数对象 是一个行为类似函数的对象 可象函数一样调用 例如 向量Vector就是容器 iterator是迭代器 STL用sort 来对一个vector中的数据进行排序 用find 来搜索一个list中的对象 最基本的 遍历结构 对数据结构的操作 C STL是通用数据结构和算法的封装 C STL中 容器 container 就是通用的数据结构 容器用来承载不同类型的数据对象 C 中的容器还存在一定的 数据加工能力 它如同一个对数据对象进行加工的模具 可以把不同类型的数据放到这个模具中进行加工处理 形成具有一定共同特性的数据结构 例如 将int型 char型或者float型放到队列容器中 就分别生成int队列 char型队列或者float型队列 它们都是队列 具有队列的基本特性 但是具体数据类型是不一样的 概念之容器 就如同现实生活中 人们使用容器用来装载各种物品一样 24 概念之容器适配器 C STL容器适配器用来扩充7种基本容器 stack 栈 LIFO queue 队列 FIFO priority queue 优先级队列 25 概念之迭代器 用于指向容器中的元素 通过迭代器可以读取它指向的元素 迭代器是泛化的指针 可用 改变其指向位置 可用 访问内容 26 26 概念之算法 C STL包含70多个算法 包括 查找 排序 比较 变换 置换 容器管理等 算法是通用的 可作用于不同的类对象和预定义类型数据 27 27 STL组件间的关系 C STL将迭代器和函数对象作为算法的参数 提供了极大灵活性 使用STL提供的或自定义的迭代器 配合STL算法 可组合出各种各样强大的功能 STL头文件一览 容器的基本功能与分类 容器是容纳 包含一组元素或元素集合的对象 七种基本容器 向量 vector 双端队列 deque 列表 list 集合 set 多重集合 multiset 映射 map 多重映射 multimap C STL的容器各有不尽相同的功能和用法 29 二 顺序容器 顺序容器 sequencecontainer 简介 顺序容器 也称 序列式容器 将一组具有相同类型的元素以严格的线性形式组织起来 三类顺序容器 1 vector头文件实际上是动态数组 随机存取任何元素都能在常数时间完成 在尾端增删元素具有较佳的性能 2 deque头文件也是动态数组 随机存取任何元素都能在常数时间完成 但性能次于vector 在两端增删元素具有较佳的性能 3 list头文件双向链表 在任何位置增删元素都能在常数时间完成 不支持随机存取 31 关联容器简介 关联容器内的元素是排序的 插入任何元素 都按相应的排序准则来确定其位置 特点是在查找时具有非常好的性能 通常以平衡二叉树方式实现 插入和检索的时间都是O logN 四种关联容器 1 set multiset 头文件set即集合 set中不允许相同元素 multiset中允许存在相同的元素 2 map multimap 头文件map与set的不同在于map中存放的是成对的key value 并根据key对元素进行排序 可快速地根据key来检索元素map同multimap的不同在于是否允许多个元素有相同的key值 类似于Hash表 32 容器适配器简介 1 stack 头文件栈 是项的有限序列 并满足序列中被删除 检索和修改的项只能是最近插入序列的项 即按照后进先出的原则 2 queue 头文件队列 插入只可以在尾部进行 删除 检索和修改只允许从头部进行 按照先进先出的原则 3 priority queue 头文件优先队列 最高优先级元素总是第一个出列 容器适配器是一种接口类 为已有类提供新的接口三种容器适配器 33 容器的共有成员函数 提供容器的通用功能 所有容器共有的成员函数 关系运算 empty 判断容器中是否为空max size 容器中最多能装多少元素size 容器中元素个数s1 swap s2 交换两个容器的内容构造函数 拷贝构造函数 析构函数 34 容器的共有成员函数 续 所有顺序容器和关联容器共有的成员函数 begin 返回指向容器中第一个元素的迭代器end 返回指向容器中最后一个元素后面的位置的迭代器rbegin 返回指向容器中最后一个元素的迭代器rend 返回指向容器中第一个元素前面的位置的迭代器erase 从容器中删除一个或几个元素clear 清空容器 35 所有容器都具有的成员函数 顺序和关联容器共同支持的成员函数 例1 创建两个整型向量容器 分别从尾端增加一些值 输出两个容器的元素数 两个容器的比较结果 交换两个容器后再输出一次 38 include includeusingnamespacestd intmain vectorv1 v2 v1 push back 5 v1 push back 1 v2 push back 1 v2 push back 2 v2 push back 3 coutv2 v2 endl return0 声明2个向量 向量赋值 求元素数 向量内容比较 交换2个向量 1 vector向量容器 实际上就是动态数组 但它比数组更灵活 当添加数据时 vector的大小能够自动增加以容纳新的元素 内存自动管理 可动态调整所占内存 支持随机访问 随机访问时间为常数 所有STL算法都能对vector操作 在尾部添加速度很快 在中间插入慢 39 1 创建vector对象 四种方式 不指定容器的元素个数 vector对象名 例如 vectorv 创建整型向量v指定容器大小 vector对象名 n 例如 vectorv 10 创建整型向量v 10个元素注意 元素下标0 9 初始化为0 指定容器大小和元素初始值 vector对象名 n 初值 例如 vectorv 10 1 创建整型向量v 10个元素 每个元素值均为1由已有向量容器创建 vector对象名 已有对象名 例如 vectorv2 v1 创建整型向量v1的副本v2 40 拷贝构造函数 创建vector向量 include includeusingnamespacestd intmain vectorv 10 1 for vector iteratorit v begin it v end it cout it cout endl return0 例2 创建一个整型向量容器 输出全部元素值 42 2 下标方式访问vector元素 可用 运算符访问vector的元素 例3 用 运算符为整型向量容器元素赋值 输出全部元素值 include includeusingnamespacestd intmain vectorv 3 v 0 10 v 1 100 v 2 20 for inti 0 i 3 i cout v i cout endl return0 43 vector 向量 下标访问元素 注意 下标操作仅能对确知已存的元素进行赋值和读取操作 vectorivec emptyvectorfor intix 0 ix 100 ix ivec ix ix ivechasnoelement 出错 向量中尚没有元素 不能访问 3 用迭代器访问vector元素 如何使相同的算法能用于不同的数据结构 迭代器 算法与容器的 中间人 45 容器类迭代器定义方法 容器类名 iterator变量名 访问一个迭代器指向的元素 迭代器变量名迭代器上可执行 指向容器中的下一个元素 如果迭代器到达了容器中的最后一个元素的后面 则迭代器变成past the end值 使用一个past the end值的迭代器来访问对象是非法的 定义迭代器的关键字 46 对照理解 vector iteratorxHere x Begin vector iteratorxEnd x End for xHere xEnd xHere func name xHere for inti 0 i x Size i func name x Get i 例4 include includeusingnamespacestd intmain vectorv v push back 1 v push back 2 v push back 3 v push back 4 vector const iteratorit1 常量迭代器for it1 v begin it1 v end it1 cout reverse iteratorit2 反向迭代器for it2 v rbegin it2 v rend it2 cout it2 cout endl 47 vector iteratorit3 非常量迭代器for it3 v begin it3 v end it3 it3 100 重置向量for it3 v begin it3 v end it3 cout it3 cout endl return0 1 const iterator 常量迭代器 可以使用这种类型的迭代器来指向一个只读的值 2 reverse iterator 反向迭代器 用来反转遍历vector的各元素 注意用rbegin 来代替begin 用rend 代替end 而此时的 操作符会朝向后的方向遍历 3 iterator 随机迭代器 可任意方向或移动任意个位置访问 vector的迭代器 有const限制的只可读取元素值 不可修改元素值 48 不同的容器 STL提供的迭代器功能各不相同 vector容器的迭代器 可使用 中的任何一种操作符可使用 等比较运算符可随机访问容器中的数据元素 vector的迭代器 49 4 元素插入 push back在尾部追加元素 insert方法可在vector任意位置插入元素 例5 向整型向量容器追加元素 输出全部元素值 include includeusingnamespacestd intmain vectorv 10 1 v push back 100 v psuh back 200 for vector iteratorit v begin it v end it cout it cout endl return0 尾部追加元素 vector容器自动分配内存 可对空的vector追加 也可对已有元素的vector追加 尾部元素追加 50 vector 向量 添加 在尾端增删元素具有较佳的性能 51 指定位置插入元素 insert iteratorit Tt 对vector容器在指定位置插入新元素 例6 对整型向量容器插入元素 输出全部元素值 include includeusingnamespacestd intmain vectorv 3 vector iteratorit v 0 10 v 1 100 v 2 20 v insert v begin 50 在最前面插入新元素50v insert v begin 2 8 在第2个元素之前插入新元素8v insert v end 9 在末尾插入新元素8for it v begin it v end it cout it cout endl return0 注意 insert方法要求插入的位置 是迭代器位置 而不是下标 52 通过迭代器随机访问元素 5 元素删除 pop back删除向量最后一个元素 erase删除指定位置或一段区间的元素 clear方法删除所有元素 例7 向量容器删除元素方法示例 include includeusingnamespacestd intmain vectorv 10 vector iteratorit for inti 0 i 10 i v i i v erase v begin 3 删除第3个元素 从0开始计数for it v begin it v end it cout it cout endl v erase v begin 1 v begin 3 删除第1 3个元素for it v begin it v end it cout it cout endl 向量V中元素数 v size endl v clear 清空向量cout endl 向量V中元素数 v size endl return0 区间删除 53 6 向量大小的有关操作 54 向量的大小 size 和resize vectorvec 10 42 10int eachhasvalue42cout vec size endl vec resize 15 adds5elementsofvalue0tothebackofthevectorcout vec size endl vec resize 25 1 adds10elementsofvalue 1tothebackofthevectorcout vec size endl 新增元素初始化为 1 55 size max size 和capacity vectorv1 coutv2 100 1 cout v2 size v2 max size v2 capacity endl size 返回向量中元素的个数max size 返回向量中最多可容纳的元素个数capacity 获取向量的容量 再分配内存空间之前所能容纳的元素个数 当元素个数等于capacity返回的元素个数时 vector自动分配一段空间用于存储输入的新元素 vec size vec capacity 向量的大小 systemmemory max size max size是系统最大可分配的容量 并非实际分配 56 7 在向量上使用算法 C STL很多算法都可以在向量上使用 使用算法需要包含头文件 例8 在整型向量容器上使用排序算法 include include includeusingnamespacestd intmain vectorv vector iteratorit for inti 0 i 10 i v push back 10 i for it v begin it v end it cout it cout endl sort v begin v end 对向量排序for it v begin it v end it cout it cout endl return0 57 8 vector作为函数参数 include includeusingnamespacestd voidprint vectorv for vector iteratorit v begin it v end it coutvec vec push back 1 vec push back 2 vec push back 3 print vec return0 例9 向量作为函数参数示例 58 include includeusingnamespacestd constintKVectSize 5 intmain vectorvec inti for i 0 i KVectSize i vec push back i cout p newvector vec coutsize capacity endl for i 0 i p size i p i 0 p clear coutsize capacity endl deletep return0 练习 阅读程序 59 练习 学生成绩标准分的计算方法为 成绩 最高成绩 100 编写程序 使用向量作为存储结构 输入学生原始成绩 以输入 1为结束 将学生成绩转换为标准分输出 每行一个 SampleInput 769258958772 1 SampleOutput 8096 842161 052610091 578975 7895 60 分析 首先须比较所有学生的成绩 取得最高分 将学生原始成绩除以最高分 然后乘上100 由于程序没有给出学生人数 所以采用向量作为数据存储结构 因为向量的元素个数可以自动的动态增长 include includeusingnamespacestd intmain vectorscore 创建向量vector iteratorit doublemax temp cin max score push back max while true cin temp if temp 1 break score push back temp if temp max max temp for it score begin it score end it it max cout it endl return0 61 对比代码 include includeusingnamespacestd intmain vectorscore 创建向量doublemax temp inti cin max score push back max for i 1 true i cin temp if temp 1 break score push back temp if temp max max temp max 100 for i 0 i score size i score i max cout score i endl return0 未充分使用向量容器上的迭代器来访问元素 仍自己管理下标 存在不安全隐患 62 练习 ImageTransformation图像是以像素矩阵存储在计算机中 在rgb三色系统中 一个像素的颜色以 rgb 格式表示 r g b 0 255 然而 有时候我们需要灰度图像而不是彩色图像 把RGB图像转换为灰度图像的一种简单方法为 把一个像素的r g b值都设置为一个相同的值 即 r g b 3 这里假定 r g b 总能被3整除 编写程序测试这种方法的有效性 63 输入 包含多个测试样例 每个测试样例以2个整数N和M 1 N M 100 打头 表示图像的高度和宽度 接下来是3个N M矩阵 分别代表每个像素的r g b值 当一行上的N和M都为0时 表示输入结束 这行数据不需处理 输出 对每个测试样例 先输出 Case 是测试样例序号 从1开始 然后输出一个N M矩阵 它描述了灰度图像中每个像素的灰度值 应当有N行 每行有M个整数 其间用逗号隔开 SampleInput 22146925710368112301234201234301234400 SampleOutput Case1 2 57 10Case2 0 1 23 4 3 64 分析 本题英文原题比较长 理解题意比较难 每个测试样例的数据由两部分组成 第一行是矩阵大小 N M 第二部分是三个N M矩阵 共3 N行数据含义 2214692571036811 1 2 3 4 5 6 6 7 8 9 10 11 提示 问题中涉及r g b三类数据的存储和计算 而每个测试样例包含的像素数是N M个 每个样例的N M可能都不一样 若自行管理数组 涉及动态存储管理 较为复杂 可考虑建立三个向量r g b 分别存储像素点的r g b值 利用向量的方法可方便的处理元素 2 list列表容器 66 list是一个双向链表可以双向 从头到尾 从尾到头 访问链表中的结点 结点可以是任意数据类型 链表中结点的访问常通过迭代器进行 不可随机访问 67 list数据结构分析 头结点 list每个结点有三个域 存储可以不连续 迭代器只能通过 或 移动到目标元素上 每个元素还有两个指针的额外空间开销 1 创建list对象 四种方式 创建空链表 list对象名 例如 listtable 创建整型链表table创建具有n个元素的链表 list对象名 n 例如 listtable 10 创建整型链表table 10个元素创建具有n个元素的链表 指定元素初始值 list对象名 n 初值 例如 listtable 10 9 创建整型链表table 10个元素 每个元素值均为9由已有list容器创建 list对象名 已有对象名 例如 listt2 t1 创建整型链表t1的副本t2 68 创建list链表 69 include includeusingnamespacestd intmain listt1 5 创建链表listt3 3 9 list iteratorit t1 push back 2 t1 push front 3 listt2 t1 创建链表for it t1 begin it t1 end it cout it cout endl for it t2 begin it t2 end it cout it cout endl for it t3 begin it t3 end it cout it cout endl return0 例10 创建整型链表 输出全部元素值 70 2 元素插入 push back在尾部插入元素 push front在头部插入元素 insert向迭代器位置处插入新元素 71 三个方法 注意 插入元素时 链表自动扩展 不可自行修改迭代器 insert iteratorit Tt 对list容器在指定位置插入新元素 例11 用insert向整型链表中插入元素 输出全部元素值 include includeusingnamespacestd intmain listt1 5 创建链表list iteratorit t1 push back 2 t1 push front 3 it t1 begin it it t1 insert it 100 for it t1 begin it t1 end it cout it cout endl return0 注意 链表的迭代器只能顺序逐位移动 不可 n 72 3 元素删除 remove删除链表中值相同的元素 pop front删除链表首元素 pop back删除链表尾元素 erase删除迭代器位置上的元素 clear方法删除所有元素 73 五个方法 remove删除链表中相同值元素 remove Telem 删除链表中所有与elem值相等的元素 例12 list的remove方法示例 include includeusingnamespacestd intmain listt1 创建链表t1 push back 20 t1 push front 13 t1 push back 100 t1 push back 19 t1 push back 13 t1 push back 20 for list iteratorit t1 begin it t1 end it cout iteratorit t1 begin it t1 end it cout it cout endl return0 74 删除链表首 尾元素 pop front pop back 删除链表中首 尾元素 例13 list的pop front pop back 方法示例 include includeusingnamespacestd intmain listt1 创建链表t1 push back 20 t1 push front 13 t1 push back 100 t1 push back 19 t1 push back 13 t1 push back 20 for list iteratorit t1 begin it t1 end it cout iteratorit t1 begin it t1 end it cout it cout endl return0 75 erase删除指定元素 erase iteratorit 删除链表中迭代器it所指位置处的元素 例14 list的erase方法示例 include includeusingnamespacestd intmain listt1 创建链表list iteratorit t1 push back 20 t1 push front 13 t1 push back 100 t1 push back 19 t1 push back 13 t1 push back 20 for it t1 begin it t1 end it cout it cout endl it t1 begin it t1 erase it 删除it所指位置的元素for it t1 begin it t1 end it cout it cout endl return0 注意迭代器当前位置 思考 若list链表为空 执行删除操作会产生何结果 76 4 遍历链表 iterator前向迭代器 前向迭代reverse iterator反向迭代器 反向迭代 例15 list的反向迭代器reverse iterator示例 include includeusingnamespacestd intmain listt1 创建链表list iteratorit1 list reverse iteratorit2 t1 push back 20 t1 push front 13 t1 push back 100 t1 push back 19 t1 push back 13 t1 push back 20 for it1 t1 begin it1 t1 end it1 cout it1 cout endl for it2 t1 rbegin it2 t1 rend it2 cout it2 cout endl return0 反向遍历 77 前向遍历 5 元素排序 list的sort方法 对链表元素排序 例16 list的sort方法示例 include includeusingnamespacestd intmain listt1 创建链表list iteratorit t1 push back 20 t1 push front 13 t1 push back 100 t1 push back 19 t1 push back 13 t1 push back 20 for it t1 begin it t1 end it cout it cout endl t1 sort for it t1 begin it t1 end it cout it cout endl return0 78 6 剔除连续重复元素 list的unique方法 剔除链表中连续的重复元素 例17 list的unique方法示例 include includeusingnamespacestd intmain listt1 创建链表list iteratorit t1 push back 20 t1 push front 13 t1 push back 100 t1 push back 100 t1 push back 100 t1 push back 100 t1 push back 13 t1 push back 20 for it t1 begin it t1 end it cout it cout endl t1 sort for it t1 begin it t1 end it cout it cout endl return0 79 7 重组列表 list的splice方法 拼接方法 用来重组列表voidsplice iteratorit list 将范围 fast last 中的元素从列表x中移出 并插入到当前列表中it之前 x与当前列表可以是同一个 当这时范围 first last 不能包含it所指的元素 80 splice方法使序列便于重组 无需移动大量元素 例18 list的unique方法示例 include includeusingnamespacestd intmain listt1 创建链表1listt2 创建链表2list iteratorit1 it2 it3 t1 push back 20 t1 push front 13 t1 push back 100 t1 push back 20 t2 push back 120 t2 push front 30 t2 push back 10 t2 push back 2 t2 push back 13 t2 push back 143 for it1 t1 begin it1 t1 end it1 cout it1 cout endl it1 t1 begin it1 it1 it2 t2 begin it2 it3 t2 end it3 t1 splice it1 t1 it2 it3 for it1 t1 begin it1 t1 end it1 cout it1 cout endl return0 81 8 链表逆置 list的reverse方法 逆置方法 用来逆置链表 82 例19 list的reverse方法示例 include includeusingnamespacestd intmain listt1 创建链表list iteratorit t1 push back 20 t1 push front 13 t1 push back 100 t1 push back 100 t1 push back 100 t1 push back 100 t1 push back 13 t1 push back 20 for it t1 begin it t1 end it cout it cout endl t1 reverse for it t1 begin it t1 end it cout it cout endl return0 9 两个有序链表合并 list的merge方法 合并方法 用来合并2个有序链表 83 例20 list的merge方法示例 include includeusingnamespacestd intmain listt1 t2 创建链表list iteratorit t1 push back 13 t1 push front 20 t1 push back 30 t1 push back 100 t2 push back 10 t2 push back 50 for it t1 begin it t1 end it cout it cout endl for it t2 begin it t2 end it cout it cout endl t1 merge t2 for it t1 begin it t1 end it cout it cout endl return0 10 元素查找 使用find算法 在链表中查找元素 找到 返回迭代器位置 找不到 返回end 迭代器位置 例21 在list中查找的示例 include include includeusingnamespacestd intmain listt1 创建链表list iteratorit t1 push back 20 t1 push front 13 t1 push back 100 t1 push back 20 for it t1 begin it t1 end it cout it cout endl it find t1 begin t1 end 100 在全表范围内查找元素100if it t1 end it 100 for it t1 begin it t1 end it cout it cout endl return0 84 include includeusingnamespacestd intmain inti listL1 L2 inta1 100 90 80 70 60 inta2 30 40 50 60 60 60 80 for i 0 i 5 i L1 push back a1 i for i 0 i 7 i L2 push back a2 i L1 reverse L1 merge L2 cout L1的元素个数为 L1 size endl L1 unique while L1 empty cout L1 front t L1 pop front cout endl 练习 阅读程序 85 练习 编写程序建立一个保存学生数据 学号 姓名 专业 的链表 可以输出所有学生的数据 并可逆置链表 删除指定学生 3 deque双端队列容器 87 双端队列中的元素可以从两端弹出 插入和删除操作可以在表的两端进行 而且效率极高 vector与deque同属于随机访问容器 vector拥有的成员函数deque也都含有 特点在两端插入或删除元素快在中间插入或删除元素慢随机访问较快 但比向量容器慢 88 deque数据结构分析 deque采用分块线性存储结构 deque分成若干线性存储块 称为deque块 块的大小一般为512个字节 所有的deque块使用一个Map块进行管理 每个Map数据项记录各个deque块的首地址 deque使用了两个迭代器M start和M finish 对首个deque块和末deque块进行控制访问 1 创建deque对象 四种方式 创建空双端队列 deque对象名 例如 dequed 创建整型双端队列d创建具有n个元素的双端队列 deque对象名 n 例如 dequed 10 创建整型双端队列d 10个元素创建具有n个元素的双端队列 指定元素初始值 deque对象名 n 初值 例如 dequed 10 8 创建整型双端队列d 10个元素 每个元素值均为8由已有deque容器创建 deque对象名 已有对象名 例如 dequed2 d1 创建整型双端队列d1的副本d2 89 创建deque双端队列 90 include includeusingnamespacestd intmain dequed1 5 创建双端队列dequed2 8 9 deque iteratorit d1 push back 2 d1 push front 3 dequed3 d1 创建双端队列for it d1 begin it d1 end it cout it cout endl for it d2 begin it d2 end it cout it cout endl for it d3 begin it d3 end it cout it cout endl return0 例22 创建整型双端队列 输出全部元素值 91 deque容器中主要成员函数 2 元素插入 push back在尾部插入元素 push front在头部插入元素 insert向迭代器位置处插入新元素 93 三个方法 注意 插入元素时 链表自动扩展 不可自行修改迭代器 insert iteratorit T