第7章 模板与标准模板库

第7章模板与标准模板库STL----灵活、可扩展、可重用的软件模块标准C++类库概述10年的争论，有了C++库的ANSI/ISO标准-----StandardTemplateLibrary(STL),是ANSI/ISOC++最有特色、最实用的部分之一。STL包括：输入输出类容器类与ADT（抽象数据类型）算法存储管理错误处理语言环境7.1模板的基本知识使用面向对象方法构建软件系统，我们可以利用OO的特性，很好的解决纵向的问题，因为，OO的核心概念，如继承等，都是纵向结构的。但是，在软件系统中，往往有很多模块，或者很多类共享某个行为，或者说，某个行为存在于软件的各个部分中，这个行为可以看作是“横向”存在于软件之中.例：先进后出行为（栈）代码重用：垂直性：继承、多态水平性：模板（参数化）例：函数参数的类型是参数化的。例：数组类、队列类等，其中的元素的类型是参数化的。模板函数用关键字template描述的形式参数修饰函数templateclassT1,classT2,….T1,T2,…用来说明函数的参数类型。例：求两数中较大的数。templateclassTTmaxV(Ta,Tb){returnab?a:b;}main(){doublea=maxV(0.1,0.2);intd=maxV(1,2);}例：查找templateclassTintSeqSearch(Tlist[],Tkey,intn){for(inti=0;in;i++)if(list[i]==key)returni;return-1;}模板类1.模板类的定义：templateclassT1,classT2,….class类名{……};T1,T2,…用来说明类中数据成员和成员函数的类型。2.模板类方法的外联式的实现：templateclassT1,classT2,….类型类名T1,T2,…::成员函数(…..){…}3.创建模板类对象模板类不是实例类，模板类的模板参数必须有具体的实例类才能创建其对象，否则没有创建其对象的概念。模板类名实际类型obj;模板类名实际类型*pobj=new模板类名实际类型;7.1--7.1.2模板类，模板实例例：P258Arraytempl.dsw7.1.3模板的函数式参数例：P262Arraytempl_ex.dsw7.2.7断言(assert)用于调试，使用方法assert(表达式);当表达式为假，系统停止程序在该处，于是可检查调用栈各函数的执行的状态。当表达式为真，系统继续执行后面的代码。头文件#includecassert在其头文件前声明NDEBUG#defineNDEBUG可关闭，即不执行assert语句，节省CPU。最后交付不再调试程序时才这样做。7.2示例程序模板Stack类定义实现使用使用assert用于调试Stack_Ex7.3标准模板库STL7.3.1容器、算法、迭代器STL容器：对象的集合，通过由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，这些成员函数通过返回迭代子来指定元素在序列中的位置。序列式：vector,stack,queue,deque,list关联式：set,map特点：容器的大小动态变化，容器中的对象类型是参数化的。迭代子（iterator):对容器中对象的遍历机制，表现如同指针，或是一种高级指针,是面向对象版本的指针，它提供了访问容器或序列中每个对象的方法。这样就可以把算法用于容器所管理的序列。intA[100];int*p=A;for(inti=0;i100;i++){*p=i;p++}vectorintA(100);vectorint::iteratorp=A.begin();for(inti=0;i100;i++){*p=i;p++;}算法：对容器进行处理的函数，是模板函数.通用的算法更易于扩充。算法中采用函数对象（functionobject）引入不同情况下同一算法的差异。它没有使用继承和多态，避免了虚函数的开销，使STL效率更高。copy,sort,search,merge容器分为三大类：标准库容器类说明顺序容器vector（向量）deque（双端队列）list（列表）从后面快速插入与删除，直接访问任何元素从前面或后面快速插入与删除，直接访问任何元素从任何地方快速插入与删除，双链表关联容器set（集合）multiset（多重集合）map（映射）multimap（多重映射）快速查找，不允许重复值快速查找，允许重复值一对一映射，基于关键字快速查找，不允许重复值一对多映射，基于关键字快速查找，允许重复值容器适配器stack（栈）queue（队列）priority_queue（优先级队列）后进先出（LIFO）先进先出（FIFO）最高优先级元素总是第一个出列所有容器通用的方法插入：insert(位置，对象)删除：erase(位置)，erase(位置1,位置2)清除所有元素：clear()所有容器通用的特殊方法首元素迭代子：begin()尾迭代子（最后一个元素的后继位置）：end()元素个数：size()判容器是否为空：empty()所有容器通用的特殊操作符：访问元素：*迭代子指向下个元素：迭代子++各种迭代子可执行的操作包含正向迭代子所有功能，再增加先++后执行，前置自减迭代子先执行后++，后置自减迭代子双向迭代子--pp--提供输入和输出迭代子的所有功能正向迭代子间接引用迭代子，作为左值将一个迭代子赋给另一个迭代子输出迭代子*pp=p1间接引用迭代子，作为右值将一个迭代子赋给另一个迭代子比较迭代子的相等性比较迭代子的不等性输入迭代子*pp=p1p==p1p!=p1前置自增迭代子，先++后执行后置自增迭代子，执行后再++所有迭代子++pp++说明迭代操作包含双向迭代子所有功能，再增加迭代子p递增i位（后移i位）（p本身变）迭代子p递减i位（前移i位）（p本身变）在p所在位置后移i位后的迭代子（迭代子p本身不变）在p所在位置前移i位后的迭代子（迭代子p本身不变）返回与p所在位置后移i位的元素引用如迭代子p小于p1，返回true，所谓小，即p在p1之前如迭代子p小于等于p1，返回true，否则返回false如迭代子p大于等于p1，返回true，所谓大即p在p1之后如迭代子p大于迭代子p1，返回true，否则返回false随机访问迭代子p+=ip-=ip+ip-ip[i]pp1p=p1p=p1pp1说明迭代操作头文件使用STL容器或容器适配器，要包含定义该容器模板类头文件。这些头文件的内容都在std名字空间域中，程序中必须加以说明。头文件说明dequelistmapsetqueuestackvector两端队deque的头文件表list的头文件映射map和多重映射multimap的头文件集合set和多重集合multimap的头文件队queue和优先级队列priority_queue的头文件栈stack的头文件向量vector的头文件7.3.4序列式容器1）vector矢量（vector）类提供了具有连续内存地址的数据结构。通过下标运算符[]直接有效地访问矢量的任何元素。与数组不同，矢量的内存用尽时，矢量自动分配更大的连续内存区，将原先的元素复制到新的内存区，并释放旧的内存区。这是矢量类的优点。在这里内存分配是由分配子（allocator）完成。矢量可以用来实现队列、堆栈、列表和其他更复杂的结构。vector支持随机访问迭代子，具有最强的功能。vector的迭代子通常实现为vector元素的指针。优点：不用考虑越界，面向对象，有大量的方法支持各种操作。逻辑结构：构造函数vector()vector(intn)访问方法：[]*Insert[0][3]Size=4使用向量容器的声明如下：#includevector……vectorintvi;//定义存放整形序列的向量容器对象vi，长度为0的空vectorvectorfloatvf(100);//存放实型序列的向量容器vectorcharvch;//存放字符序列的向量容器vectorchar*vstr;//存放字符串序列的向量容器矢量容器有多种构造函数。包括构造一个有n个元素的矢量，每个元素都是由元素缺省的构造函数所构造出来的，还可以为每个元素用同一个对象来赋初值。还包括拷贝构造函数，可以由一个已有的矢量容器对象来初始化新容器各元素的构造函数。7.3.4序列式容器2）deque双端队列（deque）（double-endedqueue）类。双端队列允许在队列的两端进行操作。以顺序表为基础，支持随机访问迭代子。双端队列有高度的灵活性，它放松了访问的限制，对象既可从队首进队，也可以从队尾进队，同样也可从任一端出队。除了可从队首和队尾移走对象外，也支持通过使用下标操作符“[]”进行访问。要增加存储空间时，可以在内存块中对deque两端分别进行分配。并且新分配的存储空间保存为指向这些块的指针数组，这样双端队列可以利用不连续内存空间。因此它的迭代子比vector的迭代子更加智能化。为双端队列分配的存储块，往往要等删除双端队列时才释放，它比重复分配（再分配和释放）更有效，但也更浪费内存。使用双端队列，必须包含头文件deque。逻辑结构：构造函数deque()deque(intn)访问方法：[]push_backpush_frontpop_backpop_back*frontbackpoppush7.3.4序列式容器3）list列表（list）是由双向链表（doublylinkedlist）组成的。我们也已经在有关链表的一节中介绍过了，它有两个指针域，可以向前也可以向后进行访问，但不能随机访问，即支持的迭代子类型为双向迭代子。使用起来很方便，与双链表类模板相似，但通用性更好，使用更方便。列表的定义在头文件list中。逻辑结构：构造函数list()访问方法：insert*headtail7.3.6基本的关联式容器map关联容器（associativecontainer）能通过关键字（searchkey）直接访问(存储和读取元素)。四个关联容器为：集合（set），多重集合（multiset），映射（map）和多重映射（multimap）。映射和多重映射类提供了操作与关键字相关联的映射值（mappedvalue）的方法。映射和多重映射的主要差别在于多重映射允许存放与映射值相关联的重复关键字，而映射只允许存放与映射值一一对应的单一关键字。多重映射和映射关联容器类用于快速存储和读取关键字与相关值（关键字/数值对，key/valuepair）。如果保存学生的简明资料，要求按学号排序，使用映射关联容器（因为不会重号）是最合适的。如用姓名排序，因姓名可能重复，使用多重映射更为合适。使用时要用头文件set。逻辑结构templateclassKey,classTypeclassmap21001lei22003li20012xie19222zaokeyvaluevalue_typepairmap使用头文件#includemapusingnamespacestd;类型迭代子:iterator,const_iteratormap元素类型：value_type，其定义：typedefpairconstKey,Typevalue_type;templateclassType1,classType2structpair{Type1first;Type2second;pair();pair(constType1&Val1,constType2&Val2);};访问方法：[]*查找：iteratorfind(constKey&_Key);构造方法mapkey类型,value类型m;7.3.7容器适配器STL提供了三