C语言程序设计（第4版）清华大学出版社c10

1、第十章第十章 C+标准模板库标准模板库清华大学清华大学 郑郑 莉莉C+语言程序设计C+语言程序设计清华大学 郑莉2主要内容主要内容l泛型程序设计泛型程序设计l迭代器迭代器l顺序容器顺序容器l关联容器关联容器l函数对象函数对象l算法算法l深度探索深度探索C+语言程序设计清华大学 郑莉3泛型程序设计泛型程序设计l编写不依赖于具体数据类型的程序编写不依赖于具体数据类型的程序l将算法从特定的数据结构中抽象出来，成将算法从特定的数据结构中抽象出来，成为通用的为通用的lC+的模板为泛型程序设计奠定了关键的的模板为泛型程序设计奠定了关键的基础基础l几个术语几个术语 概念（concept）：用来界定具备一定功

2、能的数据类型，如“支持运算符”的数据类型构成Comparable这一概念； 模型（model）：符合一个概念的数据类型称为该概念的模型，如int型是Comparable概念的模型。泛型程序设计C+语言程序设计清华大学 郑莉STL程序实例程序实例(例例10-1)4/包含的头文件略去包含的头文件略去using namespace std;using namespace std;intint main() main() const const intint N = 5; N = 5;vectorvector s(N); s(N); for (for (intint i i = 0; = 0; i i

3、 N; s si i;transform(transform(s.begins.begin(), (), s.ends.end(),(), ostream_iteratorostream_iterator (coutcout, ), negate, ), negate();();coutcout endlendl; ;return 0;return 0; 容器函数对象算法迭代器泛型程序设计C+语言程序设计清华大学 郑莉STL的组成部分的组成部分lSTL是泛型程序设计的一个范例是泛型程序设计的一个范例 容器（container） 迭代器（iterator） 算法（algorithms） 函数对象

4、（function object）5泛型程序设计容器容器(container)算法算法(algorithm)容器容器(container)迭代器迭代器(iterator)函数对象函数对象(functionobject)迭代器迭代器(iterator)C+语言程序设计清华大学 郑莉输入流迭代器和输出流迭代器输入流迭代器和输出流迭代器l输入流迭代器输入流迭代器 istream_iterator 以输入流（如cin）为参数构造 可用*(p+)获得下一个输入的元素l输出流迭代器输出流迭代器 ostream_iterator 构造时需要提供输出流（如cout） 可用(*p+) = x将x输出到输出流l二

5、者都属于适配器二者都属于适配器 适配器是用来为已有对象提供新的接口的对象 输入流适配器和输出流适配器为流对象提供了迭代器的接口6迭代器C+语言程序设计清华大学 郑莉例例10-27/包含的头文件略去包含的头文件略去using namespace std;using namespace std;double square(double x) double square(double x) return x return x * * x; x; intint main() main() transform(transform(istream_iteratoristream_iterator(cinc

6、in) ), , istream_iteratoristream_iterator()(), , ostream_iteratorostream_iterator(coutcout, t), t), square);, square); coutcout 运算符）运算符）l输入迭代器输入迭代器 可以用来从序列中读取数据，如输入流迭代器l输出迭代器输出迭代器 允许向序列中写入数据，如输出流迭代器l前向迭代器前向迭代器 既是输入迭代器又是输出迭代器，并且可以对序列进行单向的遍历l双向迭代器双向迭代器 与前向迭代器相似，但是在两个方向上都可以对数据遍历l随机访问迭代器随机访问迭代器 也是双向迭代器，

7、但能够在序列中的任意两个位置之间进行跳转，如指针、使用vector的begin()、end()函数得到的迭代器迭代器C+语言程序设计清华大学 郑莉迭代器的区间迭代器的区间l两个迭代器表示一个区间：两个迭代器表示一个区间：p1, p2)lSTL算法常以迭代器的区间作为输入算法常以迭代器的区间作为输入，传递输入数据，传递输入数据l合法的区间合法的区间 p1经过n次(n 0)自增(+)操作后满足p1 = p2l区间包含区间包含p1，但不包含，但不包含p210迭代器C+语言程序设计清华大学 郑莉迭代器的辅助函数迭代器的辅助函数ladvance(p, n) 对p执行n次自增操作ldistance(fir

8、st, last) 计算两个迭代器first和last的距离，即对first执行多少次“+”操作后能够使得first = last11迭代器C+语言程序设计清华大学 郑莉12容器容器l容器类是容纳、包含一组元素或元素容器类是容纳、包含一组元素或元素集合的对象。集合的对象。l七种基本容器：七种基本容器： 向量（vector）、双端队列（deque）、列表（list）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）容 器C+语言程序设计清华大学 郑莉容器的概念图容器的概念图13容 器容器(Container)随机访问容器(Random Access Co

9、ntainer)可逆容器(Reversible Container)容器(Container)顺序容器(Sequence)关联容器(Associative Container)vectordequelistmultisetmultimapsetmapC+语言程序设计清华大学 郑莉14容器的通用功能容器的通用功能l容器的通用功能容器的通用功能 用默认构造函数构造空容器 支持关系运算符：=、!=、= begin()、end()：获得容器首、尾迭代器 clear()：将容器清空 empty()：判断容器是否为空 size()：得到容器元素个数 s1.swap(s2)：将s1和s2两容器内容交换l相关

10、数据类型（相关数据类型（S S表示容器类型）表示容器类型） S:iterator：指向容器元素的迭代器类型 S:const_iterator：常迭代器类型容 器C+语言程序设计清华大学 郑莉可逆容器、随机访问容器可逆容器、随机访问容器l可逆容器可逆容器 S:reverse_iterator：逆向迭代器类型 S:const_reverse_iterator：逆向常迭代器类型 rbegin() ：指向容器尾的逆向迭代器 rend()：指向容器首的逆向迭代器l随机访问容器随机访问容器 sn：获得容器s的第n个元素15容 器C+语言程序设计清华大学 郑莉16顺序容器顺序容器l顺序容器的接口顺序容器的接

11、口 赋值lassign 插入函数linsert， push_front（只对list和deque）， push_back 删除函数lerase，clear，pop_front（只对list和deque） ，pop_back 其他顺序容器访问函数lfront，back 改变大小lresize顺序容器C+语言程序设计清华大学 郑莉例例10-417顺序容器/包含的头文件略去包含的头文件略去template template void void printContainerprintContainer(const char(const char* * msgmsg, const T& s) ,

12、 const T& s) coutcout msgmsg : ; : ;copy(copy(s.s.beginbegin()(), , s.s.endend()(), , ostream_iteratorostream_iterator (coutcout, );, );coutcout endlendl; ; intint main() main() dequedeque s; s;for (for (intint i i = 0; = 0; i i 10; x; x;s.s.push_frontpush_front(x);(x); 18printContainerprintCont

13、ainer(dequedeque at first, s); at first, s);/用用s s容器的内容的逆序构造列表容器容器的内容的逆序构造列表容器l llistlist l( l(s.s.rbeginrbegin()(), , s.s.rendrend()(););printContainerprintContainer(list at first, l);(list at first, l);/将列表容器将列表容器l l的每相邻两个容器顺序颠倒的每相邻两个容器顺序颠倒listlist:iteratoriterator iteriter = = l.l.beginbegin()();

14、 ;while (while (iteriter != != l.endl.end() () intint v = v = * *iteriter; ;iteriter = = l.l.eraseerase( (iteriter););l.l.insertinsert(+(+iteriter, v);, v); printContainerprintContainer(list at last, l);(list at last, l);/用列表容器用列表容器l l的内容给的内容给s s赋值，将赋值，将s s输出输出s.s.assignassign( (l.l.beginbegin()(),

15、, l.l.endend()(););printContainerprintContainer(dequedeque at last, s); at last, s);return 0;return 0; C+语言程序设计清华大学 郑莉向量向量(vector)l特点特点 一个可以扩展的动态数组 随机访问、在尾部插入或删除元素快 在中间或头部插入或删除元素慢l向量的容量向量的容量 容量(capacity)：实际分配空间的大小 s.capacity() ：返回当前容量 s.reserve(n)：若容量小于n，则对s进行扩展，使其容量至少为n19顺序容器C+语言程序设计清华大学 郑莉双端队列双端队列

16、(deque)l特点特点 在两端插入或删除元素快 在中间插入或删除元素慢 随机访问较快，但比向量容器慢20顺序容器C+语言程序设计清华大学 郑莉列表列表(list)l特点特点 在任意位置插入和删除元素都很快 不支持随机访问l接合接合(splice)操作操作 s1.splice(p, s2, q1, q2)：将s2中q1, q2)移动到s1中p所指向元素之前21顺序容器C+语言程序设计清华大学 郑莉顺序容器的插入迭代器顺序容器的插入迭代器l插入迭代器插入迭代器 用于向容器头部、尾部或中间指定位置插入元素的迭代器 包括前插迭代器（front_inserter）、后插迭代器（back_insrter

17、）和任意位置插入迭代器（inserter）l例：例：listlist s; s;back_inserterback_inserter iteriter(s);(s);* *( (iteriter+) = 5; /+) = 5; /通过通过iteriter把把5 5插入插入s s末尾末尾22顺序容器C+语言程序设计清华大学 郑莉顺序容器的适配器顺序容器的适配器l以顺序容器为基础构建一些常用数据以顺序容器为基础构建一些常用数据结构结构 栈(stack)：最先压入的元素最后被弹出 队列(queue)：最先压入的元素最先被弹出 优先级队列(priority_queue)：最“大”的元素最先被弹出23顺

18、序容器C+语言程序设计清华大学 郑莉关联容器的一般特性关联容器的一般特性l关联容器的特点关联容器的特点 每个关联容器都有一个键(key) 可以根据键高效地查找元素l接口接口 插入：insert 删除：erase 查找：find 定界：lower_bound、upper_bound、equal_range 计数：count24关联容器C+语言程序设计清华大学 郑莉关联容器概念图关联容器概念图25关联容器(Associative Container)单重关联容器(Unique Asso-ciative Container)多重关联容器(Multiple Asso-ciative Container

19、)关联容器(Associative Container)简单关联容器(Simple Asso-ciative Container)二元关联容器(Pair Asso-ciative Container)multisetmultimapsetmap关联容器C+语言程序设计清华大学 郑莉单重关联容器与多重关联容器单重关联容器与多重关联容器l单重关联容器单重关联容器(set和和map) 键值是唯一的，一个键值只能对应一个元素l多重关联容器多重关联容器(multiset和和multimap) 键值是不唯一的，一个键值可以对应多个元素26关联容器C+语言程序设计清华大学 郑莉简单关联容器和二元关联容器简单

20、关联容器和二元关联容器l简单关联容器简单关联容器(set和和multiset) 容器只有一个类型参数，如set、multiset，表示键类型 容器的元素就是键本身l二元关联容器二元关联容器(map和和multimap) 容器有两个类型参数，如map、multimap，分别表示键和附加数据的类型 容器的元素类型是pair，即由键类型和元素类型复合而成的二元组27关联容器C+语言程序设计清华大学 郑莉例例10-1028intint main() main() mapstring, map courses;courses;/将课程名称和学分插入将课程名称和学分插入coursescourses映射中映

21、射中courses.courses.insertinsert( (make_pairmake_pair(CSAPP, 3);(CSAPP, 3);courses.insertcourses.insert( (make_pairmake_pair(C+, 2);(C+, 2);courses.insertcourses.insert( (make_pairmake_pair(CSARCH, 4);(CSARCH, 4);courses.insertcourses.insert( (make_pairmake_pair(COMPILER, 4);(COMPILER, 4);courses.inse

22、rtcourses.insert( (make_pairmake_pair(OS, 5);(OS, 5);intint n = 3; n = 3;/剩下的可选次数剩下的可选次数intint sum = 0; sum = 0;/学分总和学分总和关联容器29while (n 0) while (n 0) string name;string name;cincin name; name;/输入课程名称输入课程名称mapstring, map:iteratoriterator iteriter= = courses.courses.findfind(name);(name); /查找课程查找课程if

23、 (if (iteriter = = courses.endcourses.end()() ) /判断是否找到判断是否找到coutcout name is not available name is not available second-second; ; /累加学分累加学分courses.courses.eraseerase( (iteriter);); /将刚选过的课程从映射中删除将刚选过的课程从映射中删除n-;n-; coutcout Total credit: sum Total credit: sum endlendl; ;/输出总学分输出总学分return 0;return 0

24、; C+语言程序设计清华大学 郑莉函数对象函数对象l函数对象函数对象 一个行为类似函数的对象 可以没有参数，也可以带有若干参数 其功能是获取一个值，或者改变操作的状态。l例例 普通函数就是函数对象 重载了“()”运算符的类的实例是函数对象30函数对象C+语言程序设计清华大学 郑莉例例10-13、例、例10-14l使用两种方式定义表示乘法的函数对象使用两种方式定义表示乘法的函数对象 通过定义普通函数（例10-13） 通过重载类的“()”运算符（例10-14）l用到以下算法：用到以下算法：templateclass template Type accumulate(Type accumulate(

25、InputIteratorInputIterator first, first, InputIteratorInputIterator last, Type last, Type valval, , BinaryFunctionBinaryFunction binaryOpbinaryOp);); 对first, last)区间内的数据进行累“加”，binaryOp为用二元函数对象表示的“加”运算符，val为累“加”的初值31函数对象32#include #include #include #include /包含数值算法头文件包含数值算法头文件using namespace std;usin

26、g namespace std;/定义一个普通函数定义一个普通函数intint multmult( (intint x, x, intint y) return x y) return x * * y; ; y; ;intint main() main() intint a = 1, 2, 3, 4, 5 ; a = 1, 2, 3, 4, 5 ;const const intint N = N = sizeofsizeof(a) / (a) / sizeofsizeof( (intint););coutcout The result by The result by multiplingmu

27、ltipling all elements in a is all elements in a is accumulate(a, a + N, 1, accumulate(a, a + N, 1, multmult) ) endlendl; ;return 0;return 0; 例10-13：使用普通函数33#include #include #include #include /包含数值算法头文件包含数值算法头文件using namespace std;using namespace std;class class MultClassMultClass public:public:inti

28、nt operator() ( operator() (intint x, x, intint y) const return x y) const return x * * y; y; ;intint main() main() intint a = 1, 2, 3, 4, 5 ; a = 1, 2, 3, 4, 5 ;const const intint N = N = sizeofsizeof(a) / (a) / sizeofsizeof( (intint););coutcout The result by The result by multiplingmultipling all

29、elements in a is all elements in a is accumulate(a, a + N, 1, accumulate(a, a + N, 1, MultClassMultClass()() ) endlendl; ;return 0;return 0; 例10-14：重载“()”运算符C+语言程序设计清华大学 郑莉函数对象概念图函数对象概念图34函数对象(Function)一元函数对象(Unary Function)二元函数对象(Binary Function)产生器(Generator)一元谓词(Unary Predicate)二元谓词(Binary Predic

30、ate)函数对象C+语言程序设计清华大学 郑莉STL提供的函数对象提供的函数对象l用于算术运算的函数对象：用于算术运算的函数对象： 一元函数对象：negate 二元函数对象：plus、minus、multiplies、divides、modulusl用于关系运算、逻辑运算的函数对象用于关系运算、逻辑运算的函数对象 一元谓词：logical_not 二元谓词：equal_to、not_equal_to、greater、less、greater_equal、less_equal、logical_and、logical_or35函数对象C+语言程序设计清华大学 郑莉函数适配器函数适配器l绑定适配器

31、将n元函数对象的指定参数绑定为一个常数，得到n-1元函数对象：bind1st、bind2ndl组合适配器 将指定谓词的结果取反：not1、not2l指针函数适配器 对一般函数指针使用，使之能够作为其它函数适配器的输入：ptr_funl成员函数适配器 对成员函数指针使用，把n元成员函数适配为n + 1元函数对象，该函数对象的第一个参数为调用该成员函数时的目的对象：ptr_fun、ptr_fun_ref36函数对象C+语言程序设计清华大学 郑莉例例10-1737/包含的头文件略去包含的头文件略去intint main() main() intint intArrintArr = 30, 90, 1

32、0, 40, 70, 50, 20, 80 ; = 30, 90, 10, 40, 70, 50, 20, 80 ;const const intint N = N = sizeofsizeof( (intArrintArr) / ) / sizeofsizeof( (intint););vectorvector a( a(intArrintArr, , intArrintArr + N); + N);vectorvector:iteratoriterator p = p = find_iffind_if( (a.begina.begin(), (), a.enda.end(),(), bin

33、d2nd(greaterbind2nd(greater(), 40)(), 40););if (p = if (p = a.enda.end()()coutcout no element greater than 40 no element greater than 40 endlendl; ;elseelsecoutcout first element greater than 40 is: first element greater than 40 is: * *p p endlendl; ;return 0;return 0; 函数对象C+语言程序设计清华大学 郑莉算法算法lSTL算法本

34、身是一种函数模版算法本身是一种函数模版 通过迭代器获得输入数据 通过函数对象对数据进行处理 通过迭代器将结果输出lSTL算法是通用的，独立于具体的数据类型、容算法是通用的，独立于具体的数据类型、容器类型器类型lSTL算法分类算法分类 不可变序列算法 可变序列算法 排序和搜索算法 数值算法38算 法C+语言程序设计清华大学 郑莉不可变序列算法不可变序列算法l不可变序列算法不可变序列算法 不直接修改所操作的容器内容的算法 用于查找指定元素、比较两个序列是否相等、对元素进行计数等l例：例：templateInputIterator find_if(InputIterator first, Input

35、Iterator last, UnaryPredicate pred);用于查找first, last)区间内pred(x)为真的首个元素39算 法C+语言程序设计清华大学 郑莉可变序列算法可变序列算法l可变序列算法可变序列算法 可以修改它们所操作的容器对象 包括对序列进行复制、删除、替换、倒序、旋转、交换、变换、分割、去重、填充、洗牌的算法及生成一个序列的算法l例：例：templateInputIterator find_if(ForwardIterator first, ForwardIterator last, const T& x);把first, last)区间内的元素全部改

36、写为x40算 法C+语言程序设计清华大学 郑莉排序和搜索算法排序和搜索算法l排序和搜索算法排序和搜索算法 对序列进行排序 对两有序序列进行合并 对有序序列进行搜索 有序序列的集合操作 堆算法l例：例：template void sort(RandomAccessIterator first, RandomAccessIterator last, UnaryPredicate comp);以函数对象comp为“”，对 first, last)区间内的数据进行排序41算 法C+语言程序设计清华大学 郑莉数值算法数值算法l数值算法数值算法 求序列中元素的“和”、部分“和”、相邻元素的“差”或两序列的

37、内积 求“和”的“+”、求“差”的“-”以及求内积的“+”和“”都可由函数对象指定l例：例：templateOutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryFunction op);对first, last)内的元素求部分“和”（所谓部分“和”，是一个长度与输入序列相同的序列，其第n项为输入序列前n个元素的“和”），以函数对象op为“+”运算符，结果通过result输出，返回的迭代器指向输出序列最后一个元素的下一个元素42算 法C+语言程序设计清华大

38、学 郑莉关于交换操作关于交换操作(swap)lswap的一种通用实现的一种通用实现template void swap(T &a, T &b) T tmp = a;a = b;b = tmp;l当当T为为vector等数据类型时，这种实现有什等数据类型时，这种实现有什么问题？么问题？ 以上函数中，需要进行多次深拷贝 执行交换操作，有必要深拷贝吗？43深度探索C+语言程序设计清华大学 郑莉swap高效的执行方式高效的执行方式44342堆空间asizecapacityptr14?314257?68bsizecapacityptr交换前交换后以vector型对象为例深度探索C+语言程

39、序设计清华大学 郑莉对容器实现高效的对容器实现高效的swapl每个容器都有一个成员函数每个容器都有一个成员函数swap，执行高，执行高效的交换操作效的交换操作l对于每个容器，对于每个容器，STL都对都对swap函数模版进行函数模版进行了重载，使之调用容器的成员函数，从而在了重载，使之调用容器的成员函数，从而在对容器使用对容器使用swap函数时，执行的是高效的函数时，执行的是高效的交换操作，如：交换操作，如：template inline void swap(vector& a, vector& b) a.swap(b);45深度探索C+语言程序设计清华大学 郑莉STL组件的类型

40、特征组件的类型特征l思考思考 在一个以迭代器为输入的算法中，如何表示迭代器所指向元素的类型？l类型特征类型特征 通过类型特征可以获得与一个类型相关联的其它数据类型l通过函数对象的类型特征可以得到函数对象的参数和返回值类型l通过迭代器的类型特征可以得到迭代器指向元素的类型46深度探索C+语言程序设计清华大学 郑莉函数对象的类型特征函数对象的类型特征lSTL提供的二元函数对象皆继承自以下结构体：提供的二元函数对象皆继承自以下结构体：templatestruct binary_function typedef Arg1 first_argument_type;typedef Arg2 second_argument_type;typedef Result result_type;l若若TypeType为一个符合二元函数对象的类型参数，则为一个符合二元函数对象的类型参数，则可通过可通过typenametypename Type: Type:first_argument_typefirst_argument_type表示它的第一个参数