第10章 泛型程序设计与C++标准模板库_945906616

C++语言程序设计（第4版）第十章泛型程序设计与C++标准模板库清华大学郑莉C++语言程序设计（第4版），郑莉，清华大学目录10.1泛型程序设计及STL的结构10.2迭代器10.3容器的基本功能与分类10.4顺序容器10.5关联容器10.6函数对象10.7算法小结2C++语言程序设计（第4版），郑莉，清华大学10.1.1泛型程序设计的基本概念•编写不依赖于具体数据类型的程序•将算法从特定的数据结构中抽象出来，成为通用的•C++的模板为泛型程序设计奠定了关键的基础•几个术语▫概念（concept）：用来界定具备一定功能的数据类型，如“支持‘’运算符”的数据类型构成Comparable这一概念；▫模型（model）：符合一个概念的数据类型称为该概念的模型，如int型是Comparable概念的模型。•为概念赋予一个名称，并使用该名称作为模板参数名例如，我们将用这样的方式表示insertionSort这样一个函数模板的原型：templateclassSortablevoidinsertionSort(Sortablea[],intn);▫事实上，很多STL的实现代码就是使用概念来命名模板参数的。310.1泛型程序设计及STL的结构C++语言程序设计（第4版），郑莉，清华大学10.1.2STL简介•标准模板库（StandardTemplateLibrary，简称STL）提供了一些非常常用的数据结构和算法•STL程序实例（例10-1）：410.1泛型程序设计及STL的结构//包含的头文件略去……usingnamespacestd;intmain(){constintN=5;vectorints(N);for(inti=0;iN;i++)cins[i];transform(s.begin(),s.end(),ostream_iteratorint(cout,),negateint());coutendl;return0;}容器迭代器函数对象算法C++语言程序设计（第4版），郑莉，清华大学10.1.2STL简介•transform算法的一种实现：templateclassInputIterator,classOutputIterator,classUnaryFunctionOutputIteratortransform(InputIteratorfirst,InputIteratorlast,OutputIteratorresult,UnaryFunctionop){for(;first!=last;++first,++result)*result=op(*first);returnresult;}5C++语言程序设计（第4版），郑莉，清华大学STL的组成部分6•STL是泛型程序设计的一个范例▫容器（container）▫迭代器（iterator）▫算法（algorithms）▫函数对象（functionobject）容器(container)算法(algorithm)容器(container)迭代器(iterator)函数对象(functionobject)迭代器(iterator)10.1泛型程序设计及STL的结构——10.1.2STL简介C++语言程序设计（第4版），郑莉，清华大学10.2.1输入流迭代器和输出流迭代器•输入流迭代器▫istream_iteratorT▫以输入流（如cin）为参数构造▫可用*(p++)获得下一个输入的元素•输出流迭代器▫ostream_iteratorT▫构造时需要提供输出流（如cout）▫可用(*p++)=x将x输出到输出流•二者都属于适配器▫适配器是用来为已有对象提供新的接口的对象▫输入流适配器和输出流适配器为流对象提供了迭代器的接口710.2迭代器C++语言程序设计（第4版），郑莉，清华大学例10-2从标准输入读入几个实数，分别将它们的平方输出//10_2.cpp#includeiterator#includeiostream#includealgorithmusingnamespacestd;//求平方的函数doublesquare(doublex){returnx*x;}intmain(){//从标准输入读入若干个实数，分别将它们的平方输出transform(istream_iteratordouble(cin),istream_iteratordouble(),ostream_iteratordouble(cout,\t),square);coutendl;return0;}810.2迭代器——10.2.1输入流迭代器和输出流迭代器C++语言程序设计（第4版），郑莉，清华大学10.2.2迭代器的分类910.2迭代器输入迭代器(InputIterator)输出迭代器(OutputIterator)前向迭代器(ForwardIterator)双向迭代器(BidirectionalIterator)随机访问迭代器(RandomAccessIterator)C++语言程序设计（第4版），郑莉，清华大学迭代器支持的操作•迭代器是泛化的指针，提供了类似指针的操作（诸如++、*、-运算符）•输入迭代器▫可以用来从序列中读取数据，如输入流迭代器•输出迭代器▫允许向序列中写入数据，如输出流迭代器•前向迭代器▫既是输入迭代器又是输出迭代器，并且可以对序列进行单向的遍历•双向迭代器▫与前向迭代器相似，但是在两个方向上都可以对数据遍历•随机访问迭代器▫也是双向迭代器，但能够在序列中的任意两个位置之间进行跳转，如指针、使用vector的begin()、end()函数得到的迭代器1010.2迭代器——10.2.2迭代器的分类C++语言程序设计（第4版），郑莉，清华大学10.2.3迭代器的区间•两个迭代器表示一个区间：[p1,p2)•STL算法常以迭代器的区间作为输入，传递输入数据•合法的区间▫p1经过n次(n0)自增(++)操作后满足p1==p2•区间包含p1，但不包含p21110.2迭代器C++语言程序设计（第4版），郑莉，清华大学例10-3综合运用几种迭代器的示例//10_3.cpp#includealgorithm#includeiterator#includevector#includeiostreamusingnamespacestd;//将来自输入迭代器p的n个T类型的数值排序，将结果通过输出迭代器result输出templateclassT,classInputIterator,classOutputIteratorvoidmySort(InputIteratorfirst,InputIteratorlast,OutputIteratorresult){//通过输入迭代器p将输入数据存入向量容器s中vectorTs;for(;first!=last;++first)s.push_back(*first);sort(s.begin(),s.end());//对s进行排序，sort函数的参数必须是随机访问迭代器copy(s.begin(),s.end(),result);//将s序列通过输出迭代器输出}1210.2迭代器——10.2.3迭代器的区间C++语言程序设计（第4版），郑莉，清华大学例10-3（续）intmain(){//将s数组的内容排序后输出doublea[5]={1.2,2.4,0.8,3.3,3.2};mySortdouble(a,a+5,ostream_iteratordouble(cout,));coutendl;//从标准输入读入若干个整数，将排序后的结果输出mySortint(istream_iteratorint(cin),istream_iteratorint(),ostream_iteratorint(cout,));coutendl;return0;}1310.2迭代器——10.2.3迭代器的区间运行结果：0.81.22.43.23.32-458-136-5-5-4-123568C++语言程序设计（第4版），郑莉，清华大学10.2.4迭代器的辅助函数•advance(p,n)▫对p执行n次自增操作•distance(first,last)▫计算两个迭代器first和last的距离，即对first执行多少次“++”操作后能够使得first==last1410.2迭代器C++语言程序设计（第4版），郑莉，清华大学10.3容器的基本功能与分类•容器类是容纳、包含一组元素或元素集合的对象。•七种基本容器：▫向量（vector）▫双端队列（deque）▫列表（list）▫集合（set）▫多重集合（multiset）▫映射（map）▫多重映射（multimap）15C++语言程序设计（第4版），郑莉，清华大学10.3容器的基本功能与分类（续）16容器(Container)随机访问容器(RandomAccessContainer)可逆容器(ReversibleContainer)容器(Container)顺序容器(Sequence)关联容器(AssociativeContainer)vectordequelistmultisetmultimapsetmapC++语言程序设计（第4版），郑莉，清华大学容器的通用功能•容器的通用功能▫用默认构造函数构造空容器▫支持关系运算符：==、!=、、=、、=▫begin()、end()：获得容器首、尾迭代器▫clear()：将容器清空▫empty()：判断容器是否为空▫size()：得到容器元素个数▫s1.swap(s2)：将s1和s2两容器内容交换•相关数据类型（S表示容器类型）▫S::iterator：指向容器元素的迭代器类型▫S::const_iterator：常迭代器类型1710.3容器的基本功能与分类C++语言程序设计（第4版），郑莉，清华大学可逆容器、随机访问容器•可逆容器▫S::reverse_iterator：逆向迭代器类型▫S::const_reverse_iterator：逆向常迭代器类型▫rbegin()：指向容器尾的逆向迭代器▫rend()：指向容器首的逆向迭代器•随机访问容器▫s[n]：获得容器s的第n个元素1810.3容器的基本功能与分类C++语言程序设计（第4版），郑莉，清华大学10.4.1顺序容器的基本功能•顺序容器的接口▫赋值assign▫插入函数insert，push_front（只对list和deque），push_back▫删除函数erase，clear，pop_front（只对list和deque），pop_back▫其他顺序容器访问函数front，back▫改变大小resize1910.4顺序容器C++语言程序设计（第4版），郑莉，清华大学例10-4顺序容器的基本操作//10_4.cpp，包含的头文件略去//输出指定的整型顺序容器的元素templateclassTvoidprintContainer(constchar*msg,constT&s){coutmsg:;copy(s.begin(),s.end(),ostream_iteratorint(cout,));coutendl;}intmain(){//从标准输入读入10个整数，将它们分别从s的头部加入dequeints;for(inti=0;i10;i++){intx;cinx;s.push_front(x);}2010.4顺序容器——10.4.1顺序容器的基本功能C++语言程序设计（第4版），郑莉，清华大学例10-4（续）printContainer(dequeatfirst,s);//用s容器的内容的逆序构造列表容器llistintl(s.rbegin(),s.rend());printContainer(listatfirst,l);//将列表容器l的每相