C++实用教程[郑阿奇主编]16.ppt

第16章标准模板库 STL 16 1迭代器 16 1 1迭代器的由来 在STL中 迭代器是一种 特殊 的指针 用来指定或引用容器中元素的位置正是因为对不同容器的操作具有相同的实现代码 所以才会形成STL的算法器及迭代器以优化和简化算法代码 16 1 2迭代器的类型 STL提供了5种不同的迭代器 输入 输出 正向 双向和随机访问迭代器 1 输入迭代器 它是一种单向迭代器 只可递增 不可回退 2 输出迭代器 它是一种单向迭代器 只不过它是向容器中写入元素 3 正向迭代器 它是输入迭代器和输出迭代器功能的组合 其操作元素总是向前移动 即支持 操作 与输入迭代器或输出迭代器不同的是 它多次遍历的顺序都是相同的 4 双向迭代器 它常用于reserse 逆序 等操作 支持指针的 和操作 5 随机访问迭代器 它具有双向迭代器的所有功能 同时增加了直接访问容器中任何元素的功能 即可向前 向后跳过任意多个元素 以及用于对元素排序的关系运算等 16 2容器类 容器是一个与数组类似的单元 可以存取若干元素主要容器类有 deque 双端队列 list 链表 列表 queue 队列 stack 栈 vector 向量 map 映像 multimap 多重映像 set 集合 和multiset 多重集合 16 2 1向量 链表和双端队列 1 模型概述向量 链表和双端队列都可以看成是顺序存储的线性表 只是链表不像向量和双端队列那样具有随机访问的能力2 deque list和vectortemplate classvector template classdeque template classlist 一旦建立了容器类vector list或deque实例化类对象 就可以通过对象进行下列常用操作 1 元素的插入操作 用于元素插入操作的成员函数为insert push front和push back 2 元素的删除和清除操作 用于删除元素操作的成员函数有erase pop front和pop back clear用于清除操作 3 元素访问操作 容器类vector和deque除了提供下标运算符 来引用指定位置的对象元素的内存空间外 还提供下列元素访问操作 4 迭代器和空间大小属性操作 容器类vector list和deque都提供下列有关迭代器和空间大小属性的常用操作 5 链表操作 与容器类vector和deque不同的是 容器类list自身还有不同的常用操作 如反序 排序 合并等 例Ex Vector 向量容器类示例 include include 向量容器类头文件包含 include 迭代器头文件包含 include 算法器头文件包含usingnamespacestd 演示iterator操作voidshow vector 演示 操作 include include 向量容器类头文件包含 include 迭代器头文件包含 include 算法器头文件包含usingnamespacestd 演示iterator操作voidshow vector 程序运行结果如下 4 list示例 例Ex List 链表容器类示例 include include 链表容器类头文件包含 include 迭代器头文件包含usingnamespacestd 演示iterator操作voidshow list intmain listv v push back 20 v push back 40 v push back 5 v push back 7 list iteratorip v begin ip v insert ip 13 v insert ip 7 show v 输出所有结点元素v remove 7 移除 7结点v reverse show v v sort show v listl l push back 12 l push back 8 l push back 16 l push back 7 v splice v end l show v show l v pop back v pop back v pop back v pop back show v l push back 1 l push back 8 l push back 16 v merge l show v show l return0 程序运行结果如下 16 2 2栈和队列 栈 stack 是一种 FILO 先进后出 或 LIFO 后进先出 的线性表 它只允许在表的一端进行插入和删除操作 而队列 queue 是一种 FIFO 先进先出 的线性表 与栈刚好相反 在队列中 只允许在表的一端插入元素 而在另一端删除元素 定义对象时 它们都可以有下列简单的形式 Xv X v 使用向量容器来构造 注意 vector 的最后面是两个大于符号 它们之间一定要有空格 说明 1 ANSI ISOC 类模板stack和deque中都有一个protected数据成员c 其定义如下 protected Containerc 但在VisualC 2005中 该数据成员是公有的 因此可以在对象中通过c访问构造时指定的容器类模板的成员 对于VisualC 6 0需要通过派生才能使用该数据成员c 2 另外 类模板stack和deque还都重载了运算符 用于两个栈或两个队列之间的关系比较 例Ex Stack 栈类模板示例 include include 栈模板头文件包含 include 向量容器类头文件包含 include 迭代器头文件包含usingnamespacestd typedefstack STACK classCStack publicSTACK public voidshow 遍历操作 if empty cout iteratorip c begin 定义指针while ip c end cout ip t ip cout endl 清栈操作voidclear while empty pop intmain CStackv v push 20 v push 40 v push 5 v push 7 v show v top 8 v show v pop v show v clear v show return0 程序运行结果如下 16 2 3映像 1 概述与map概念相同 关联容器类multimap支持的是多对一关系 即一个键对应于多个值 map和multimap都支持双向迭代器 可以实现多路遍历操作2 map容器类容器类map具有下列声明 template classAllocator allocator classmap 一旦建立了容器类map的实例化对象 就可以通过实例化类对象进行下列常用操作 1 元素的插入操作 需要说明的是 这里操作的元素是指 键 和 值 的对子 简称键值对 在容器类map中 用于元素插入操作的成员函数为insert 2 元素的删除和清除操作 容器类map用于删除元素操作的成员函数是erase 用于清除操作的是clear 3 元素访问操作 容器类map只提供下标运算符 来引用指定位置元素的内存空间 4 迭代器和空间大小属性操作 5 映像操作另外 容器类map还重载了运算符 用于两个映像之间的关系比较 例Ex Map 映像容器类示例 pragmawarning disable 4786 避免string使用中的警告出现 include include 映像容器类头文件包含 include 迭代器头文件包含 include 字符串类头文件包含usingnamespacestd typedefmap STR2INT 定义类型名以便后面使用typedefSTR2INT iteratorPOS 定义类型名以便后面使用 输出键值对voidshowpair POSpos cout 主键为 pos first t值为 pos second endl 遍历输出voidshow STR2INT 显示某范围的键值对 演示lower bound和upper bound voidshowu STR2INT intmain STR2INTv 添加操作v insert STR2INT value type Zero 0 v insert STR2INT value type One 1 v insert STR2INT value type Two 2 v insert STR2INT value type Three 3 v Four 4 v Five 5 v Six 6 v Seven 7 v Eight 8 show v 删除操作coutpp v equal range FIVE showpair pp first showpair pp second return0 程序运行结果如下 16 2 4集合 容器类set具有下列声明 template classAllocator allocator classset 25 可编辑 例Ex Set 集合容器类示例 pragmawarning disable 4786 include include 映像容器类头文件包含 include 迭代器头文件包含 include 字符串类头文件包含usingnamespacestd typedefset STRSET 定义类型以便后面使用typedefSTRSET iteratorPOS 定义类型以便后面使用 遍历输出voidshow STRSET 显示某范围的键值对 演示lower bound和upper bound voidshowu STRSET intmain STRSETv 添加操作v insert Zero v insert One v insert Two v insert Three v insert Four v insert Five v insert Six show v 删除操作coutpp v equal range FIVE cout pp first endl cout pp second endl return0 程序运行结果如下 16 3算法 16 3 1概述STL算法部分主要由头文件 和组成 16 3 2copy和流迭代器1 copy函数模板copy将序列中某个范围的元素复制到另一个序列中 例Ex Copy copy函数使用示例 include include include includeusingnamespacestd typedefvectorIntVector intmain intarr 10 2 3 7 8 4 11 5 9 1 13 IntVectorv 8 copy arr arr 8 v begin ostream iteratorout cout copy arr arr 10 out cout endl copy v begin v end out cout endl return0 程序运行结果如下 2 流迭代器 输出流迭代器ostream iterator是STL预定义的迭代器类模板 它具有下列定义 template classostream iterator publiciterator public ostream iterator ostream type 16 3 3find 函数模板find用于查找 它的原型如下 templateInItfind InItfirst InItlast constT 例Ex Find find函数使用示例 include include include includeusingnamespacestd typedefvectorIntVector classUSERDO public booloperator inti 运算符 重载函数 return i 5 intmain ostream iteratorout cout inta 1 3 5 6 6 7 7 7 8 8 8 8 整数数组aconstintANUM sizeof a sizeof int IntVectorv a a ANUM A 构造copy v begin v end out cout 7 if it v end cout 找到 it 的位置在 it v begin endl start it 1 while it v end cout endl start v begin do C 循环找出所有大于7的数it find if start v end bind2nd greater 7 if it v end cout 找到 it 的位置在 it v begin endl start it 1 while it v end cout endl start v begin do D 循环找出所有 5 8 的数it find if start v end USERDO Eif it v end cout 找到 it 的位置在 it v begin endl start it 1 while it v end return0 程序运行结果如下 16 3 4sort 函数模板sort用于为指定序列排序 它的原型如下 sort RanIt表示随机访问迭代器templatevoidsort RanItfirst RanItlast templatevoidsort RanItfirst RanItlast BPredpred 其功能是将 first last 之间的序列按从小到大的升序进行排序 例Ex Sort sort函数使用示例 include include include includeusingnamespacestd classC2Pred public C2Pred inta intb first a second b voidshow cout first second endl booloperator constC2Pred intmain vectorvect inti for i 0 i 5 i C2Predob 10 i i 3 vect push back ob for i 0 i vect size i vect i show cout 按first值从小到大排序 endl sort vect begin vect end for i 0 i vect size i vect i show cout 按second值从小到大排序 endl sort vect begin vect end less second for i 0 i vect size i vect i show return0 程序运行结果如下 16 4综合应用实例 include include include 链表类头文件包含 include 迭代器头文件包含 include include includeusingnamespacestd classCStudent ostream classCStudent public CStudent CStudent char name char id floats1 floats2 floats3 voidprint intn 1 char GetName returnstrName friendostream voidCStudent print intn n为序号 0 cout0 cout setw 6 n cout setw 20 strName setw 10 strID setw 10 fScore 0 setw 10 fScore 1 setw 10 fScore 2 setw 10 total endl ostream classCStuList public voidAdd CStudentstu 添加记录intSeek char name CStudent vo