第11章 模板与标准模板库

第十一章

模板与标准模板库函数模板11.1函数模板模板是C++支持参数化多态的工具，它可以实现类型参数化，即把类型定义为参数，真正实现了代码的可重用性，减轻了编程及维护的工作量和难度。模板使类或函数可在编译时定义所需处理和返回的数据类型，一个模板并非一个实实在在的类或函数，仅仅是一个类或函数的描述。模板一般分为函数模板和类模板。模板的定义函数模板并不是一个可以直接使用的函数，它是可以产生多个函数的模板。使用模板的目的就是要让这些程序的实现与类型无关。函数模板定义函数模板的语法格式如下所示： template<typename形参名,typename形参名...>

返回值类型函数名（参数列表） {

函数体; }函数模板定义11.1函数模板11.1函数模板#include<iostream>usingnamespacestd;//定义函数模板template<typenameT>Tadd(Tt1,Tt2){ returnt1+t2;}intmain(){ cout<<add(1,2)<<endl;//传入int类型参数 cout<<add(1.2,3.4)<<endl;//传入double类型参数 system("pause"); return0;}函数模板的用法案例代码函数模板并不是一个函数，它只相当于一个模子，定义一次即可使用不同类型的参数来调用该函数，这样做可以减小代码的书写，提高代码的复用性。使用函数模板不会减少最终可执行程序的大小，因为在调用函数模板时，编译器会根据调用时的参数类型进行相应的实例化。函数模板实例化所谓实例化，就是用类型参数去替换模板中的模板参数，生成一个具体类型的真正函数。实例化可分为隐式实例化与显式实例化。实例化11.1函数模板隐式实例化是根据函数调用时传入的数据类型确定模板形参T的类型，模板形参的类型是隐式确定的。在例5-1中第一次调用add()函数模板时，传入的是int型数据add(1,2)，此时编译器根据传入的实参推演出模板形参类型是int，就会将函数模板实例化出一个int类型的函数，如下所示： intadd(intt1,intt2){ returnt1+t2; }隐式实例化11.1函数模板编译器生成具体类型函数的这一过程就称为实例化，生成的函数称为模板函数。生成int类型的函数后，再将实参1和2传入进行运算。同理当传入double类型的数据时，编译器先将模板实例化为如下形式的函数： doubleadd(doublet1,doublet2){ returnt1+t2;}每一次调用时都会根据不同的类型实例化出不同类型的函数，所以最终可执行程序的大小并不会减少，它只是提高了程序员对代码的复用。隐式实例化11.1函数模板隐式实例化不能为同一个模板形参指定两种不同的类型。可以用另一种实例化方式来解决这个问题——显式实例化。显式实例化就是显式的指定函数模板中的数据类型。其语法格式如下所示： template函数返回值类型函数名<实例化的类型>(参数列表);注意这是声明语句，要以分号结束，<>中是显式实例的数据类型，即要实例化出一个什么类型的函数，例如，显示实例化为int，则在调用时，不是int类型的数据会转换为int类型进行计算。例如：add()函数模板显式实例化为int类型，代码如下所示：templateintadd<int>(intt1,intt2);显式实例化11.1函数模板usingnamespacestd;template<typenameT>Tadd(Tt1,Tt2){ returnt1+t2;}templateintadd<int>(intt1,intt2);//显式实例化为int类型intmain(){ cout<<add<int>(10,'B')<<endl;//函数模板调用 cout<<add(1.2,3.4)<<endl; system("pause"); return0;}显示实例化案例11.1函数模板函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，不同类型的参数调用就产生一系列重载函数。如例5-1中两次调用add()函数模板，编译时会根据传入参数不同实例化出两个函数，如下所示： intadd(intt1,intt2)//int类型参数实例化出的函数{ returnt1+t2;} doubleadd(doublet1,doublet2)//double类型参数实例化出的函数{ returnt1+t2;}函数模板重载11.1函数模板template<typenameT>//定义求两个任意类型数据的最大值Tmax(constT&t1,constT&t2){ returnt1>t2?t1:t2;}template<typenameT>//定义求三个任意类型数据的最大值Tmax(constT&t1,constT&t2,constT&t3){ returnmax(max(t1,t2),t3);}intmain(){ cout<<max(1,2,3)<<endl;//调用三个参数的函数模板 cout<<max('a','e')<<endl;//调用两个参数的函数模板 system("pause"); return0;}函数模板重载案例11.1函数模板类模板11.2类模板函数可以定义模板，对于类来说，也可以定义一个类模板，类模板是针对成员数据类型不同的类的抽象，它不是代表一个具体的实际的类，而是一个类型的类，一个类模板可以生成多种具体的类，定义类模板的格式如下所示： template<typename形参名,typename形参名…> class类名{}定义一个类模板并实例化11.2类模板类模板中的关键字含义与函数模板相同。类模板的模板形参不能为空，一旦声明了类模板就可以用类模板的形参名声明类中的成员变量和成员函数，即可以在类中使用数据类型的地方都可以使用模板形参名来声明。 template<typenameT> classA{ public: Ta; Tb; Tfunc(Ta,Tb);};注意11.2类模板由于类模板包含类型参数，因此也称为参数化类，如果说类是对象的抽象，对象是类的实例，则类模板是类的抽象，类是类模板的实例。定义了类模板后就要使用类模板创建对象以及实现类中的成员函数，这个过程其实也是类模板实例化的过程，实例化出的具体类称为模板类。如果用类模板创建类的对象，如用上述定义的模板类A创建对象，则在类A后面跟上一个<>，并在里面表明相应的类型，格式如下所示： A<int>a;定义一个类模板并实例化11.2类模板这样类A中凡是用到模板形参的地方都会被int类型所代替。当类模板有两个模板形参时，创建对象时，类型之间要用逗号分隔开，如定义一个有两个模板形参的类B，然后用B创建类对象，示例代码如下所示： template<typenameT1,typenameT2> classB{ public: T1a; T2b; T1func(T1a,T2&b);}; B<int,string>b;//创建模板类B的一个对象定义一个类模板并实例化11.2类模板使用类模板时，必须要为模板形参显式指定实参，不存在实参推演过程，也就是说不存在将整型值10推演为int类型传递给模板形参，必须要在<>中指定int类型，这一点与函数模板不同。注意11.2类模板模板的声明或定义只能在全局、命名空间或类范围内进行，不能在局部范围、函数内进行，比如不能在main()函数中声明或定义一个模板。声明或定义一个模板还有以下几点需要注意：如果在全局域中声明了与模板参数同名的变量，则该变量被隐藏。模板参数名不能被当作类模板定义中类成员的名字。同一个模板参数名在模板参数表中只能出现一次。在不同的类模板声明或定义中，模板参数名可以被重复使用。模板声明或定义的作用域11.2类模板类模板的成员函数都是在类的内部实现的，类模板的成员函数可以在类模板的定义中定义(inline函数)，也可以在类模板定义之外定义(此时成员函数定义前面必须加上template及模板参数)，在类模板外部定义成员函数的方法如下所示： template<模板形参表>

函数返回类型类名<模板形参名>::函数名（参数列表）｛｝在类模板外部定义成员函数11.2类模板

template是类模板的声明，在实现成员函数时，也要加上类作用域，而且在类名后要用<>指明类的模板形参。例如有下列类模板的定义：

template<typenameT1,typenameT2> classB{ public: T1a; T2b; T1func(T1a,T2&b);};在类模板外部定义成员函数11.2类模板上述代码中，如果在类模板外定义类B的成员函数func()，其实现如下所示：

template<typenameT1,typenameT2> T1B<T1,T2>::func(T1a,T2&b){}在类模板外部定义成员函数11.2类模板template<typenameT>classCompare{private:

Tt1,t2;public:

Compare(Ta,Tb):t1(a),t2(b){}

Tmax(){returnt1>t2?t1:t2;}

Tmin(){returnt1<t2?t1:t2;}};intmain(){

Compare<int>c1(1,2);//定义int类型的类对象 cout<<"intmax:"<<c1.max()<<endl;

Compare<double>c2(1.2,3.4);//定义double类型的对象 cout<<"doublemin:"<<c2.min()<<endl; return0;}类模板案例实战STL与容器11.3.1STL简介STLStandardTemplateLibrary，即标准模板库，包含了诸多在计算机科学领域里所常用的基本数据结构和算法。为C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性，极大地提高了软件编程的效率。

STL的一个重要特点是数据结构和算法的分离。例如，由于STL的sort()函数是完全通用的，可以用它来操作几乎任何数据集合，包括链表，容器和数组。

从逻辑层次来看，在STL中体现了泛型化程序设计的思想。提倡使用现有模板开发应用程序，将算法和数据结构分离，大部分算法独立于与之对应的数据结构，是一种软件的复用技术。从实现层次看，整个STL是以一种类型参数化的方式实现的，是一个基于模板的标准类库。概念：

特点：11.3.1STL简介8.1STL简介STL容器（container）算法（algorithm）迭代器（iterator）通用的数据结构，承载不同类型的数据对象。独立与数据对象的常用数据处理方法，以函数模板实现的。指向容器中数据对象的指针，通过迭代器访问数据元素，是容器和算法连接的纽带。

序列式容器11.3.2序列式容器序列容器也叫顺序容器，用于存储线性表类型的数据结构，有连续存储和链式存储两种存储方式。11.3.2序列式容器向量,连续存储，动态数组同义词，动态扩展与收缩，可以随机存取元素（用[]运算符存取），尾部添加或移除元素非常快速。但是在中部或头部安插元素比较费时。头文件<vector>

序列式容器主要有三种：vector、deque、listvector双向链表，链式存储，不提供随机存取，插入删除迅速。头文件<list>双端队列,可以随机存取元素，数组头部和尾部添加或移除元素都非常快速。但是在中部或头部安插元素比较费时。头文件<deque>

Deque:

List11.3.2序列式容器函数含义front();back()返回容器头部元素的引用;返回容器尾部元素的引用push_back()将元素val插入到尾部，无返回值pop_back()删除尾部的元素，无返回值begin(),end()然后容器前端和尾部的迭代器（指针）insert()向容器中插入元素erase()删除容器中间元素vecktor存储结构示意图intmain(){ vector<char>v; //创建空的vector容器v v.insert(v.begin(),'a'); //在头部位置插入元素a v.insert(v.begin(),'b'); //在头部位置插入元素b v.insert(v.begin(),'c'); //在头部位置插入元素c v.insert(v.begin()+1,5,'t'); //在v.begin()+1位置插入5个元素t for(inti=0;i<8;i++) //输出容器v中的元素 cout<<v[i]<<"";

v.erase(v.begin()+1,v.begin()+6); //删除5个元素 for(inti=0;i<3;i++) //输出容器v中的元素 cout<<v[i]<<""; return0;

}程序运行结果为：ctttttbacba11.3.2序列式容器元素位置取决于特定的排序准则，和插入顺序无关，set、multiset、map、multimap等。Set/Multiset

:集合。内部的元素依据其值自动排序，Set存储无重复的数据元素，Multisets允许存储重复的元素，内部由二叉树实现，便于查找。Map/Multimap

:映射。Map的元素是成对的键值/实值，内部的元素依据其值自动排序，Map内的元素不允许重复，Multimaps内元素允许重复，内部由二叉树实现，便于查找；容器类自动申请和释放内存，无需new和delete操作。11.3.3关联性容器11.3.4适配器容器容器适配器是一个封装了序列容器的类模板，它在一般序列容器的基础上提供了一些不同的功能。之所以称作适配器类，是因为它可以通过适配容器现有的接口来提供不同的功能。本章将介绍3种容器适配器，分别是stack、queue、priority_queue：stack<T>：是一个封装了deque<T>容器的适配器类模板，默认实现的是一个后入先出（Last-In-First-Out，LIFO）的压入栈。stack<T>模板定义在头文件stack中。queue<T>：是一个封装了deque<T>容器的适配器类模板，默认实现的是一个先入先出（First-In-First-Out，LIFO）的队列。可以为它指定一个符合确定条件的基础容器。queue<T>模板定义在头文件queue中。priority_queue<T>：是一个封装了vector<T>容器的适配器类模板，默认实现的是一个会对元素排序，从而保证最大元素总在队列最前面的队列。priority_queue<T>模板定义在头文件queue中。11.3.4适配性容器

stack存储的元素具有后进先出的特点，存储结构如下图。

函数含义top()返回栈顶元素的引用，即最后一个进入stack容器适配器的元素push(val)将元素val插入到栈顶，无返回值pop()删除栈顶的元素，无返回值swap(s1,s2)交换两个stack容器中的元素，是非成员函数重载(C++11)11.3.4适配性容器queue容器适配器是一个先进先出(FIFO)的存储结构，具有队列的特点。容器中的元素只能从一端使用push()函数进行插入，从另一端使用pop()函数进行删除,queue容器适配器不允许一次插入或删除多个元素，且不支持迭代器方法如begin()、rbegin()等。11.3.5经典案例11.3.5经典案例11.3.5经典案例11.3.5经典案例

泛型算法传统的程序设计中，算法与数据类型，数据结构紧密耦合，缺乏通用性。STL倡导泛型编程，实现容器（数结结构）与算法分离，即同一算法适用不同的容器和数据类型，成为通用算法，即泛型算法。可以最大限度地节省源代码资源。因此比传统的函数库或类库具有通用性。11.4.1算法概述STL中提供的所有算法都包含在三个头文件中：<algorithm>、<numeric>、<functional>。●

algorithm是最大的一个头文件，它由一大堆函数模板组成，其中涉及到的功能有比较、交换、查找、遍历、复制、修改、删除、合并、排序等。●

头文件numeric很小，只包括几个在序列中进行简单数学运算的函数模板，以及加法和乘法在序列中的一些操作。●

头文件functional中则定义了一些类模板，用于声明一些函数对象。11.4.2常用算法1.for_each()算法函数原型定义如下所示：template<typenameInputIterator,typenameFunction>for_each(InputIteratorbegin,InputIteratorend,Functionfunc);for_each()算法对[begin,end)区间中的每个元素都调用func函数（对象）进行操作，它不会对区间中的元素做任何修改，也不会改变原来序列的元素次序。11.4.2常用算法2.find()算法find()函数原型如下所示：template<typenameInputIterator,typenameT>InputIteratorfind(InputeIterator

first,

InputIteratorlast,constT&value);find()算法用于在[begin,last)区间查找value元素是否存在，如果存在，就返回指向这个元素的迭代器，如果不存在，就返回end。11.4.2常用算法3.copy()算法函数原型如下所示：template<typenameInputIterator,typenameOutputIterator>OutputIteratorcopy(InputIteratorfirst,InputIteratorlast,OutputIteratorDestBeg);copy()函数实现将[first,last)区间的元素复制到另一个地方，这个地方的起始位置为DestBeg。11.4.2常用算法4.sort()算法sort()属于可变序列算法，它支持对容器中的所有元素进行排序。函数的原型有如下两种形式：template<typenameRanIt>

//第一种形式，默认为升序voidsort(RanItfirst,RanItlast);template<typenameRanIt,typenamePred>

//第二种形式,指定排序规则voidsort(RanItfirst,RanItlast,Predop);注意：sort()算法只支持随机迭代器，只能适用于vector与deque容器；

list容器不支持随机迭代器，只能使用sort()成员函数，用于自身的元素排序。11.4.2常用算法5.accumulate()算法accumulate()算法属于数值算法，它的原型如下所示：template<typenameInputIterator,typenameT>

//第一种形式Taccumulate(InputIteratorfirst,InputIteratorlast,Tt);template<typenameInputIterator,typenameT,typenamePred>

//第二种形式Taccumulate(InputIteratorfirst,InputIteratorlast,Tt,Predop);accumulate()函数的功能是将[first,last)区间内的数值累加，累加的初始值为t，它的返回值是元素累加结果。第二种形式可以按照指定的规则将元素相加。11.4.3程序举例classMulti{ //类模板private:

Tvalue;public: Multi(constT&v):value(v){} //构造函数 voidoperator()(T&elem)const{elem*=value;}//重载()运算符};voidprint(intelem){ //打印元素 cout<<elem<<"";}11.4.3程序举例intmain(){

intarr[]={21,4,55,22,46,79,9,5,78,34,100};

vector<int>v;

v.assign(arr,arr+sizeof(arr)/sizeof(int)); //用数组给v容器赋值

//调用for_each()函数将容器中每个元素都乘以2

for_each(v.begin(),v.end(),Multi<int>(2));//调用copy()构造函数将容器中元素输出

copy(v.begin(),v.end(),ostream_iterator<int>(cout,""));

cout<<endl;

//调用find()算法查找容器中是否存在值为200的元素

vector<int>::iteratorit=find(v.begin(),v.end(),200);11.4.3程序举例if(*it==200)

cout<<"容器中有值为200的元素"<<endl;else

cout<<"容器中不存在值为200的元素"<<endl;

sort(v.begin(),v.end());//调用sort()算法将容器中元素从小到大排列

cout<<"排序之后："<<endl;

copy(v.begin(),v.end(),ostream_iterator<int>(cout,""));

cout<<endl;

intsum=accumulate(v.begin(),v.end(),0);//累加容器中元素

cout<<"sum="<<sum<<endl;

return0;}

案例实战与实训11.5案例实战与实训数组函数模板。分别编写一个数组元素输入函数模板、数组元素求和函数模板和数组元素输出的函数模板，函数参数为数组名，长度。编写主程序，检验各种类型的输入、求和和输出。案例