标准模板库(STL).ppt

第十一章标准模板库 STL 库 library 是一系列程序组件的集合 它们可以在不同的程序中重复使用 库函数设计的第一位的要求就是通用性 模板 template 为通用性带来了不可估量的前景 我们可以在使用模板时才对某些类型作选择 模板是标准C 实现代码复用的有力工具 特别是在有关数据结构的算法方面 为程序员提供大量实用的库是C 的又一特色 标准模板库 StandardTemplateLibrary 是ANSI ISOC 最有特色 最实用的部分之一 STL包含了容器类 container 迭代子 iterator 和算法 algorithm 三个部分 泛型算法 genericalgorithm 和函数对象 functionobject 的概念与使用使算法摆脱了对不同类型数据个性操作的依赖 这样就可以编出更具通用性的算法 11 1标准模板库简介 11 3顺序容器 11 2迭代子类 11 5容器适配器 11 7VC 中的STL 11 6泛型算法与函数对象 11 4关联容器 第十一章标准模板库 STL 11 1标准模板库简介 容器类是管理序列的类 是容纳一组对象或对象集的类 通过由容器类提供的成员函数 可以实现诸如向序列中插入元素 删除元素 查找元素等操作 这些成员函数通过返回迭代子来指定元素在序列中的位置 STL提供了一个标准化的模板化的对象容器库 包含多种数据结构及其算法 可以节省大量的时间和精力 而且程序是高质量的 迭代子是面向对象版本的指针 它提供了访问容器或序列中每个对象的方法 这样就可以把算法用于容器所管理的序列 泛型算法不依赖于具体的容器 通用的算法更易于扩充 泛型算法中采用函数对象 functionobject 引入不同情况下同一算法的差异 它没有使用继承和多态 避免了虚函数的开销 使STL效率更高 11 1标准模板库简介 容器分为三大类 11 1标准模板库简介 顺序容器和关联容器称为第一类容器 first classcontainer 另外有四种容器称为近容器 nearcontainer C语言风格数组 字符串string 操作1 0标志值的bitset和进行高速数学矢量运算的valarray 它们虽然提供与第一类容器类似的功能 但没有全部功能 STL也使容器提供类似的接口 许多基本操作是所有容器都适用的 而有些操作则适用于类似容器的子集 这样就可以用新的类来扩展STL 这些函数和运算符可通称为容器的接口 表11 2所有标准库容器共有的函数 11 1标准模板库简介 11 1标准模板库简介 表11 3只在第一类中的函数 11 1标准模板库简介 使用STL容器或容器适配器 要包含定义该容器模板类头文件 参见表11 4 这些头文件的内容都在std名字空间域中 程序中必须加以说明 表11 4标准容器库的头文件 11 1标准模板库简介 在有关数组 链表和二叉树等线性表和非线性表的讨论中 若要访问其中一个元素 结点 我们可以用下标或者指针去访问 而下标实际上也是一种指针即地址 访问时取地址的方式还有很多 一系列的访问方法都可以抽象为迭代子 iterator 访问方法最终要归于内存地址的获得 所以说迭代子是面向对象版本的指针 迭代子与指针有许多相同之处 但迭代子保存所操作的特定容器需要的状态信息 从而实现与每种容器类型相适应的迭代子 而且有些迭代子操作在所有容器中是一致的 如 运算符总是返回容器下一个元素的迭代子 间接引用符 总是表示迭代子指向的容器元素 迭代子用来将STL的各部分结合在一起 从本质上说 STL提供的所有算法都是模板 我们可以通过使用自己指定的迭代子来对这些模板实例化 迭代子可以包括指针 但又不仅是一个指针 11 1标准模板库简介 STL最大的优点是提供能在各种容器中通用的算法 例如插入 删除 查找 排序等等 STL提供70种左右的标准算法 算法只是间接通过迭代子操作容器元素 算法通常返回迭代子 一个算法通常可用于多个不同的容器 所以称为泛型算法 genericalgorithm 算法分为 修改容器的算法 即变化序列算法 mutating sequencealgorithm 如copy remove replace swap 等 不修改容器的算法 即非变化序列算法 non mutating sequencealgorithm 如count find 等 数字型算法 11 2迭代子类 C 标准库中有五种预定义迭代子 其功能最强最灵活的是随机访问迭代子 输入InputIterator输出OutputIterator正向ForwardIterator双向BidirectionalIterator随机访问RandomAccessIterator 从容器中读取元素 输入迭代子只能一次一个元素地向前移动 即从容器开头到容器末尾 要重读必须从头开始 向容器写入元素 输出迭代子只能一次一个元素地向前移动 输出迭代子要重写 必须从头开始 组合输入迭代子和输出迭代子的功能 并保留在容器中的位置 作为状态信息 所以重新读写不必从头开始 组合正向迭代子功能与逆向移动功能 即从容器序列末尾到容器序列开头 组合双向迭代子的功能 并能直接访问容器中的任意元素 即可向前或向后跳过任意个元素 表11 5迭代子类别 11 2迭代子类 标准库定义迭代子的层次结构 按这个层次 从上到下 功能越来越强 但不是继承 图11 1迭代子层次 11 2迭代子类 只有第一类容器能用迭代子遍历 表11 6STL容器支持的迭代子类别 表11 7各种迭代子可执行的操作 结合find 算法讨论迭代子与泛型算法的关系 find 定义如下 templateInputIteratorfind InputIteratorfirst InputIteratorlast countTvalue for first last first if value first returnfirst returnlast 可见 泛型算法不直接访问容器的元素 与容器无关 元素的全部访问和遍历都通过迭代子实现 并不需要预知容器类型 11 2迭代子类 例11 1 寻找数组元素 include includeusingnamespacestd voidmain intsearch value ia 9 47 29 37 23 11 7 5 31 41 cout search value int presult find 这里a 9 数组元素并不存在 但内存地址单元存在 11 2迭代子类 例11 2 寻找vector容器元素 include include includeusingnamespacestd voidmain intsearch value ia 9 47 29 37 23 11 7 5 31 41 vectorvec ia ia 9 数据填入vectorcout search value vector iteratorpresult 定义迭代子presult find vec begin vec end search value cout 数值 search value presult vec end 不存在 存在 endl 11 2迭代子类 在头文件中还定义了一些专用迭代子 反转型迭代子 reverseiterator 把一切都颠倒过来 正向遍历一个第一类容器时 如果用了反转迭代子 实际上实现的是反向遍历 第一类容器支持两对操作 begin 和end 分别返回指向容器首元素和容器的末元素的后继的迭代子 而rbegin 和rend 分别返回指向容器末元素和容器的首元素的前导的迭代子 后一对操作用于支持反转型迭代子 vectorveco vector reverse iteratorr iter for r iter veco rbegin 将r iter指向到末元素r iter veco rend 不等于首元素的前导r iter 实际是上是递减如果要把升序的序列改为降序的序列 只要使用反转迭代子就可以了 反转迭代子定义为随机迭代子 11 2迭代子类 插入型迭代子 insertioniterator 可以用输出迭代子来产生一个元素序列 可以添加元素而不必重写 有三种插入迭代子 back insert iterator是输出迭代子 用来将产生的元素添加到类型为Type的容器对象的末端 就象在一个字符串末尾加一个串 strcat front insert iterator是输出迭代子 用来将产生的元素添加到容器的前端 就是 产生出来的元素以逆序方式结束于被控序列前端 insert iterator也是输出迭代子 它用来将产生的元素插入到一个由迭代子 第二个参数Iter 指定的元素的前面 与之对应的也有三个相关的适配器函数 它们返回特定的插入迭代子 back inserter Type 它使用容器的push back 插入操作代替赋值操作符 实参是容器自己 返回一个back inserter迭代子 front insertor Type 使用容器的push front 插入操作代替赋值操作符 实参也是容器本身 返回一个front inserter迭代子 inserter Type Iter 用容器的insert 插入操作符代替赋值操作符 inserter 要求两个实参 容器本身和它的一个迭代子指示起始插入的位置 标记起始插入位置的迭代子并不保持不变 而是随每个被插入的元素而递增 这样每个元素就能顺序被插入 11 2迭代子类 流迭代子有输入流迭代子 istream iterator 和输出流迭代子 ostream iterator 在STL中为输入 输出流iostream提供了迭代子 它们可以与标准库容器类型和泛型算法结合起来工作 使用这两个迭代子必须包含头文件 输入流迭代子 istream iterator 类支持在istream及其派生类 如ifstream 上的迭代子操作 istream iterator声明方式为 istream iterator迭代子标识符 istream Type为已定义了输入操作的类型 实参可以是任意公有派生的istream的子类型的对象 输出流也有对应的ostream iterator类支持 其声明方式为 ostream iterator迭代子标识符 ostream 实参同样可以是公有派生子类型对象ostream iterator迭代子标识符 ostream char 第二参数为C风格字符串 11 2迭代子类 例11 3 用istreamiterator从标准输入读入一个整数集到vector中 include include include include includeusingnamespacestd voidmain istream iteratorinput cin istream iteratorend of stream vectorvec copy input end of stream inserter vec vec begin 输入 Z结束流sort vec begin vec end greater 升序排列ostream iteratoroutput cout unique copy vec begin vec end output 11 2迭代子类 首先 用一个istream iterator迭代子input 其实参为cin 即标准输入 读入一个整数集到一个矢量类对象中 出现光标后 可输入 4139572317191311373123294139 Z 例中泛型算法copy 定义如下 templateOutputIteratorcopy InputIteratorfirst InputIteratorlast OutputInteratorx for first last x first x firstreturn x end of stream是指示文件 流 的结束位置 它使用了缺省的构造函数 不必由读者去为它定参数和做任何事 这里标识符是无关紧要的 重要的是无参 调用缺省的构造函数 输入时必须在最后一个数字后加分隔符 然后加Ctrl Z结束 拷贝算法要求提供一对iterator来指示文件 流 内部的开始和结束位置 我们使用由istream对象初始化的istream iterator提供开始位置 本例中为input 本例中插入迭代子inserter作为copy的第三个参数 它是输出型的 把流插入vec 11 2迭代子类 泛型算法sort 为升序排序算法 声明如下templatevoidsort RandomAccessIteratorfirst RandomAccessInteratorlast Prp 第三参数为排序方式 greater 是预定义的 大于 函数对象 排序时用它来比较数值大小 缺省时为 小于 即升序排序 例中用输出迭代子output来输出 泛型算法unique copy 复制一个序列 并删除序列中所有重复元素 本例中 拷贝到output迭代子 即用空格分隔各整数的标准输出 输出为 413937312923191713119753 流缓冲迭代子 这是STL后添加的一对迭代子 用来直接从一个流缓冲区 streambuffer 中插入或提取某种类型 通常为char 的元素 11 3顺序容器 1 矢量 vector 类提供了具有连续内存地址的数据结构 通过下标运算符 直接有效地访问矢量的任何元素 与数组不同 矢量的内存用尽时 矢量自动分配更大的连续内存区 将原先的元素复制到新的内存区 并释放旧的内存区 这是矢量类的优点 在这里内存分配是由分配子 allocator 完成 矢量可以用来实现队列 堆栈 列表和其他更复杂的结构 vector支持随机访问迭代子 具有最强的功能 vector的迭代子通常实现为vector元素的指针 所谓选择容器类 实际上很大部分是在选择所支持的迭代子 C 标准模板库提供三种顺序容器 vector list和deque vector类和deque类是以数组为基础的 list类是以双向链表为基础的 11 3顺序容器 使用向量容器的声明如下 include vectorvi 定义存放整形序列的向量容器对象vi 长度为0的空vectorvectorvf 存放实型序列的向量容器vectorvch 存放字符序列的向量容器vectorvstr 存放字符串序列的向量容器 使用方法是典型的函数模板的使用方法 调用缺省的构造函数 创建长度为0的向量 矢量容器有多种构造函数 包括构造一个有n个元素的矢量 每个元素都是由元素缺省的构造函数所构造出来的 还可以为每个元素用同一个对象来赋初值 还包括拷贝构造函数 可以由一个已有的矢量容器对象来初始化新容器各元素的构造函数 这些构造函数还可以显式给出分配子 allocator 对象 11 3顺序容器 2 列表 list 是由双向链表 doublylinkedlist 组成的 我们也已经在有关链表的一节中介绍过了 它有两个指针域 可以向前也可以向后进行访问 但不能随机访问 即支持的迭代子类型为双向迭代子 使用起来很方便 与我们在 7 2节中定义的双链表类模板相似 但通用性更好 使用更方便 列表的定义在头文件中 3 双端队列 deque double endedqueue 类 双端队列允许在队列的两端进行操作 以顺序表为基础 支持随机访问迭代子 双端队列有高度的灵活性 它放松了访问的限制 对象既可从队首进队 也可以从队尾进队 同样也可从任一端出队 除了可从队首和队尾移走对象外 也支持通过使用下标操作符 进行访问 要增加存储空间时 可以在内存块中对deque两端分别进行分配 并且新分配的存储空间保存为指向这些块的指针数组 这样双端队列可以利用不连续内存空间 因此它的迭代子比vector的迭代子更加智能化 为双端队列分配的存储块 往往要等删除双端队列时才释放 它比重复分配 再分配和释放 更有效 但也更浪费内存 使用双端队列 必须包含头文件 11 4关联容器 关联容器 associativecontainer 能通过关键字 searchkey 直接访问 存储和读取元素 四个关联容器为 集合 set 多重集合 multiset 映射 map 和多重映射 multimap 集合和多重集合类提供了控制数值集合的操作 其中数值是关键字 即不必另有一组值与每个关键字相关联 集合与多重集合类的主要差别在于多重集合允许重复的关键字 key 而集合不允许重复的关键字 元素的顺序由比较器函数对象 comparatorfunctionobject 确定 如对整型multiset 只要用比较器函数对象less排序关键字 元素即可按升序排列 multiset和set通常实现为红黑二叉排序树 在生成二叉排序树时 当输入数据为已排好序时 会形成高度不平衡的只有半边的斜杠形的树 即退化为链表 二叉排序树只有形成平衡的树 也就是接近完全二叉数或满二叉树的形状才能达到对半查找的效果 红黑二叉排序树是实现平衡二叉排序树的方法之一 11 4关联容器 例11 4 整型多重集合关联容器类的演示 类模板声明 template typenameA allocator classmultiset 模板参数表中的非类型参数同样可有缺省值 include include 包含集合头文件 include 包含算法头文件usingnamespacestd C 标准库名字空间域typedefmultisetINTMS 特例取名INTMS 整型多重集合按升序排列 voidmain constintsize 16 inta size 17 11 29 89 73 53 61 37 41 29 3 47 31 59 5 2 INTMSintMultiset a a size 用a来初始化INTMS容器实例ostream iteratoroutput cout 整型输出迭代子output 可通过cout输出一个用空格分隔的整数cout 这里原来有 intMultiset count 17 个数值17 endl 查找有几个关键字17 11 4关联容器 intMultiset insert 17 插入一个重复的数17cout 输入后这里有 intMultiset count 17 个数值17 endl INTMS const iteratorresult const iterator使程序可读INTMS的元素 但不让程序修改它的元素 result为INTMS的迭代子result intMultiset find 18 找到则返回所在位置 设找到返回与调end 返回的同样值if result intMultiset end cout 没找到值18 endl elsecout 找到值18 endl cout intMultiset容器中有 endl copy intMultiset begin intMultiset end output 输出容器中全部元素cout endl 运行结果为 这里原来有1个数值17输入后这里有2个数值17没找到值18容器中有 2351117172929313741475359617389请注意multiset容器中自动作了升序排列 11 4关联容器 映射和多重映射类提供了操作与关键字相关联的映射值 mappedvalue 的方法 映射和多重映射的主要差别在于多重映射允许存放与映射值相关联的重复关键字 而映射只允许存放与映射值一一对应的单一关键字 多重映射和映射关联容器类用于快速存储和读取关键字与相关值 关键字 数值对 key valuepair 如果保存学生的简明资料 要求按学号排序 使用映射关联容器 因为不会重号 是最合适的 如用姓名排序 因姓名可能重复 使用多重映射更为合适 使用时要用头文件 11 5容器适配器 STL提供了三个容器适配器 containeradapter 栈 队列和优先级队 栈是标准的栈 使用时要用头文件 队也是标准的 使用时要用头文件 所谓适配器并不独立 它依附在一个顺序容器上 如要声明一个用矢量实现的字符型堆栈 可使用如下声明 stack sk 优先级队列 priority queue 适配器实现优先级队列 元素插入是自动按优先级顺序插入 使最高优先级元素首先从优先级队列中取出 优先级队列 priority queue 的每个常用操作都实现为内联函数 调用基础容器的相应函数时 可避免二次函数调用的开销 常用矢量为基础容器 缺省情况下priority queue实现时用vector为基础数据结构 然后它就可以象顺序容器一样使用 但是它没有自己的构造和析构函数 它使用其实现类 如vector 的构造和析构函数 就象一个仪器加了一个适配器增加了某些功能一样 队列 queue 缺省用deque为基础 栈 stack 可用vector或deque为基础 11 5容器适配器 例11 5 优先级队列类演示 头文件用 优先级用数表示 数值越大优先级越高 include include includeusingnamespacestd voidmain priority queueprioque 实例化存放int值的优先级队列 并用deque作为基础数据结构prioque push 7 压入优先级队列prioque push 12 prioque push 9 prioque push 18 cout 从优先级队列中弹出 endl while prioque empty cout prioque top t 取最高优先级数据prioque pop 弹出最高优先级数据cout endl 输出结果为 从优先级队列中弹出 181297 11 6泛型算法与函数对象 算法表现为一系列的函数模板 它们是STL中最类似于传统函数库的部分 它们不是作为预先编译好的对象模块组成的可链接库来提供 它们完整定义在STL头文件中 使用者可以用很多方式来特化每一个模板函数 大大提高了它作为通用型程序组件的适用性 一般这些函数模板都使用迭代子作为它的参数和返回值 以此在容器 序列 上进行各种操作 如每个容器都可使用find 算法 11 6 1函数对象 11 6 2泛型算法 11 6 1函数对象 在C 中 为了使程序的安全性更好 采用 引用 来代替指针作为函数的参数或返回值 在C 的泛型算法中类似地采用了 函数对象 functionobject 来代替函数指针 函数对象是一个类 它重载了函数调用操作符 operator 该操作符封装了应该被实现为一个函数的操作 典型情况下 函数对象被作为实参传递给泛型算法 和 引用 一样 函数对象 独立使用比较少 函数对象亦称拟函数对象 function likeobject 和函子 functor 每个泛型算法 genericalgorithm 的实现都独立于单独的容器类型 它消除了算法的类型依赖性 例11 6 求和函数对象的定义和测试 函数对象是一个类 它重载了调用操作符 使用方法与类模板相同 includetemplateclassSum Tres public Sum Ti 0 res i 构造函数 即sum Ti 0 res i Toperator Tx res x returnres 累加 重载的调用操作符 Tresult const returnres 11 6 1函数对象 templateTFunc1 FuncObjectfob constT 函数对象标准用法 未实现累加 注意Sum仅能实例化为有限种类型 整型 实型 字符型等等 11 6 1函数对象 函数对象与函数指针相比较有三个优点 第一 函数指针是间接引用 不能作为内联函数 而函数对象可以 这样速度更快 第二 函数对象可以拥有任意数量的额外数据 用这些数据可以用来缓冲当前数据和结果 提高运行质量 当然多数情况下不一定使用 上例中res就是一个额外数据 第三 编译时对函数对象作类型检查 下面给出采用函数对象作为 数值比较算法 的求序列中最小值的函数模板 templateconstType 例中Comp为比较函数对象类 对不同的数据类型 可以定义不同的函数对象 11 6 1函数对象 预定义函数对象分为算术 关系和逻辑操作 每个对象都是一个类模板 其中操作数类型作为模板参数 使用时要包含头文件 include以加法为例 讨论名为plus的类模板 对整数的用法实例如下 plusintAdd intival1 30 ival2 15 intsum intAdd ival1 ival2 等效于 sum ival1 inval2 函数对象有多种来源1 标准库预定义的一组算术 关系和逻辑函数对象 2 预定义的一组函数适配器 允许对预定义的函数对象进行特殊化或扩展 3 自定义函数对象 函数对象主要是作为泛型算法的实参使用 通常用来改变缺省的操作 比如在 例11 3 中有sort vec begin vec end greater 这就是把整数的大于关系函数对象作为实参 得降序排列 如果是字符串 则有 sort svec begin svec end greater 只要改一下参数就又可用于字符串的排序 11 6 1函数对象 greater的比较算法在内置类型int 字符串类string中定义 譬如可以自定义整数类Int 其中重载了 运算符 classInt public Int intival 0 val ival intoperator return val 负数符号重载intoperator intival return val ival 求余符号重载booloperator intival return val ival 小于符号重载booloperator return val 0 逻辑非符号重载private int val 每个类对象都可以作为有名或无名对象传递给函数 同时也把所需重载的算法传递过去了 11 6 1函数对象 下面给出各种预定义的函数对象及其使用方法 参数和返回值 为方便说明 定义以下变量 对象 vectorsvec stringsval1 sval2 sres complexcval1 cval2 cres intival1 ival2 ires IntIval1 Ival2 Ires doubledval1 dval2 dres 同时为了用实例来说明使用方法 再定义一个可用单参数函数对象 一元函数对象 的函数模板和一个可用双参数函数对象 二元函数对象 的函数模板 templateTypeUnaryFunc FuncObjectfob constType 11 6 1函数对象 算术函数对象 加法 plusplusintPlus ires intPlus ival1 ival2 dres BinaryFunc plus dval1 dval2 sres BinaryFunc plus sval1 sval2 减法 minus 同加法乘法 multiplies 不能用串 可用于复数和浮点数等multipliesintMulti ires intMulti ival1 ival2 cres BinaryFunc multiplies cal1 cal2 dres BinaryFunc multiplies dval1 dval2 除法 divides 同乘法求余 modulus 不能用于复数 浮点数 只能用于整数modulusIntModulus Int自定义类型Ires IntModulus Ival1 Ival2 ires BinaryFunc modulus ival1 ival2 取反 negate 同取余 但为单参数ires UnaryFunc negate Ival1 11 6 1函数对象 逻辑函数对象 这里Type必须支持逻辑运算 有两个参数 逻辑与 logical and 对应 逻辑或 logical or 对应 逻辑非 logical not 对应 关系函数对象 它们的返回值为布尔量 两个参数 第一参数和第二参数相比 等于 equal to不等于 not equal to大于 great大于等于 great equal小于 less小于等于 less equal 返回布尔值的函数对象称为谓词 predicate 默认的二进制谓词是小于比较操作符 所以默认的排序方式都是升序排列 它采用小于比较形式 11 6 1函数对象 和容器类一样 函数对象也可以由函数适配器来特殊化或扩展一元 单参数 或二元 双参数 函数对象 1 绑定器 binder 把二元函数对象中的一个参数固定 绑定 使之转为一元函数 C 标准库提供两种预定义的binder适配器 bind1st和bind2nd 分别绑定了第一或第二个参数 2 取反器 negator 把函数对象的值翻转的适配器 如原来为小于 用了它后就变成了大于 C 标准库也提供了两种negator适配器 not1和not2 not1用于一元预定义函数对象 not2用于二元预定义函数对象 11 6 2泛型算法 在C 标准库中给出了70余种算法 泛型算法函数名都加有后缀 这些后缀的意思如下 if表示函数采用的操作是在元素上 而不是对元素的值本身进行操作 如find if算法表示查找一些值满足函数指定条件的元素 而find查找特定的值 copy表示算法不仅操作元素的值 而且还把修改的值复制到一个目标范围中 reverser算法颠倒范围中元素的排列顺序 而reverse copy算法同时把结果复制到目标范围中 其它的后缀从英文意思上立即可以认出其意义 对照附录C 在泛型算法中有一种习惯用语 不说满足某条件的元素 而讲满足指定二进制谓词规则的元素 因为谓词是返回布尔值的函数对象 满足则返回true 即与满足指定条件是同样意思 11 6 2泛型算法 其次我们介绍泛型算法的构造与使用方法 所有泛型算法的前两个实参是一对iterator 通常称为first和last 它们标出要操作的容器或内置数组中的元素范围 元素的范围