C++电子课件下第十一章

1、第十一章 标准模板库（选读）,库（library）是一系列程序组件的集合，它们 可以在不同的程序中重复使用。 库函数设计的第一位的要求就是通用性，模板（template）为通用性带来了不可估量的前景。 标准模板库（Standard Template Library）是ANSI/ISO C+最有特色、最实用的部分之一。STL包含: 容器类（container） 迭代子（iterator） 算法（algorithm） 泛型算法（generic algorithm）和函数对象（function object）的概念与使用使算法摆脱了对不同类型数据个性操作的依赖。,标准模板库的引入：,11.1 标准模

2、板库简介,11.3 顺序容器,11.2 迭代子类,11.6 容器适配器,11.4 泛型算法与函数对象,11.5 关联容器,第十一章 标准模板库（选读）,11.1 标准模板库简介,容器类（Container） 容器类是管理序列的类，是容纳一组对象或对象集的类。通过由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，这些成员函数通过返回迭代子来指定元素在序列中的位置。,容器分为三大类： 顺序容器（Sequence Container or Sequential Container） 关联容器（Associative Container） 容器适配器（Container

3、Adopter） 参见表11.1。,11.1 标准模板库简介,顺序容器和关联容器称为第一类容器（first-class container）。,STL也使容器提供类似的接口。许多基本操作是所有容器都适用的，可以用有类似操作的新类来扩展STL。这些函数和运算符可通称为容器的接口。,表11.2 所有标准库容器共有的函数,11.1 标准模板库简介,(2) 泛型算法（Generic Algorithm）： 在模板中算法不依赖于具体的数据类型，而泛型算法更进一步不依赖于具体的容器。泛型算法中采用函数对象（Function Object）引入不同情况下同一算法的差异。它没有使用继承和多态，避免了虚函数的开

4、销，使STL效率更高。,迭代子把算法与容器连接起来。注意算法只是间接通过迭代子操作容器元素，算法本身与容器无关。算法通常返回迭代子。,(3) 迭代子（Iterator）： 迭代子是指针概念的泛型化，它指向容器中的元素，它能象指针一样增减，轮流指示容器中每个元素。所以说迭代子是面向对象版本的指针。迭代子可以包括指针，但迭代子又不仅仅是一个指针。,11.2 迭代子类,迭代子属性： C+标准库中对普通类型迭代子按照基本访问功能分类，有五种四级（输入/输出为同一级）预定义迭代子，其功能最强最灵活的是随机访问迭代子。,表11.3 迭代子属性,表11.4 各种迭代子可执行的操作,【例11.1】寻找数组元素

5、。 由本例演示可见，泛型算法不直接访问容器的元素，所以与容器无关。元素的全部访问和遍历都通过迭代子实现，并不需要预知容器类型。,11.3 顺序容器,顺序容器： vector，list和deque。vector类和deque类是以数组为基础的，list类是以双向链表为基础的。,11.3.1 矢量类,11.3.2 列表类,11.3.3 双端队列类,11.3. 1 矢量类,矢量类的概念： 矢量（vector）类提供了具有连续内存地址的数据结构。它可通过下标运算符 直接有效地访问矢量的任何元素。 与数组不同，vector的内存用尽时，vector自动分配更大的连续内存区，将原先的元素复制到新的内存区，

6、并释放旧的内存区。这是矢量类的优点。 内存分配由分配子（Allocator）完成。分配子也是类，它运用了new和delete运算符，本教材不作进一步讨论。 矢量类的迭代子： 每个容器都有自己所支持的迭代子类型，迭代子决定了可采用哪种算法。vector支持随机访问迭代子，具有最强的功能。vector的迭代子通常实现为vector元素的指针。所谓选择容器类，实际上很大部分是选择所支持的迭代子。,11.3. 1 矢量类,矢量容器的声明： #include vector vi; /定义存放整形序列的向量容器对象vi，长度为0的空vector vector vf;/存放实型序列的向量容器 vector

7、vch;/存放字符序列的向量容器 vectorvstr; /存放字符串序列的向量容器,11.3.1 矢量类,矢量容器的构造函数： vector(size_t n); /构造一个有n个元素的矢量， /每个元素都是由默认的构造函数所建立的 vector(size_t n,T /元素的初值由区间first,last)指定的序列中的元素复制而来 vector(vector vector:reverse_iterator r_iter; for(r_iter=veco.rbegin(); /将r_iter指向到末元素 r_iter!=veco.rend(); /不等于首元素的前导 r_iter+) /实

8、际上是递减 /循环体 如果需要把升序的序列改为降序的序列时，并不需要真正去逆序一个序列，只要使用反转迭代子就可以了。反转迭代子属性为随机迭代子。,11.3.1 矢量类,插入型迭代子（Insertion Iterator）： 当用普通输出迭代子来产生一个元素序列时，一旦添加一些元素就得完全重写。例如普通输出迭代子可以把一个矢量a的内容复制到另一个矢量b中，复制可以从矢量b任一元素开始，矢量b对应位置上的元素被覆盖，相当于改写。插入迭代子则可以添加元素，复制时它可以把矢量a插入到矢量b任一位置。同一个copy()算法用不同类型迭代子，结果是不同的。,有三种插入迭代子，属性均为输出迭代子： inse

9、rt_iterator 用来将新元素插入到一个由迭代子（第二个参数Iter）指定的元素的前面（所谓插在a10之前，即在a9和a10之间添加）。 back_insert_iterator 用来将新元素添加到类型为Type的容器对象的末端； front_insert_iterator 用来将新元素添加到容器的前端（注意：新添加的元素以逆序方式结束于被控序列前端,即最后添加的元素放在最前面）。,11.3.1 矢量类,插入型迭代子使用方法： 标准库定义了一组（3个）插入型迭代子适配器函数。它们返回对应的插入迭代子： Inserter(Type /在迭代子it指定元素前插入一个值为x的元素，返回指向新元

10、素的迭代子 insert (it,n,x); /在迭代子it指定元素前插入n个值为x的元素 insert (it,first,last); /在迭代子it指定元素前插入由区间first,last)指定的序列,11.4 泛型算法与函数对象,算法表现为一系列的函数模板。它们完整定义在STL头文件中。使用者可以用很多方式来特化每一个模板函数，大大提高了它作为通用型程序组件的适用性。这些函数模板使用迭代子作为它的参数和返回值，以此在容器（序列）上进行各种操作。本节进一步讨论算法的通用性。,11.4.1 函数对象,11.4.2 泛型算法,11.4.1 函数对象,函数对象的基本概念： 每个泛型算法（Gen

11、eric Algorithm）的实现都独立于容器类型，它消除了算法对类型的依赖性。 在STL的泛型算法中采用“函数对象”（Function Object）来解决该问题。函数对象是一个类，通常它仅有一个成员函数，该函数重载了函数调用操作符（operator()）。该操作符封装了应该被实现为一个函数的操作。典型情况下，函数对象被作为实参传递给泛型算法。 和“引用”一样，“函数对象”很少独立使用。函数对象亦称拟函数对象（Function_Like Object）和函子（Functor）。,11.4.1 函数对象,【例11.6】求和函数对象的定义和测试。 注意函数对象Sum能实例化为有限种类型，如：整

12、型、实型、字符型等等，也能用于string类型，因为string重载了operator +。,函数对象的应用： 函数对象主要是作为泛型算法的实参使用，通常用来改变默认的操作，如： sort(vec.begin(),vec.end(),greater(); 这就是把整数的大于关系函数对象作为实参，得降序排列。如果是字符串，则有： sort(svec.begin(),svec.end(),greater(); 只要改一下参数就又可用于字符串的排序。 greater中所包含的比较算法实际上在内置类型int，字符串类string中定义。由此可见函数对象并没有新东西，只是一个固定格式，用起来更方便。,1

13、1.4.1 函数对象,例如，自定义整数类Int，其中重载了比较算法“”运算符： class Int public: 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类可以作为类型参数传递给函数对象g

14、reater()，同时把重载的运算符也传递过去了。,11.4.1 函数对象,以函数对象作为求序列中最小值的函数模板的“数值比较算法”参数： template const Type 例中Comp为比较函数对象（类模板），对不同的数据类型，可以产生不同的比较函数，以实现泛型算法。,使用函数对象实现泛型算法：,11.4.1 函数对象,函数对象与函数指针相比较有三个优点：第一，函数指针是间接引用，不能作为内联函数，而函数对象可以，这样速度更快；第二，函数对象可以拥有任意数量的额外数据，用这些数据可以用来缓冲当前数据和结果，提高运行质量，当然多数情况下不一定使用，上例中res就是一个额外数据；第三，编译

15、时对函数对象作类型检查。,函数对象来源： 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,不

16、能用串,可用于复数和浮点数等 求余：modulus(x,y) /返回x%y,只能用于整数 取反：negate(x) /返回-x,补码,只能用于整数,11.4.1 函数对象,逻辑函数对象： 这里Type必须支持逻辑运算，有两个参数。 逻辑与：logical_and(x,y) /对应“ /模板参数表中的非类型参数同样可有默认值,11.5.1 集合和多重集合类,set容器的构造函数： set (); /构造一个空的按默认次序排列的集合 set (pr); /构造一个空的按函数对象pr排序的集合 set (first,last); /构造一个默认次序排列的集合， /元素值由区间first,last)指

17、定的序列复制 set (first,last,pr); /同上，但按函数对象pr排序 这些构造函数还可以显式给出分配子(Allocator)对象。,集合和多重集合类支持双向迭代子。 multiset和set通常实现为红黑二叉排序树。红黑二叉排序树是实现平衡二叉排序树的方法之一。,【例11.7】整型多重集合关联容器类,11.5.2 映射和多重映射类,映射和多重映射类引入： 它们提供了操作与关键字相关联的映射值（mapped value）的方法。映射和多重映射的主要差别在于多重映射允许存放与映射值相关联的重复关键字，而映射只允许存放与映射值一一对应的单一关键字。 多重映射和映射关联容器类用于快速存

18、储和读取关键字与相关值（关键字/数值对，key/value pair）。如果保存学生的简明资料，要求按学号排序，使用映射关联容器（因为不会重号）是最合适的。如用姓名排序，因姓名可能重复，使用多重映射更为合适。使用时要用头文件。,11.5.2 映射和多重映射类,map类模板声明： template, typename A = allocator class map; map容器有多种构造函数： map (); /构造一个空的按默认次序排列的映射 map (pr); /构造一个空的按函数对象pr排序的映射 map (first,last); /构造按默认次序排列的映射， /元素值由区间first,

19、last)指定的有序序列复制 map (first,last,pr); /同上，但按函数对象pr排序 这些构造函数还可以显式给出分配子(allocator)对象。,11.5.2 映射和多重映射类,映射的使用： 映射和多重映射类支持双向迭代子。 映射定义了成员操作符： T,然后它可以象顺序容器一样使用。但它没有自己的构造和析构函数，它使用其实现类（如vector）的构造和析构函数。队列（queue）默认用deque为基础，栈（stack）可用vector或deque为基础。,11.5.1 栈类,11.5.2 队列类,11.5.3 优先级队列类,11.5.1 栈类,栈并不独立，它依附在一个顺序容器

20、上。栈（stack）可用vector或deque为基础。 声明一个用矢量实现的字符型堆栈，格式如下： stack sk;,【例11.9】演示堆栈的压入和弹出。,栈类的引入：,11.5.2 队列类,队列（queue）： 默认以deque为基础,【例11.10】演示队列的入队和出队。,11.5.3 优先级队列类,优先级队列（priority_queue）适配器： 用以实现优先级队列。元素插入是自动按优先级顺序插入，使最高优先级元素首先从优先级队列中取出。常用矢量为基础容器。默认时priority_queue用vector为基础数据结构。,【例11.11】 优先级队列类演示，头文件用，优先级用数表示

21、，数值越大优先级越高。,第十一章 标准模板库（选读）,课程全部结束,祝同学们有一个好成绩！,表11.1 标准库容器类,表11.2 所有标准库容器共有的函数（1）,表11.2 所有标准库容器共有的函数（2）,表11.2 所有标准库容器共有的函数（3）,表11.3 迭代子属性,输入 InputIterator 输出 OutputIterator 正向 ForwardIterator 双向Bidirectional Iterator 随机访问 Random AccessIterator,从容器中读取元素。输入迭代子只能一次一个元素地正向移动（即从容器开头到容器末尾，后移）。要重读必须从头开始。 向容

22、器写入元素。输出迭代子只能一次一个元素地正向移动。输出迭代子要重写，必须从头开始。 组合输入迭代子和输出迭代子的功能，并保留在容器中的位置（作为状态信息），所以重新读写不必从头开始。 组合正向迭代子功能与逆向移动功能（即从容器序列末尾到容器序列开头）。 组合双向迭代子的功能，并能直接访问容器中的任意元素，即可向前或向后跳过任意个元素。,表11. 4 各种迭代子可执行的操作（1）,表11. 4 各种迭代子可执行的操作（2）,【例11.1】寻找数组元素,int main() int search_value,ia9=47,29,37,23,11,7,5,31,41; coutsearch_valu

23、e; 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 ( i

24、ter=vec.end() ?不存在:存在)endl; return 0;,【例11.3】标准输入,#include #include #include #include #include using 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(); /降序

25、排列 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()定义如下： template OutputIterator copy(InputIterator first,Inpu

26、tIterator last,OutputInterator x) for(;first!=last;+x,+first) *x=*first return (x); ,实参end_of_stream是指示文件（流）的结束位置，输入时必须在最后一个数字后加分隔符，然后加Ctrl-Z结束。复制算法要求提供一对iterator来指示文件（流）内部的开始和结束位置。第三个参数是标准函数inserter()返回的插入迭代子，它把流插入vec。,【例11.3】标准输入,泛型算法sort()为升序排序算法，声明如下 template void sort(RandomAccessIterator first

27、, 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

28、; 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!=list

29、2.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 prin

30、t_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);

31、 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; ; template T Func1(FuncObject fob,const

32、 T ,【例11.6】求和函数对象的定义和测试,int main() Sum sum(10); /调用构造函数建立sum。res值为10 int i=5,j=10; cout(5),i)(),j)endl; / 0+j，输出：10 return 0;,输出：2025 303535 304050 101010 101010,【例11.7】整型多重集合关联容器类,多重集合关联容器类，类模板声明: template, typename A = allocator class multiset; /模板参数表中的非类型参数同样可有默认值 #include #include /包含集合头文件 #incl

33、ude/包含算法头文件 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输出用空

34、格分隔的整数 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容器中有endl; copy(intMultiset.begin(),intMultiset.end(),output); /输出容器中全部元素 coutendl;return 0； 运行结果为： 这里原来有1个数值17 输入后这里有2个数值17 没找到值18 容器中有： 2 3 5 11 17 17 29 29 31 37 41 47 53 59