c++电子课件(下)第十一章

第十一章 标准模板库（选读）,库（library）是一系列程序组件的集合，它们可以在不同的程序中重复使用。 库函数设计的第一位的要求就是通用性，模板（template）为通用性带来了不可估量的前景。 标准模板库（Standard Template Library）是ANSI/ISO C+最有特色、最实用的部分之一。STL包含:容器类（container）迭代子（iterator）算法（algorithm） 泛型算法（generic algorithm）和函数对象（function object）的概念与使用使算法摆脱了对不同类型数据个性操作的依赖。,标准模板库的引入：,11.1 标准模板库简介,11.3 顺序容器,11.2 迭代子类,11.6 容器适配器,11.4 泛型算法与函数对象,11.5 关联容器,第十一章 标准模板库（选读）,11.1 标准模板库简介,容器类（Container）容器类是管理序列的类，是容纳一组对象或对象集的类。通过由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，这些成员函数通过返回迭代子来指定元素在序列中的位置。,容器分为三大类：顺序容器（Sequence Container or Sequential Container）关联容器（Associative Container）容器适配器（Container Adopter）参见表11.1。,11.1 标准模板库简介,顺序容器和关联容器称为第一类容器（first-class container）。,STL也使容器提供类似的接口。许多基本操作是所有容器都适用的，可以用有类似操作的新类来扩展STL。这些函数和运算符可通称为容器的接口。,表11.2 所有标准库容器共有的函数,11.1 标准模板库简介,(2) 泛型算法（Generic Algorithm）：在模板中算法不依赖于具体的数据类型，而泛型算法更进一步不依赖于具体的容器。泛型算法中采用函数对象（Function Object）引入不同情况下同一算法的差异。它没有使用继承和多态，避免了虚函数的开销，使STL效率更高。,迭代子把算法与容器连接起来。注意算法只是间接通过迭代子操作容器元素，算法本身与容器无关。算法通常返回迭代子。,(3) 迭代子（Iterator）：迭代子是指针概念的泛型化，它指向容器中的元素，它能象指针一样增减，轮流指示容器中每个元素。所以说迭代子是面向对象版本的指针。迭代子可以包括指针，但迭代子又不仅仅是一个指针。,11.2 迭代子类,迭代子属性：C+标准库中对普通类型迭代子按照基本访问功能分类，有五种四级（输入/输出为同一级）预定义迭代子，其功能最强最灵活的是随机访问迭代子。,表11.3 迭代子属性,表11.4 各种迭代子可执行的操作,【例11.1】寻找数组元素。由本例演示可见，泛型算法不直接访问容器的元素，所以与容器无关。元素的全部访问和遍历都通过迭代子实现，并不需要预知容器类型。,11.3 顺序容器,顺序容器：vector，list和deque。vector类和deque类是以数组为基础的，list类是以双向链表为基础的。,11.3.1 矢量类,11.3.2 列表类,11.3.3 双端队列类,11.3. 1 矢量类,矢量类的概念： 矢量（vector）类提供了具有连续内存地址的数据结构。它可通过下标运算符 直接有效地访问矢量的任何元素。 与数组不同，vector的内存用尽时，vector自动分配更大的连续内存区，将原先的元素复制到新的内存区，并释放旧的内存区。这是矢量类的优点。 内存分配由分配子（Allocator）完成。分配子也是类，它运用了new和delete运算符，本教材不作进一步讨论。矢量类的迭代子：每个容器都有自己所支持的迭代子类型，迭代子决定了可采用哪种算法。vector支持随机访问迭代子，具有最强的功能。vector的迭代子通常实现为vector元素的指针。所谓选择容器类，实际上很大部分是选择所支持的迭代子。,11.3. 1 矢量类,矢量容器的声明：#includevector vi; /定义存放整形序列的向量容器对象vi，长度为0的空vectorvector vf;/存放实型序列的向量容器vector vch;/存放字符序列的向量容器vectorvstr; /存放字符串序列的向量容器,11.3.1 矢量类,矢量容器的构造函数：vector(size_t n); /构造一个有n个元素的矢量，/每个元素都是由默认的构造函数所建立的vector(size_t n,T/元素的初值由区间first,last)指定的序列中的元素复制而来 vector(vector& X) /复制构造函数这些构造函数还可以显式给出分配子(allocator)对象。,【例11.2】寻找vector容器元素。,对矢量的操作包含了第六章在顺序表中所列出的操作，甚至更丰富。每种操作都是成员函数。对用户自定义的元素类，要重载“= =”和“”运算符：class Intpublic: Int(int ival=0):_val(ival) int operator-()return -_val; /负数符号重载 int operator%(int ival)return _val%ival; /求余符号重载 bool operator(int ival)return _valival; /大于符号重载 bool operator!()return _val=0; /逻辑非符号重载private: int _val;Int类可以作为类型参数传递给函数对象greater()，同时把重载的运算符也传递过去了。,11.4.1 函数对象,以函数对象作为求序列中最小值的函数模板的“数值比较算法”参数：templateconst Type 例中Comp为比较函数对象（类模板），对不同的数据类型，可以产生不同的比较函数，以实现泛型算法。,使用函数对象实现泛型算法：,11.4.1 函数对象,函数对象与函数指针相比较有三个优点：第一，函数指针是间接引用，不能作为内联函数，而函数对象可以，这样速度更快；第二，函数对象可以拥有任意数量的额外数据，用这些数据可以用来缓冲当前数据和结果，提高运行质量，当然多数情况下不一定使用，上例中res就是一个额外数据；第三，编译时对函数对象作类型检查。,函数对象来源：1. 标准库预定义的一组算术，关系和逻辑函数对象；2. 预定义的一组函数适配器，允许对预定义的函数对象进行特殊化或扩展；3. 自定义函数对象。,函数对象的优点：,11.4.1 函数对象,预定义函数对象及其使用方法：使用时要包含头文件：#include 算术函数对象：加法：plus(x,y) /返回x+y,可用于string、复数和浮点数等减法：minus(x,y) /返回x-y,不能用串,可用于复数和浮点数等乘法：multiplies(x,y) /返回x*y,不能用串,可用于复数和浮点数等除法：divides(x,y) /返回x/y,不能用串,可用于复数和浮点数等求余：modulus(x,y) /返回x%y,只能用于整数取反：negate(x) /返回-x,补码,只能用于整数,11.4.1 函数对象,逻辑函数对象：这里Type必须支持逻辑运算，有两个参数。逻辑与：logical_and(x,y) /对应“&”逻辑或：logical_or(x,y) /对应“|”逻辑非：logical_not(x) /对应“!”,关系函数对象：它们的返回值为布尔量，两个参数，第一参数和第二参数相比：等于：equal_to(x,y) /对应x=y不等于：not_equal_to(x,y) /对应x!=y大于：great(x,y) /对应xy大于等于：great_equal(x,y) /对应x=y小于：less(x,y) /对应x(x,y) /对应x=y,11.4.1 函数对象,返回布尔值的函数对象称为谓词（predicate），默认的二进制谓词是小于比较操作符“class set; /模板参数表中的非类型参数同样可有默认值,11.5.1 集合和多重集合类,set容器的构造函数：set (); /构造一个空的按默认次序排列的集合set (pr); /构造一个空的按函数对象pr排序的集合set (first,last); /构造一个默认次序排列的集合， /元素值由区间first,last)指定的序列复制set (first,last,pr); /同上，但按函数对象pr排序这些构造函数还可以显式给出分配子(Allocator)对象。,集合和多重集合类支持双向迭代子。 multiset和set通常实现为红黑二叉排序树。红黑二叉排序树是实现平衡二叉排序树的方法之一。,【例11.7】整型多重集合关联容器类,11.5.2 映射和多重映射类,映射和多重映射类引入： 它们提供了操作与关键字相关联的映射值（mapped value）的方法。映射和多重映射的主要差别在于多重映射允许存放与映射值相关联的重复关键字，而映射只允许存放与映射值一一对应的单一关键字。 多重映射和映射关联容器类用于快速存储和读取关键字与相关值（关键字/数值对，key/value pair）。如果保存学生的简明资料，要求按学号排序，使用映射关联容器（因为不会重号）是最合适的。如用姓名排序，因姓名可能重复，使用多重映射更为合适。使用时要用头文件。,11.5.2 映射和多重映射类,map类模板声明：template, typename A = allocator class map; map容器有多种构造函数：map (); /构造一个空的按默认次序排列的映射map (pr); /构造一个空的按函数对象pr排序的映射map (first,last); /构造按默认次序排列的映射， /元素值由区间first,last)指定的有序序列复制map (first,last,pr); /同上，但按函数对象pr排序这些构造函数还可以显式给出分配子(allocator)对象。,11.5.2 映射和多重映射类,映射的使用：映射和多重映射类支持双向迭代子。映射定义了成员操作符：T& operatorconst Key& key这样映射的使用是非常方便的，就如同一个数组，关键字作为下标，相关值作为元素值。,【例11.8】我国部分省份与面积映射关联容器类的演示。,11.6 容器适配器,容器适配器（container adapter）：栈，队列和优先级队。所谓适配器并不独立，它依附在一个顺序容器上。如要声明一个用矢量实现的字符型堆栈，声明如下： stack sk;,然后它可以象顺序容器一样使用。但它没有自己的构造和析构函数，它使用其实现类（如vector）的构造和析构函数。队列（queue）默认用deque为基础，栈（stack）可用vector或deque为基础。,11.5.1 栈类,11.5.2 队列类,11.5.3 优先级队列类,11.5.1 栈类,栈并不独立，它依附在一个顺序容器上。栈（stack）可用vector或deque为基础。声明一个用矢量实现的字符型堆栈，格式如下： stack sk;,【例11.9】演示堆栈的压入和弹出。,栈类的引入：,11.5.2 队列类,队列（queue）： 默认以deque为基础,【例11.10】演示队列的入队和出队。,11.5.3 优先级队列类,优先级队列（priority_queue）适配器：用以实现优先级队列。元素插入是自动按优先级顺序插入，使最高优先级元素首先从优先级队列中取出。常用矢量为基础容器。默认时priority_queue用vector为基础数据结构。,【例11.11】 优先级队列类演示，头文件用，优先级用数表示，数值越大优先级越高。,第十一章 标准模板库（选读）,课程全部结束,祝同学们有一个好成绩！,表11.1 标准库容器类,表11.2 所有标准库容器共有的函数（1）,表11.2 所有标准库容器共有的函数（2）,表11.2 所有标准库容器共有的函数（3）,表11.3 迭代子属性,输入InputIterator输出OutputIterator正向ForwardIterator双向Bidirectional Iterator随机访问 RandomAccessIterator,从容器中读取元素。输入迭代子只能一次一个元素地正向移动（即从容器开头到容器末尾，后移）。要重读必须从头开始。向容器写入元素。输出迭代子只能一次一个元素地正向移动。输出迭代子要重写，必须从头开始。组合输入迭代子和输出迭代子的功能，并保留在容器中的位置（作为状态信息），所以重新读写不必从头开始。组合正向迭代子功能与逆向移动功能（即从容器序列末尾到容器序列开头）。组合双向迭代子的功能，并能直接访问容器中的任意元素，即可向前或向后跳过任意个元素。,表11. 4 各种迭代子可执行的操作（1）,表11. 4 各种迭代子可执行的操作（2）,【例11.1】寻找数组元素,int main() int search_value,ia9=47,29,37,23,11,7,5,31,41; coutsearch_value; int* presult=find(,【例11.2】寻找vector容器元素,int main() int i,search_value,ia9=47,29,37,23,11,7,5,31,41; vector vec(ia,ia+9); /数据填入vector vector:iterator iter; /iter是vector用的迭代子，自动建为随机访问迭代子 for(i=0;isearch_value; iter=find(vec.begin(),vec.end(),search_value); /使用vector成员函数赋迭代子初值 cout数值search_value ( iter=vec.end() ?不存在:存在)endl; return 0;,【例11.3】标准输入,#include#include#include#include#includeusing namespace std;int main() istream_iterator input(cin); istream_iterator end_of_stream; vector vec; 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); coutendl; return 0;,【例11.3】标准输入,首先，用一个istream_iterator迭代子input（其实参为cin，即标准输入）读入一个整数集到一个矢量类对象中，出现光标后，可输入：41 3 9 5 7 23 17 19 13 11 37 31 23 29 41 39 Z,例中泛型算法copy()定义如下：templateOutputIterator copy(InputIterator first,InputIterator last,OutputInterator x) for(;first!=last;+x,+first) *x=*first return (x); ,实参end_of_stream是指示文件（流）的结束位置，输入时必须在最后一个数字后加分隔符，然后加Ctrl-Z结束。复制算法要求提供一对iterator来指示文件（流）内部的开始和结束位置。第三个参数是标准函数inserter()返回的插入迭代子，它把流插入vec。,【例11.3】标准输入,泛型算法sort()为升序排序算法，声明如下templatevoid sort(RandomAccessIterator first, RandomAccessInterator last, Pr p);/第三参数为排序方式，greater()是预定义的“大于”函数对象，排序时用它来比较数值大小。默认时为“小于”，即升序排序。,例中用输出迭代子output来输出。其第二个参数 表示用空格分隔各数字。泛型算法unique_copy（），复制一个序列，并删除序列中所有重复元素。本例中，复制到output迭代子，并用空格分隔各整数的标准输出。输出为：41 39 37 31 29 23 19 17 13 11 9 7 5 3,【例11.4】列表类的链表操作,int main() int i; list list1,list2; list:iterator iter; /iter是list用的迭代子，自动建为双向访问迭代子 int arr1=5,7,17,19,23,43; int arr2=3,9,13,29,41; for(i=0;i6;i+) list1.push_back(arr1i); for(i=0;i5;i+) list2.push_front(arr2i); for(iter=list1.begin();iter!=list1.end();iter+) cout*itert; /输出5,7,17,19,23,43 coutendl; for(iter=list2.begin();iter!=list2.end();iter+) cout*itert; /输出41,29,13,9,3 coutendl; list2.reverse(); /反转为3,9,13,29,41 list1.merge(list2); /list2归并到list1,方式默认为升序 while(!list1.empty() /表空结束 coutlist1.front()t; /读第一项，输出3,5,7,9,13,17,19,23,29,41,43 list1.pop_front(); /从链表首删去一项 coutendl; return 0;,【例11.5】双端队列类成员函数insert() 操作,void print_string(char_deque deq)ostream_iteratoroutput(cout);cout生成的字符串是：;copy(deq.begin(),deq.end(),output);int main()char arr1=功能强,arr2=使用方便。;char_deque chdeq(arr1,arr1+6);print_string(chdeq);coutendl;chdeq.insert(chdeq.begin(),L); /逆序chdeq.insert(chdeq.begin(),T);chdeq.insert(chdeq.begin(),S);print_string(chdeq);coutendl;chdeq.insert(chdeq.end(),arr2,arr2+10);print_string(chdeq);coutendl;return 0;,【例11.6】求和函数对象的定义和测试,templateclass Sum T res;public: Sum(T i=0):res(i) /构造函数,即Sum(T i=0)res=i; T operator()(T x) /累加，重载的调用操作符() res+=x; return res; ;templateT Func1(FuncObject fob,const T ,【例11.6】求和函数对象的定义和测试,int main() Sum sum(10); /调用构造函数建立sum。res值为10 int i=5,j=10; cout(5),i)(),j) class multiset; /模板参数表中的非类型参数同样可有默认值 #include#include /包含集合头文件#include/包含算法头文件using namespace std; /C+标准库名字空间域typedef multisetINTMS; /特例取名INTMS，整型多重集合按升序排列,【例11.7】整型多重集合关联容器类,int main() const int size=16; int asize=17,11,29,89,73,53,61,37,41,29,3,47,31,59,5,2; INTMS intMultiset(a,a+size);/用a来初始化INTMS容器实例 ostream_iterator output(cout, ); /整型输出迭代子output，可通过cout输出用空格分隔的整数 cout这里原来有intMultiset.count(17) 个数值17endl; /查找有几个关键字17 intMultiset.insert(17); /插入一个重复的数17 cout输入后这里有intMultiset.count(17) 个数值17endl; INTMS:const_iterator result; /const_iterator使程序可读INTMS的元素 /但不让程序修改它的元素，result为INTMS的迭代子 result=intMultiset.find(18); /找到则返回所在位置，设找到返回与调end()返回的同样值,【例11.7】整型多重集合关联容器类,if(result=intMultiset.end() cout没找到值18endl; else cout找到值18endl; coutintMultiset容