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

1、泛型程序设计和STL的结构2、迭代器3、容器4、函数对象5、算法6、综合实例3将程序写得尽可能通用将算法从特定的数据结构中抽象出来，成为通用的C++的模板为泛型程序设计奠定了关键的基础STL是泛型程序设计的一个范例容器(container)迭代器(iterator)算法（algorithms）函数对象（functionobject）4STL（StandardTemplateLibrary)是一个用于支持C++泛型编程的模板库，1994年被纳入了C++标准。STL提供了一些常用的数据结构和算法。如vector就是STL提供的一个容器。一些常用的排序、查找等算法在STL中都有现成的模板。STL的更大意义在于为泛型程序设计提供了逻辑基础。STL是一个开放的体系。#includeiostream#includevector#includeiterator#includealgorithm#includefunctionalusingnamespacestd;intmain(){constintN=5;vectorints(N);for(inti=0;iN;i++)cins[i];transform(s.begin(),s.end(),ostream_iteratorint(cout,),negateint());coutendl;return0;}从标准输入读入向量容器的内容输出向量容器中每个元素的相反数STL的4种基本组件1、容器(container)2、迭代器(iterator)3、函数对象(functionobject)4、算法(algorithm)6容器类是容纳、包含一组元素或元素集合的对象。异类容器类与同类容器类顺序容器与关联容器七种基本容器：向量（vector）、双端队列（deque）、列表（list）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）7迭代器是面向对象版本的指针，它们提供了访问容器、序列中每个元素的方法。使用独立于STL容器的迭代器，需要包含头文件iterator。8函数对象是一个行为类似函数的对象，对它可以像调用函数一样调用。任何普通函数和重载了”()”运算符的类的对象都可以作为函数对象来使用，函数对象是泛化的函数。使用STL的函数对象，需要包含头文件functional9C++标准模板库中包括70多个算法其中包括查找算法，排序算法，消除算法，记数算法，比较算法，变换算法，置换算法和容器管理等等。这些算法的一个最重要的特性就是它们的统一性，并且可以广泛用于不同的对象和内置的数据类型。使用STL的算法，需要包含头文件algorithm。10容器（container）算法（algorithm）容器（container）函数对象（functionobject）迭代器迭代器图10-1STL组件之间的关系11迭代器是算法和容器的“中间人”。通过迭代器可以把容器中的数据送到算法中，也可以把算法对这些数据处理的结果送到相应的容器中。简单点，可以把迭代器理解为一种泛化的指针。它比指针的功能更强大。12STL将输入流(如cin)也看做是一个容器。因此，可以定义输入流迭代器以便从输入流这个容器中连续地输入某种类型的数据，送到相应的地方。templateclassTistream_iteratorT#includeiostream#includeiterator#includestringusingnamespacestd;intmain(){istream_iteratorinta(cin);while(*a!=EOF){cout*abendl;a++;}return0;}14输出流迭代器用来向一个输出流中连续输出某种类型的数据，它也是一个类模板。templateclassTostream_iteratorT//10_2.cpp#includeiostream#includevector#includeiterator#includealgorithm#includefunctionalusingnamespacestd;//求平方的函数doublesquare(doublex){returnx*x;}intmain(){//从标准输入读入若干个实数，分别将它们的平方输出transform(istream_iteratordouble(cin),istream_iteratordouble(),ostream_iteratordouble(cout,),square);coutendl;return0;}#includevector#includeiostream#includestringusingnamespacestd;intmain(){vectorstringvec;vectorstring::const_iteratori;vec.push_back(dog);vec.push_back(bird);vec.push_back(girl);vec.push_back(boy);vec.push_back(Hello,there);for(i=vec.begin();i!=vec.end();++i)cout(*i)endl;return0;}17图10-25个迭代器概念之间的关系18Inputiterators：提供对数据的只读访问，前向推进。输入迭代器可以使用==和!=来测试是否相等；使用*来访问数据；使用++操作符前向推进。Outputiterators：提供对数据的只写访问，前向推进。输出迭代器缺省只写，由于该迭代器无法读取对象，因此不会在任何搜索和其他算法中使用它。19Forwarditerators：提供读写访问，前向推进。例如replace函数需要保证前向迭代器。Bidirectionaliterators：提供读写访问，前向或后向推进。例如reverse函数需要保证双向迭代器。Randomaccessiterators：提供读写访问，随机移动（非const的指针也是随机迭代器）。STL中的排序和搜索函数使用随机访问迭代器，随机访问迭代器可以使用关系操作符做比较。20设p1和p2是两个输入迭代器，则[p1,p2)表示它们所构成的区间。这个区间是一个有序序列，包括p1和p2两个迭代器所指向元素之间的所有元素单不包括p2所指向的元素。当p1==p2时，[p1,p2)是一个没有任何元素的空区间。当且仅当对p1执行n次(n=0)“++”运算后，p1==p2的值为“true”，[p1,p2)才是一个合法的区间。//10_3.cpp综合运用迭代器的实例#includeiostream#includevector#includeiterator#includealgorithm#includefunctionalusingnamespacestd;//将来自输入迭代器p的n个T类型的数值排序，将结果通过输出迭代器result输出。templateclassT,classInputIterator,classOutputIteratorvoidmySort(InputIteratorfirst,InputIteratorlast,OutputIteratorresult){vectorTs;for(;first!=last;++first)s.push_back(*first);sort(s.begin(),s.end());//对s进行排序，sort的参数必须是随机访问迭代器copy(s.begin(),s.end(),result);//将s序列通过输出迭代器result输出}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;}24advance(iterator,int)：按照指定的数目增减迭代器，iterator改变。第一个参数是迭代器，第二个参数是增减的数目（前向迭代器该数必须为正，双向或者随机迭代器该数可以为负）。distance(iterator,iterator)：返回到达一个迭代器所需递增操作的数目，即两个迭代器相差的距离。25设S表示一种容器类型（如vectorint），s1和s2是S类型的实例。容器支持的基本功能如下：Ss1;//构建一个没有任何元素的容器s1ops2//op是比较操作s1.begin()//返回指向s1第一个元素的迭代器s1.end()//返回指向s1最后一个元素下一个位置的迭代器s1.clear()//将容器s1的内容清空s1.empty()//返回一个布尔值，表示s1容器是否为空s1.size()//返回s1的元素个数s1.swap(s2)//将s1和s2容器内的元素交换26创建类型为S的容器的迭代器方法：S::iteratorS::const_iterator如：vectorint::iteratoriter;vectorint::const_iteratorciter;27图10-3对容器的两种概念划分28顺序容器组织成对象的有限线性集合，所有对象都是同一类型。STL中三种基本顺序容器是：向量(vector)、线性表(list)、双向队列(deque)。关联容器提供了基于KEY的数据的快速检索能力。元素被排好序，检索数据时可以二分搜索。STL有四种关联容器。当一个KEY对应一个Value时，可以使用集合(set)和映射(map)；若对应同一KEY有多个元素被存储时，可以使用多集合(multiset)和多映射(multimap)。29可逆容器：所提供的迭代器是双向迭代器，可以对容器的元素进行双向访问。逆向迭代器：s1.rbegin()//得到指向容器的最后一个元素的逆向迭代器s1.rend()//得到指向容器的第一个元素的前一个位置的逆向迭代器创建类型为S的容器的逆向迭代器方法：S::reverse_iteratorS::const_reverse_iterator容器中文名头文件所属概念vector顺序容器vector随机访问容器顺序容器deque顺序容器deque随机访问容器顺序容器list顺序容器list可逆容器，顺序容器set关联容器set可逆容器，关联容器multiset关联容器set可逆容器，关联容器map关联容器map可逆容器，关联容器multimap关联容器map可逆容器，关联容器31顺序容器在逻辑上可看做是一个长度课扩展的数字，容器中的元素都线性排列。可以随意决定每个元素在容器中的位置，可以随时向指定位置插入新的元素和删除已有的元素。（1）构造函数Ss(n,t)；//构造一个具有n个t元素的容器实例s。如：vectorintvec(10,5);Ss(n);//构造一个具有n个元素的容器实例s；Ss(q1,q2)；//将[q1,q2)区间内的数据作为s的元素构造s。顺序容器的基本功能：32（2）赋值函数s.assign(n,t);//赋值后的容器s由n个t元素构成s.assign(n);//赋值后的容器s具有n个元素s.assign(q1,q2)；//赋值后的容器s为[q1,q2)区间内的数据（3）元素的插入s.insert(p1,t)//在s容