泛型程序设计与C标准模板库.pptVIP

第十章泛型程序设计与C 标准模板库 清华大学郑莉 目录 10 1泛型程序设计及STL的结构10 2迭代器10 3容器的基本功能与分类10 4顺序容器10 5关联容器10 6函数对象10 7算法10 8综合实例 对个人银行账户管理程序的改进10 9深度探索10 10小结 2 10 1 1泛型程序设计的基本概念 编写不依赖于具体数据类型的程序将算法从特定的数据结构中抽象出来 成为通用的C 的模板为泛型程序设计奠定了关键的基础几个术语概念 concept 用来界定具备一定功能的数据类型 如 支持 运算符 的数据类型构成Comparable这一概念 模型 model 符合一个概念的数据类型称为该概念的模型 如int型是Comparable概念的模型 3 10 1泛型程序设计及STL的结构 10 1 2STL简介 标准模板库 StandardTemplateLibrary 简称STL 提供了一些非常常用的数据结构和算法STL程序实例 例10 1 4 10 1泛型程序设计及STL的结构 包含的头文件略去 usingnamespacestd intmain constintN 5 vectors N for inti 0 i s i transform s begin s end ostream iterator cout negate cout endl return0 容器 迭代器 函数对象 算法 STL的组成部分 5 STL是泛型程序设计的一个范例容器 container 迭代器 iterator 算法 algorithms 函数对象 functionobject 10 1泛型程序设计及STL的结构 10 1 2STL简介 10 2 1输入流迭代器和输出流迭代器 输入流迭代器istream iterator以输入流 如cin 为参数构造可用 p 获得下一个输入的元素输出流迭代器ostream iterator构造时需要提供输出流 如cout 可用 p x将x输出到输出流二者都属于适配器适配器是用来为已有对象提供新的接口的对象输入流适配器和输出流适配器为流对象提供了迭代器的接口 6 10 2迭代器 例10 2从标准输入读入几个实数 分别将它们的平方输出 10 2 cpp include include includeusingnamespacestd 求平方的函数doublesquare doublex returnx x intmain 从标准输入读入若干个实数 分别将它们的平方输出transform istream iterator cin istream iterator ostream iterator cout t square cout endl return0 7 10 2迭代器 10 2 1输入流迭代器和输出流迭代器 10 2 2迭代器的分类 8 10 2迭代器 迭代器支持的操作 迭代器是泛化的指针 提供了类似指针的操作 诸如 运算符 输入迭代器可以用来从序列中读取数据 如输入流迭代器输出迭代器允许向序列中写入数据 如输出流迭代器前向迭代器既是输入迭代器又是输出迭代器 并且可以对序列进行单向的遍历双向迭代器与前向迭代器相似 但是在两个方向上都可以对数据遍历随机访问迭代器也是双向迭代器 但能够在序列中的任意两个位置之间进行跳转 如指针 使用vector的begin end 函数得到的迭代器 9 10 2迭代器 10 2 2迭代器的分类 10 2 3迭代器的区间 两个迭代器表示一个区间 p1 p2 STL算法常以迭代器的区间作为输入 传递输入数据合法的区间p1经过n次 n 0 自增 操作后满足p1 p2区间包含p1 但不包含p2 10 10 2迭代器 例10 3综合运用几种迭代器的示例 10 3 cpp include include include includeusingnamespacestd 将来自输入迭代器p的n个T类型的数值排序 将结果通过输出迭代器result输出templatevoidmySort InputIteratorfirst InputIteratorlast OutputIteratorresult 通过输入迭代器p将输入数据存入向量容器s中vectors for first last first s push back first sort s begin s end 对s进行排序 sort函数的参数必须是随机访问迭代器copy s begin s end result 将s序列通过输出迭代器输出 11 10 2迭代器 10 2 3迭代器的区间 例10 3 续 intmain 将s数组的内容排序后输出doublea 5 1 2 2 4 0 8 3 3 3 2 mySort a a 5 ostream iterator cout cout istream iterator cin istream iterator ostream iterator cout cout endl return0 12 10 2迭代器 10 2 3迭代器的区间 运行结果 0 81 22 43 23 32 458 136 5 5 4 123568 10 2 4迭代器的辅助函数 advance p n 对p执行n次自增操作distance first last 计算两个迭代器first和last的距离 即对first执行多少次 操作后能够使得first last 13 10 2迭代器 10 3容器的基本功能与分类 容器类是容纳 包含一组元素或元素集合的对象 七种基本容器 向量 vector 双端队列 deque 列表 list 集合 set 多重集合 multiset 映射 map 多重映射 multimap 14 10 3容器的基本功能与分类 续 15 容器 Container 随机访问容器 RandomAccessContainer 可逆容器 ReversibleContainer 容器 Container list 容器的通用功能 容器的通用功能用默认构造函数构造空容器支持关系运算符 begin end 获得容器首 尾迭代器clear 将容器清空empty 判断容器是否为空size 得到容器元素个数s1 swap s2 将s1和s2两容器内容交换相关数据类型 S表示容器类型 S iterator 指向容器元素的迭代器类型S const iterator 常迭代器类型 16 10 3容器的基本功能与分类 可逆容器 随机访问容器 可逆容器S reverse iterator 逆向迭代器类型S const reverse iterator 逆向常迭代器类型rbegin 指向容器尾的逆向迭代器rend 指向容器首的逆向迭代器随机访问容器s n 获得容器s的第n个元素 17 10 3容器的基本功能与分类 10 4 1顺序容器的基本功能 顺序容器的接口赋值assign插入函数insert push front 只对list和deque push back删除函数erase clear pop front 只对list和deque pop back其他顺序容器访问函数front back改变大小resize 18 10 4顺序容器 例10 4顺序容器的基本操作 10 4 cpp 包含的头文件略去 输出指定的整型顺序容器的元素templatevoidprintContainer constchar msg constT 19 10 4顺序容器 10 4 1顺序容器的基本功能 例10 4 续 printContainer dequeatfirst s 用s容器的内容的逆序构造列表容器llistl s rbegin s rend printContainer listatfirst l 将列表容器l的每相邻两个容器顺序颠倒list iteratoriter l begin while iter l end intv iter iter l erase iter l insert iter v printContainer listatlast l 用列表容器l的内容给s赋值 将s输出s assign l begin l end printContainer dequeatlast s return0 20 10 4顺序容器 10 4 1顺序容器的基本功能 例10 4 续 运行结果如下 0986432154dequeatfirst 4512346890listatfirst 0986432154listatlast 9068341245dequeatlast 9068341245 21 10 4顺序容器 10 4 1顺序容器的基本功能 10 4 2三种顺序容器的特性 向量 Vector 特点一个可以扩展的动态数组随机访问 在尾部插入或删除元素快在中间或头部插入或删除元素慢向量的容量容量 capacity 实际分配空间的大小s capacity 返回当前容量s reserve n 若容量小于n 则对s进行扩展 使其容量至少为n 22 10 4顺序容器 双端队列 deque 特点在两端插入或删除元素快在中间插入或删除元素慢随机访问较快 但比向量容器慢 23 10 4顺序容器 10 4 2三种顺序容器的特性 例10 5奇偶排序 先按照从大到小顺序输出奇数 再按照从小到大顺序输出偶数 24 10 4顺序容器 10 4 2三种顺序容器的特性 头部分省略intmain istream iteratori1 cin i2 建立一对儿输入流迭代器vectors1 i1 i2 通过输入流迭代器从标准输入流中输入数据sort s1 begin s1 end 将输入的整数排序deques2 以下循环遍历s1for vector iteratoriter s1 begin iter s1 end iter if iter 2 0 偶数放到s2尾部s2 push back iter else 奇数放到s2首部s2 push front iter 将s2的结果输出copy s2 begin s2 end ostream iterator cout cout endl return0 列表 list 特点在任意位置插入和删除元素都很快不支持随机访问接合 splice 操作s1 splice p s2 q1 q2 将s2中 q1 q2 移动到s1中p所指向元素之前 25 10 4顺序容器 10 4 2三种顺序容器的特性 例10 6列表容器的splice操作 头部分省略intmain stringnames1 Alice Helen Lucy Susan stringnames2 Bob David Levin Mike lists1 names1 names1 4 用names1数组的内容构造列表s1lists2 names2 names2 4 用names2数组的内容构造列表s2 将s1的第一个元素放到s2的最后s2 splice s2 end s1 s1 begin list iteratoriter1 s1 begin iter1指向s1首advance iter1 2 iter1前进2个元素 它将指向s1第3个元素list iteratoriter2 s2 begin iter2指向s2首 iter2 iter2前进1个元素 它将指向s2第2个元素 26 10 4顺序容器 10 4 2三种顺序容器的特性 例10 6 续 27 list iteratoriter3 iter2 用iter2初始化iter3advance iter3 2 iter3前进2个元素 它将指向s2第4个元素 将 iter2 iter3 范围内的结点接到s1中iter1指向的结点前s1 splice iter1 s2 iter2 iter3 分别将s1和s2输出copy s1 begin s1 end ostream iterator cout cout cout cout endl return0 10 4顺序容器 10 4 2三种顺序容器的特性 运行结果 HelenLucyDavidLevinSusanBobMikeAlice 三种顺序容器的比较 STL所提供的三种顺序容器各有所长也各有所短 我们在编写程序时应当根据我们对容器所需要执行的操作来决定选择哪一种容器 如果需要执行大量的随机访问操作 而且当扩展容器时只需要向容器尾部加入新的元素 就应当选择向量容器vector 如果需要少量的随机访问操作 需要在容器两端插入或删除元素 则应当选择双端队列容器deque 如果不需要对容器进行随机访问 但是需要在中间位置插入或者删除元素 就应当选择列表容器list 28 10 4顺序容器 10 4 2三种顺序容器的特性 10 4 3顺序容器的插入迭代器 插入迭代器用于向容器头部 尾部或中间指定位置插入元素的迭代器包括前插迭代器 front inserter 后插迭代器 back insrter 和任意位置插入迭代器 inserter 例 lists back inserteriter s iter 5 通过iter把5插入s末尾 29 10 4顺序容器 10 4 4顺序容器的适配器 以顺序容器为基础构建一些常用数据结构栈 stack 最先压入的元素最后被弹出队列 queue 最先压入的元素最先被弹出优先级队列 priority queue 最 大 的元素最先被弹出 30 10 4顺序容器 例10 7利用栈反向输出单词 10 7 cpp 省略头部分intmain stacks stringstr cin str 从键盘输入一个字符串 将字符串的每个元素顺序压入栈中for string iteratoriter str begin iter str end iter s push iter 将栈中的元素顺序弹出并输出while s empty cout s top s pop cout endl return0 31 10 4顺序容器 10 4 4顺序容器的适配器 运行结果如下 congratulationssnoitalutargnoc 优先级队列 优先级队列也像栈和队列一样支持元素的压入和弹出 但元素弹出的顺序与元素的大小有关 每次弹出的总是容器中最 大 的一个元素 template classpriority queue 例10 8细胞分裂模拟一种细胞在诞生 即上次分裂 后会在500到2000秒内分裂为两个细胞 每个细胞又按照同样的规律继续分裂 32 10 4顺序容器 10 4 4顺序容器的适配器 10 8 cpp 头部分省略constintSPLIT TIME MIN 500 细胞分裂最短时间constintSPLIT TIME MAX 2000 细胞分裂最长时间classCell priority queuecellQueue classCell 细胞类private staticintcount 细胞总数intid 当前细胞编号inttime 细胞分裂时间public Cell intbirth id count birth为细胞诞生时间 初始化 确定细胞分裂时间time birth rand SPLIT TIME MAX SPLIT TIME MIN SPLIT TIME MIN intgetId const returnid 得到细胞编号intgetSplitTime const returntime 得到细胞分裂时间booloperators time 定义 33 例10 8 续 10 4顺序容器 10 4 4顺序容器的适配器 细胞分裂voidsplit Cellchild1 time child2 time 建立两个子细胞cout time 0 intt 模拟时间长度cout t cellQueue push Cell 0 将第一个细胞压入优先级队列while cellQueue top getSplitTime t cellQueue top split 模拟下一个细胞的分裂cellQueue pop 将刚刚分裂的细胞弹出 return0 34 例10 8 续 10 4顺序容器 10 4 4顺序容器的适配器 例10 8 续 运行结果如下 Simulationtime 5000971s Cell 0splitsto 1and 21719s Cell 1splitsto 3and 41956s Cell 2splitsto 5and 62845s Cell 6splitsto 7and 83551s Cell 3splitsto 9and 103640s Cell 4splitsto 11and 123919s Cell 5splitsto 13and 144162s Cell 10splitsto 15and 164197s Cell 8splitsto 17and 184317s Cell 7splitsto 19and 204686s Cell 13splitsto 21and 224809s Cell 12splitsto 23and 244818s Cell 17splitsto 25and 26 35 10 4顺序容器 10 4 4顺序容器的适配器 10 5 1关联容器分类和的基本功能 关联容器的特点每个关联容器都有一个键 key 可以根据键高效地查找元素接口插入 insert删除 erase查找 find定界 lower bound upper bound equal range计数 count 36 10 5关联容器 关联容器概念图 37 10 5关联容器 10 5 1关联容器的分类和基本功能 关联容器 AssociativeContainer 关联容器 AssociativeContainer multiset multimap set map 四种关联容器 单重关联容器 set和map 键值是唯一的 一个键值只能对应一个元素多重关联容器 multiset和multimap 键值是不唯一的 一个键值可以对应多个元素简单关联容器 set和multiset 容器只有一个类型参数 如set multiset 表示键类型容器的元素就是键本身二元关联容器 map和multimap 容器有两个类型参数 如map multimap 分别表示键和附加数据的类型容器的元素类型是pair 即由键类型和元素类型复合而成的二元组 38 10 5关联容器 10 5 1关联容器的分类和基本功能 10 5 2集合 set 集合用来存储一组无重复的元素 由于集合的元素本身是有序的 可以高效地查找指定元素 也可以方便地得到指定大小范围的元素在容器中所处的区间 例10 9输入一串实数 将重复的去掉 取最大和最小者的中值 分别输出小于等于此中值和大于等于此中值的实数 39 10 5关联容器 10 9 cpp 头部分省略intmain sets while true doublev cin v if v 0 break 输入0表示结束pair iterator bool r s insert v 尝试将v插入if r second 如果v已存在 输出提示信息cout iteratoriter1 s begin 得到第一个元素的迭代器set iteratoriter2 s end 得到末尾的迭代器doublemedium iter1 iter2 2 得到最小和最大元素的中值 输出小于或等于中值的元素cout cout cout medium copy s lower bound medium s end ostream iterator cout cout endl return0 40 10 5关联容器 10 5 2集合 set 例10 9 续 例10 9 续 运行结果如下 12 553 55792 505isduplicated2 5isduplicated medium 579 41 10 5关联容器 10 5 2集合 set 10 5 3映射 map 映射与集合同属于单重关联容器 它们的主要区别在于 集合的元素类型是键本身 而映射的元素类型是由键和附加数据所构成的二元组 在集合中按照键查找一个元素时 一般只是用来确定这个元素是否存在 而在映射中按照键查找一个元素时 除了能确定它的存在性外 还可以得到相应的附加数据 例10 10有五门课程 每门都有相应学分 从中选择三门 输出学分总和 42 10 5关联容器 10 10 cpp 头部分省略intmain mapcourses 将课程信息插入courses映射中courses insert make pair CSAPP 3 courses insert make pair C 2 courses insert make pair CSARCH 4 courses insert make pair COMPILER 4 courses insert make pair OS 5 intn 3 剩下的可选次数intsum 0 学分总和while n 0 stringname cin name 输入课程名称map iteratoriter courses find name 查找课程if iter courses end 判断是否找到coutsecond 累加学分courses erase iter 将刚选过的课程从映射中删除n cout Totalcredit sum endl 输出总学分return0 43 10 5关联容器 10 5 3映射 map 例10 10 续 例10 10 续 运行结果如下 C COMPILERC C isnotavailableCSAPPTotalcredit 9 44 10 5关联容器 10 5 3映射 map 例10 11统计一句话中每个字母出现的次数 10 11 cpp 头部分省略intmain maps 用来存储字母出现次数的映射charc 存储输入字符do cin c 输入下一个字符if isalpha c 判断是否是字母c tolower c 将字母转换为小写s c 将该字母的出现频率加1 while c 碰到 则结束输入 输出每个字母出现次数for map iteratoriter s begin iter s end iter coutfirstsecond cout endl return0 45 10 5关联容器 10 5 3映射 map 10 5 4多重集合 multiset 与多重映射 multimap 多重集合是允许有重复元素的集合 多重映射是允许一个键对应多个附加数据的映射 多重集合与集合 多重映射与映射的用法差不多 只在几个成员函数上有细微差异 其差异主要表现在去除了键必须唯一的限制 例10 12上课时间查询 46 10 5关联容器 10 12 cpp include include include includeusingnamespacestd intmain multimapcourses typedefmultimap iteratorCourseIter 将课程上课时间插入courses映射中courses insert make pair C 2 6 courses insert make pair COMPILER 3 1 courses insert make pair COMPILER 5 2 courses insert make pair OS 1 2 courses insert make pair OS 4 1 courses insert make pair OS 5 5 输入一个课程名 直到找到该课程为止 记下每周上课次数stringname intcount 47 10 5关联容器 10 5 4多重集合与多重映射 例10 12 续 do cin name count courses count name if count 0 coutrange courses equal range name for CourseIteriter range first iter range second iter coutsecond cout endl return0 48 10 5关联容器 10 5 4多重集合与多重映射 例10 12 续 运行结果如下 JAVACannotfindthiscourse OS3lesson s perweek 1 24 15 5 10 6 1函数对象 函数对象一个行为类似函数的对象可以没有参数 也可以带有若干参数其功能是获取一个值 或者改变操作的状态 例普通函数就是函数对象重载了 运算符的类的实例是函数对象 49 10 6函数对象 函数对象概念图 50 10 6函数对象 10 6 1函数对象 函数对象 Function 一元函数对象 UnaryFunction 二元函数对象 BinaryFunction 产生器 Generator 一元谓词 UnaryPredicate 二元谓词 BinaryPredicate 例10 13 例10 14 使用两种方式定义表示乘法的函数对象通过定义普通函数 例10 13 通过重载类的 运算符 例10 14 用到以下算法 templateTypeaccumulate InputIteratorfirst InputIteratorlast Typeval BinaryFunctionbinaryOp 对 first last 区间内的数据进行累 加 binaryOp为用二元函数对象表示的 加 运算符 val为累 加 的初值 51 10 6函数对象 10 6 1函数对象 include include 包含数值算法头文件usingnamespacestd 定义一个普通函数intmult intx inty returnx y intmain inta 1 2 3 4 5 constintN sizeof a sizeof int cout Theresultbymultiplingallelementsinais accumulate a a N 1 mult endl return0 52 10 6函数对象 10 6 1函数对象 例10 13 续 10 14 cpp include include 包含数值算法头文件usingnamespacestd classMultClass 定义MultClass类public intoperator intx inty const returnx y 重载操作符operator intmain inta 1 2 3 4 5 constintN sizeof a sizeof int cout Theresultbymultiplingallelementsinais accumulate a a N 1 MultClass 将类multclass传递给通用算法 endl return0 53 10 6函数对象 10 6 1函数对象 例10 14 续 STL提供的函数对象 用于算术运算的函数对象 一元函数对象 negate二元函数对象 plus minus multiplies divides modulus用于关系运算 逻辑运算的函数对象一元谓词 logical not二元谓词 equal to not equal to greater less greater equal less equal logical and logical or 54 10 6函数对象 10 6 1函数对象 例10 15利用STL标准函数对象 10 15 cpp include include 包含数值算法头文件 include 包含标准函数对象头文件usingnamespacestd intmain inta 1 2 3 4 5 constintN sizeof a sizeof int cout endl 将标准函数对象传递给通用算法return0 55 10 6函数对象 10 6 1函数对象 例10 16利用STL中的二元谓词函数对象 10 16 cpp 省略头部分 intmain intintArr 30 90 10 40 70 50 20 80 constintN sizeof intArr sizeof int vectora intArr intArr N cout cout t cout cout cout t cout endl return0 56 10 6函数对象 10 6 1函数对象 10 6 2函数适配器 绑定适配器将n元函数对象的指定参数绑定为一个常数 得到n 1元函数对象 bind1st bind2nd组合适配器将指定谓词的结果取反 not1 not2指针函数适配器对一般函数指针使用 使之能够作为其它函数适配器的输入 ptr fun成员函数适配器对成员函数指针使用 把n元成员函数适配为n 1元函数对象 该函数对象的第一个参数为调用该成员函数时的目的对象 ptr fun ptr fun ref 57 10 6函数对象 例10 17bind2nd产生binder2nd函数适配器实例 10 17 cpp include include include includeusingnamespacestd intmain intintArr 30 90 10 40 70 50 20 80 constintN sizeof intArr sizeof int vectora intArr intArr N vector iteratorp find if a begin a end bind2nd greater 40 if p a end cout noelementgreaterthan40 endl elsecout firstelementgreaterthan40is p endl return0 58 10 6函数对象 10 6 2函数适配器 例10 18ptr fun not1和not2产生函数适配器实例 10 18 cpp 头部分省略boolg intx inty returnx y intmain intintArr 30 90 10 40 70 50 20 80 constintN sizeof intArr sizeof int vectora intArr intArr N vector iteratorp p find if a begin a end bind2nd ptr fun g 40 if p a end cout noelementgreaterthan40 endl elsecout firstelementgreaterthan40is p endl 59 10 6函数对象 10 6 2函数适配器 60 10 6函数对象 10 6 2函数适配器 p find if a begin a end not1 bind2nd greater 15 if p a end cout 15 if p a end cout noelementisnotgreaterthan15 endl elsecout firstelementthatisnotgreaterthan15is p endl return0 例10 17 续 例10 19成员函数适配器实例 10 19 cpp include include include includeusingnamespacestd structCar intid Car intid this id id voiddisplay const coutpcars vectorcars 61 10 6函数对象 10 6 2函数适配器 62 10 6函数对象 10 6 2函数适配器 for inti 0 i 5 i pcars push back newCar i for inti 5 i 10 i cars push back Car i cout elementsinpcars endl for each pcars begin pcars end std mem fun 例10 19 续 10 7 1STL算法基础 STL算法本身是一种函数模版通过迭代器获得输入数据通过函数对象对数据进行处理通过迭代器将结果输出STL算法是通用的 独立于具体的数据类型 容器类型STL算法分类不可变序列算法可变序列算法排序和搜索算法数值算法 63 10 7算法 10 7 2不可变序列算法 不可变序列算法不直接修改所操作的容器内容的算法用于查找指定元素 比较两个序列是否相等 对元素进行计数等例 templateInputIteratorfind if InputIteratorfirst InputIteratorlast UnaryPredicatepred 用于查找 first last 区间内pred x 为真的首个元素 64 10 7算法 例10 20不可变序列算法应用实例 10 20 cpp 头部分省略 intmain intiarray 0 1 2 3 4 5 6 6 6 7 8 vectorivector iarray iarray sizeof iarray sizeof int intiarray1 6 6 vectorivector1 iarray1 iarray1 sizeof iarray1 sizeof int intiarray2 5 6 vectorivector2 iarray2 iarray2 sizeof iarray2 sizeof int intiarray3 0 1 2 3 4 5 7 7 7 9 7 vectorivector3 iarray3 iarray3 sizeof iarray3 sizeof int 找出ivector之中相邻元素值相等的第一个元素cout 7 endl 65 10 7算法 10 7 2不可变序列算法 找出ivector之中大于2的第一个元素所在位置的元素cout 2 iterator vector iterator result mismatch ivector begin ivector end ivector3 begin cout result first ivector begin endl return0 66 10 7算法 10 7 2不可变序列算法 例10 20 续 10 7 3可变序列算法 可变序列算法可以修改它们所操作的容器对象包括对序列进行复制 删除 替换 倒序 旋转 交换 变换 分割 去重 填充 洗牌的算法及生成一个序列的算法例 templateInputIteratorfind if ForwardIteratorfirst ForwardIteratorlast constT把 first last 区间内的元素全部改写为x 67 10 7算法 例10 21 以可变序列算法对数据序列进行复制 生成 删除 替换 倒序 旋转等可变性操作 68 10 7算法 10 7 3可变序列算法 10 21 cpp 头部分省略classevenByTwo private intx public evenByTwo x 0 intoperator returnx 2 intmain intiarray1 0 1 2 3 4 4 5 5 6 6 6 6 6 7 8 intiarray2 0 1 2 3 4 5 6 6 6 7 8 vectorivector1 iarray1 iarray1 sizeof iarray1 sizeof int vectorivector2 iarray2 iarray2 sizeof iarray2 sizeof int vectorivector3 2 ostream iteratoroutput cout 定义流迭代器用于输出数据 迭代遍历ivector3区间 每个元素填上 1fill ivector3 begin ivector3 end 1 copy ivector3 begin ivector3 end output 使用copy进行输出cout endl 迭代遍历ivector3区间 对每一个元素进行evenByTwo操作generate ivector3 begin ivector3 end evenByTwo copy ivector3 begin ivector3 end output cout endl 69 10 7算法 10 7 3可变序列算法 例10 21 续 将删除元素6后的ivector2序列置于另一个容器ivector4之中vectorivector4 remove copy ivector2 begin ivector2 end back inserter ivector4 6 copy ivector4 begin ivector4 end output cout 6 ivector2 end copy ivector2 begin ivector2 end output cout endl 将所有的元素值6 改为元素值3replace ivector2 begin ivector2 end 6 3 copy ivector2 begin ivector2 end output cout endl 逆向重排每一个元素reverse ivector2 begin ivector2 end copy ivector2 begin ivector2 end output cout endl 旋转 互换元素 first middle 和 middle end 结果直接输出rotate copy ivector2 begin ivector2 begin 3 ivector2 end output cout endl return0 70 10 7算法 10 7 3可变序列算法 例10 21 续 例10 21 续 运行结果 1 1240123457866678333788733333873 71 10 7算法 10 7 3可变序列算法 10 7 4排序和搜索算法 排序和搜索算法对序列进行排序对两有序序列进行合并对有序序列进行搜索有序序列的集合操作堆算法例 templatevoidsort RandomAccessIteratorfirst RandomAccessIteratorlast UnaryPredicatecomp 以函数对象comp为 对 first last 区间内的数据进行排序 72 10 7算法 例10 22排序与搜索算法示例 10 22 cpp 头部分省略 intmain intiarray 26 17 15 22 23 33 32 40 vectorivector iarray iarray sizeof iarray sizeof int 查找并输出第一个最大值元素及其位置vector iteratorp max element ivector begin ivector end intn p ivector begin coutivector1 5 局部排序并复制到别处partial sort copy ivector begin ivector end ivector1 begin ivector1 end copy ivector1 begin ivector1 end ostream iterator cout cout cout cout endl 73 10 7算法 10 7 4排序和搜索算法 返回小于等于24和大于等于24的元素的位置coutivector2 13 merge ivector begin ivector end ivector1 begin ivector1 end ivector2 begin copy ivector2 begin ivector2 end ostream iterator cout cout cout cout cout cout endl 74 10 7算法 10 7 4排序和搜索算法 例10 22 续 合并两个有序序列 然后就地替换intiarray3 1 3 5 7 2 4 6 8 vectorivector3 iarray3 iarray3 sizeof iarray3 sizeof int inplace merge ivector3 begin ivector3 begin 4 ivector3 end copy ivector3 begin ivector3 end ostream iterator cout coutivector4 iarray4 iarray4 sizeof iarray4 sizeof int cout lexicographical compare ivector3 begin ivector3 end ivector4 begin ivector4 end endl return0 75 10 7算法 10 7 4排序和搜索算法 例10 22 续 10 7 5数值算法 数值算法求序列中元素的 和 部分 和 相邻元素的 差 或两序列的内积求 和 的 求 差 的 以及求内积的 和 都可由函数对象指定例 templateOutputIteratorpartial sum InputIteratorfirst InputIteratorlast OutputIteratorresult BinaryFunctionop 对 first last 内的元素求部分 和 所谓部分 和 是一个长度与输入序列相同的序列 其第n项为输入序列前n个元素的 和 以函数对象op为 运算符 结果通过result输出 返回的迭代器指向输出序列最后一个元素的下一个元素 76 10 7算法 例10 23数值算法示例 10 23 cpp 头部分省略intmain intiarray 1 2 3 4 5 vectorivector iarray iarray sizeof iarray sizeof int 元素的累计cout cout cout cout cout endl return0 77 10 7算法 10 7 5数值算法 10 8综合实例 对个人银行账户管理程序的改进 使用向量容器vector来管理账户列表本例还增加了一个多重映射来存储每一笔账目 该映射的键是账目的日期 附加数据是账目的详细内容 例10 24个人银行账户管理程序程序分为6个文件 date h是日期类头文件 date cpp是日期类实现文件 accumulator h为按日将数值累加的Accumulator类的头文件 account h是各个储蓄账户类定义头文件 account cpp是各个储蓄账户类实现文件 10 24 cpp是主函数文件 78 date h ifndef DATE H define DATE H classDate 日期类private intyear 年intmonth 月intday 日inttotalDays 该日期是从公元元年1月1日开始的第几天public Date intyear 1 in