C++高级编程六v1.1暗影行者

1、1C+C+高级编程高级编程 ( (六六) )联航精英训练营2C+C+模板技术模板技术3问题的引入问题的引入n 一个求最大值的问题？int max(int a, int b) return a b ? a : b;float max(float a, float b) return a b ? a : b;char max(char a, char b) return a b ? a : b; 当我们需要求不同类型数值的最大值时，我们不得不重载代码几乎一样的不同版本的max函数 那么有没有办法让程序能够自动识别我们输入的类型并复用同样的代码呢？4C+C+模板技术模板技术n 函数模板 p函数模板p

2、模板的形参限制p模板的实例化 n 类模板 p类模板的优势p类模板及成员函数的定义p类模板的继承与派生 5函数模板函数模板n 函数模板是一个独立于类型的函数，可产生函数特定类型的版本。通过对参数类型进行参数化，获取有相同形式的函数体。n 它是一个通用函数，它可适应一定范围内的不同类型对象的操作。n 函数模板将代表着不同类型的一组函数，它们都使用相同的代码，这样可以实现代码重用，避免重复劳动，又可增强程序的安全性。 6函数模板函数模板函数模板的定义格式：template 类型 函数名(参数表) /函数体 模板形参表又称参数化类型名表，多个表项用逗号分隔。每个项称为一个模板参数（模板形参）。格式如下

3、：class 或typename或 / int , double ,char7函数模板实例函数模板实例-t1.cpp-t1.cpptemplate / template T Max(const T &a, const T &b) return a b ? a : b;n 括起部分就是模板的形参表，T是一个虚拟类型参数。注意，可以用多个虚拟参数构成模板形参表。n 不但普通函数可以声明为函数模板，类的成员函数也可以声明为函数模板void main() cout “Max(15, 60) = Max(15, 60) endl; cout “Max(a, b) = Max(a, b) endl; co

4、ut “Max(1.2, 16.2) = Max(1.2, 16.2) endl;8模板形参模板形参n 类型形参 类型形参跟在关键字class或typename之后定义，如class T 是名为T的类型形参。template int compare(const T &v1, const T &v2);n 非类型形参 在调用函数时非类型形参将用值代替，值的类型在模板形参表中指定。非类型形参通常为定义模板内部的常量值。template void sum(T data,T &result) result = 0; for(int i=0; irows; i+) result+=datai;9inli

5、neinline函数模板函数模板n inline函数模板中，inline说明符要放在模板参数列表之后，返回值之前，不能放在template关键字之前。template inline T fun(const T& a, const T& b);10模板形参限制（一）模板形参限制（一）n 模板形参作用域 模板形参的名字可以在声明为模板形参之后直到模板声明或定义的末尾处使用。typedef double T;template T fun(const T &a, const T &b) T tmp = a; return tmp;template T cacl(const T &a)11模板形参限制模

6、板形参限制（二）（二）n 使用模板形参名字的限制 模板形参的名字在同一模板形参表中只能使用一次，并且不能在模板内部重定义。注意：不能出现如下定义template T fun(const T &a, const T &b) typedef double T; /Error! T tmp = a; return tmp;template T cacl(const T &a, const T &b)12模板形参限制模板形参限制（三）（三）n 模板声明模板可以像其他函数一样只声明而不定义。在同一模板的声明和定义中，模板形参名称可以不同。template void fun(const T &);temp

7、late void fun(const T &);template void fun(const U &);template void fun(const V &a)13函数模板实例化函数模板实例化n 函数模板是模板函数的一个样板，它可以生成多个重载的模板函数，这些模板函数重用函数体代码。模板函数是函数模板的一个实例。n 编译系统将依据每一次对模板函数调用时实际所使用的数据类型生成适当的调用代码，并生成相应的函数版本。编译系统生成函数模板的某个具体函数版本的过程称为函数模板的实例化（instantiation），每一个实例就是一个函数定义。n 实例化的过程或结果通常是不可见的，编译系统会根据函

8、数调用的具体情况自动传递相应的模板实参，生成相应的函数实例。14模板实参推断模板实参推断n 从函数实参确定模板实参类型和值的过程叫做模板实参推断（template argument deduction）。n 实参推断过程中可能出现的问题p从模板函数实参表获得的信息有矛盾。 p需要获得特定类型的返回值，而不管参数的类型如何。 p函数模板含有常规形参15模板实参推断模板实参推断（一）（一）n 模板函数实参表获得的信息有矛盾n 解决办法p当实参表中有多个类型时，保证实参类型完全匹配。p指定显示模板实参template T add(T a, T b)return a+b;int main()doubl

9、e a = 5.3;add(a, 100); /error: no matching add(double, int)return 0;add(a, 100); / add(int, int)16模板实参推断模板实参推断（二二）n 获得特定类型的返回值引入新的模板形参表示返回值，并由调用者显示指定由于显示模板实参从左至右依次匹配，第一个模板实参与第一个模板形参相匹配，因此好的设计是将返回值类型设置为第一个模板形参template T1 add(T2 a, T3 b) return a + b;double v1 = add(452.8, 100);template T3 add(T2 a, T

10、1 b)long v2 = add(45.2, 100);17模板实参推断模板实参推断（三）（三）n 函数模板含有常规形参p当模板含有常规形参时，如果常规参数的信息无法从模板函数的实参表中获得，则在调用时必须显式的给出对应于常规参数的模板实参int main() int d3=1,2,3; int r; sum(d,r); coutsum=rendl; return 0;template sum(T data,T &result) result=0; for(int i=0;irows;i+) result += datai;18函数模板的重载函数模板的重载-t2.cpp-t2.cppn 函数

11、模板与函数模板、普通函数之间可以重载template T Func(T t) cout “Func(T)”endl; return t;templateT Func(int i,T t) cout “Func(int, T)”endl; return i*t;int Func(int t) cout “Func(int)”endl; return t;int main() cout Func(2.3); cout Func(5); cout Func(2.5, 5.3); cout Func(2, 42.4); return 0;结果是？19练习练习n 编写一个冒泡排序法的函数模板，并针对不少

12、于三种类型进行测试20类模板类模板n 为何要引进类模板？p按不同的方式重用相同的代码p使代码参数化（通用化），即不受类型和操作的影响n 使用类模板所定义的一种类类型，类中的某些数据成员和某些成员函数的参数及返回值可以选取一定范围内的多种类型，从而实现代码重用。n 是一种参数化类型的类，是类的生成器21引入类模板的优势引入类模板的优势template class Stackpublic: Stack(int = 10); Stack() delete stackPtr; bool push(const T&); bool pop(T&); bool isEmpty() return top =

13、-1; bool isFull() return top = size - 1; private: int size; int top; T* stackPtr;可以存放任何对象的栈22类模板的定义类模板的定义n 类模板的定义 template class 类名 /类的实现部分 ;n 模板参数表 class /typename 标识符n 用类模板定义对象的格式是： 类名 对象名(构造函数实参表)； Stack sk;Stack stk(10);23类模板成员类模板成员n 类模板成员函数的定义 template 类型 类名：函数名（参数列表） /实现部分 templateStack:Stack(

14、int size)template int Stack:push(const T &i)template int Stack:pop(T &i)24练习练习n 编写一个栈的类模板n 编写一个环形缓冲区的类模板25类模板的派生与继承类模板的派生与继承n 继承与派生方式p公有继承p私有继承p保护继承n 访问控制与一般的类一致n 常见继承与派生情况p普通类继承类模板 p模板类继承普通类p模板类继承模板类 p模板类继承模板参数给出的基类 26普通类继承类普通类继承类模板模板n 普通类继承类模板通过继承类模板的一个实例来声明一个类 templateclass Apublic: A()private: T

15、 data;class B:public A;27模板类继承普通模板类继承普通类类n 模板类继承普通类class A;templateclass B:public Apublic: B()private: T data;28模板类继承模板模板类继承模板类类n 模板类继承模板类templateclass Base T data1;templateclass Derived:public Base T2 data2;29模板类继承模板参数给出的基类模板类继承模板参数给出的基类 #includeusing namespace std;class BaseApublic: BaseA()coutBas

16、eA founedendl;class BaseBpublic: BaseB()coutBaseB founedendl;templateclass BaseCprivate: T data;public: BaseC(T n=value):data(n) coutBaseC founed dataendl;templateclass Derived:public Tpublic: Derived():T()coutDerived founedendl;int main() Derived x;/ BaseA作为基类 Derived y;/ BaseB作为基类 DerivedBaseC z;

17、/ BaseC作为基类30类的模板成员类的模板成员n 类的模板成员在类内部与一般模板函数实现方法一致n 类的模板成员函数，在类外部实现时必须包含所有模板的形参表templateclass Basepublic: template void fun(const V&);template template void Base:fun(const V &t)31STLSTL标准模板库入门标准模板库入门C+ STANDARD TEMPLATE LIBARARY32STLSTL概述概述n STL是C+标准程序库的核心，深刻影响了标准程序库的整体结构n STL是泛型（generic）程序库，利用先进、高效

18、的算法来管理数据n STL由一些可适应不同需求的集合类（collection class），以及在这些数据集合上操作的算法（algorithm）构成n STL内的所有组件都由模板（template）构成，其元素可以是任意类型33STLSTL组件组件n 容器（Container） 管理某类对象的集合n 迭代器（Iterator） 在对象集合上进行遍历n 算法（Algorithm） 处理集合内的元素 容器 Container 容器 Container容器Container算法Algorithm迭代器迭代器Iterator迭代器迭代器Iterator迭代器迭代器Iterator34STLSTL容器容

19、器类别类别n 序列式容器排列次序取决于插入时机和位置n 关联式容器排列顺序取决于特定准则listdequevector序列式容器mapset关联式容器35容器（容器（containercontainer）n 容器是用来保存数据的，是数据结构类的总称n 容器分为三种：p顺序容器p关联容器p容器适配器其中顺序和关联容器又统称为第一类容器36STLSTL容器的共通容器的共通能力能力n 所有容器中存放的都是值而非引用，即容器进行安插操作时内部实施的是拷贝操作。因此容器的每个元素必须能够被拷贝。如果希望存放的不是副本，容器元素只能是指针。n 所有元素都形成一个次序（order），可以按相同的次序一次或多

20、次遍历每个元素n 各项操作并非绝对安全，调用者必须确保传给操作函数的参数符合需求，否则会导致未定义的行为37STLSTL容器元素的容器元素的条件条件n 必须能够通过拷贝构造函数进行复制n 必须可以通过赋值运算符完成赋值操作n 必须可以通过析构函数完称销毁动作n 序列式容器元素的默认构造函数必须可用n 某些动作必须定义operator =，例如搜寻操作n 关联式容器必须定义出排序准则，默认情况是重载operator 对于基本数据类型（int, long, char, double,）而言，以上条件总是满足38STLSTL容器的共通容器的共通操作（一）操作（一）n 产生一个空容器n 以另一个容器元

21、素为初值完成初始化n 以数组元素为初值完成初始化std:list l;std:list l;std:vector c(l.begin(),l.end();int array=2,4,6,5;std:set c(array, array+sizeof(array)/sizeof(array0);39STLSTL容器的共通操作容器的共通操作（二）（二）n 与大小相关的操作（size operator）psize()返回当前容器的元素数量pempty()判断容器是否为空pmax_size()返回容器能容纳的最大元素数量n 比较（comparison）p=,!=,=p比较操作两端的容器必须属于同一类型

22、p如果两个容器内的所有元素按序相等，那么这两个容器相等p采用字典式顺序判断某个容器是否小于另一个容器n 赋值（assignment）和交换（swap）pswap用于提高赋值操作效率40STLSTL容器的共通操作容器的共通操作（三）（三）n 与迭代器（iterator）相关的操作pbegin()返回一个迭代器，指向第一个元素pend()返回一个迭代器，指向最后一个元素之后prbegin()返回一个逆向迭代器，指向逆向遍历的第一个元素prend()返回一个逆向迭代器，指向逆向遍历的最后一个元素之后n 元素操作pinsert(pos,e)将元素e的拷贝安插于迭代器pos所指的位置perase(beg

23、,end)移除beg，end区间内的所有元素pclear()移除所有元素41迭代器（迭代器（iteratoriterator）n 可遍历STL容器内全部或部分元素的对象n 指出容器中的一个特定位置n 迭代器的基本操作操作效果*返回当前位置上的元素值。如果该元素有成员，可以通过迭代器以operator -取用+将迭代器前进至下一元素=和!=判断两个迭代器是否指向同一位置=为迭代器赋值（将所指元素的位置赋值过去）42迭代器迭代器n 所有容器都提供获得迭代器的函数操作效果begin()返回一个迭代器，指向第一个元素end()返回一个迭代器，指向最后一个元素之后begin()end()半开区间beg,

24、 end)的好处：1.为遍历元素时循环的结束时机提供了简单的判断依据（只要未到达end()，循环就可以继续）2.不必对空区间采取特殊处理（空区间的begin()就等于end()）43迭代器迭代器n 所有容器都提供两种迭代器pcontainer:iterator以“读/写”模式遍历元素pcontainer:const_iterator以“只读”模式遍历元素n 迭代器示例：iteratorbegin()end() + pos44迭代器迭代器分类分类n 双向迭代器p可以双向行进,以递增运算前进或以递减运算后退。plist、set和map提供双向迭代器n 随机存取迭代器p除了具备双向迭代器的所有属性，

25、还具备随机访问能力。p可以对迭代器增加或减少一个偏移量、处理迭代器之间的距离或者使用之类的关系运算符比较两个迭代器。pvector、deque和string提供随机存取迭代器HeadTailbeginrbeginrendend45v vectorector容器容器n vector模拟动态数组n vector的元素可以是任意类型T，但必须具备赋值和拷贝能力（具有public拷贝构造函数和重载的赋值操作符）n 必须包含的头文件#include n vector支持随机存取n vector的大小（size）和容量（capacity）通常是不同的，size返回实际元素个数，capacity返回vect

26、or能容纳的元素最大数量。如果插入元素时，元素个数超过capacity，需要重新配置内部存储器。46vectorvector应用实例应用实例#include #include using namespace std;int main() const int SIZE =6; int aSIZE=1,2,3; vector v; coutthe initial size of v is: v.size() n the initial capacity of v is: v.capacity(); v.push_back(2); v.push_back(3); v.push_back(4); co

27、utn the size of v is: v.size() n the capacity of v is : v.capacity();Vector类的实例运行结果: the initial size of v is 0 the initial capacity of v is 0 the size of v is: 3 the capacity of v is: 447vectorvector应用实例应用实例 coutn contents of a using pointer notation:; for (int *ptr = a; ptr!=a+SIZE; +ptr ) cout *p

28、tr ; coutn contents of v using iterator notation:; vector:const_iterator p; for (p=v.begin(); p!=v.end(); p+) cout *p ; 运行结果: contents of a using pointer notation: 1 2 3 0 0 0 contents of v using iterator notation: 2 3 4通过迭代器访问向量实例48vectorvector常见成员函数常见成员函数 v.begin() 返回向量v中的第一个元素的迭代器v.end() 返回向量v中的最

29、后一个元素之后位置的迭代器v.rbegin() 返回向量v中倒数第一个元素的迭代器v.rend() 返回向量v中倒数最后一个元素之前的迭代器v3=8 第三个元素设置为8v.at(3) =8 第三个元素设置为8，检查下标越界v.insert(v.begin()+1, 22) 在第二个元素位置上插入22v.insert(v.begin(), a, a+SIZE) 将数组a开始SIZE个元素插入到v的前面位置上, 使得原来的首个元素成为第SIZE+1个元素v.erase(v.begin() 清除v中的第一个元素v.erase(v.begin(), v.end()清除v中的从第一个到结束标志前的所有元

30、素 = v.clear() 清空所有元素49vectorvector容器容器n 构造、拷贝和析构操作效果vector c产生空的vectorvector c1(c2)产生同类型的c1，并将复制c2的所有元素vector c(n)利用类型T的默认构造函数和拷贝构造函数生成一个大小为n的vectorvector c(n,e)产生一个大小为n的vector，每个元素都是evector c(beg,end)产生一个vector，以区间beg,end为元素初值vector()销毁所有元素并释放内存50vectorvector容器容器n 非变动操作操作效果c.size()返回元素个数c.empty()判断

31、容器是否为空c.max_size()返回元素最大可能数量（固定值）c.capacity()返回重新分配空间前可容纳的最大元素数量c.reserve(n)扩大容量为nc1=c2判断c1是否等于c2c1!=c2判断c1是否不等于c2c1c2判断c1是否大于c2c1=c2判断c1是否小于等于c251vectorvector容器容器n 赋值操作操作效果c1 = c2将c2的全部元素赋值给c1c.assign(n,e)将元素e的n个拷贝赋值给cc.assign(beg,end)将区间beg;end的元素赋值给cc1.swap(c2)将c1和c2元素互换swap(c1,c2)同上，全局函数 std:lis

32、t l; std:vector v; v.assign(l.begin(),l.end();所有的赋值操作都有可能调用元素类型的默认构造函数，拷贝构造函数，赋值操作符和析构函数52vectorvector容器容器n 元素存取操作效果at(idx)返回索引idx所标识的元素，对idx进行越界检查operator (idx)返回索引idx所标识的元素，对idx不进行越界检查front()返回第一个元素，不检查第一个元素是否存在back()返回最后一个元素，不检查最后一个元素是否存在std:vector v; /emptyv5= t;/runtime errorstd:cout v.front();

33、/runtime error53vectorvector容器容器n 迭代器相关函数操作效果begin()返回一个迭代器，指向第一个元素end()返回一个迭代器，指向最后一个元素之后rbegin()返回一个逆向迭代器，指向逆向遍历的第一个元素rend()返回一个逆向迭代器，指向逆向遍历的最后一个元素 迭代器持续有效，除非发生以下两种情况：1. 删除或插入元素2. 容量变化而引起内存重新分配54vectorvector容器容器n 插入（insert）元素操作效果c.insert(pos,e)在pos位置插入元素e的副本，并返回新元素位置c.insert(pos,n,e)在pos位置插入n个元素e的

34、副本c.insert(pos,beg,end)在pos位置插入区间beg;end内所有元素的副本c.push_back(e)在尾部添加一个元素e的副本55vectorvector容器容器n 移除（remove）元素操作效果c.pop_back()移除最后一个元素但不返回最后一个元素c.erase(pos)删除pos位置的元素，返回下一个元素的位置c.erase(beg,end)删除区间beg;end内所有元素，返回下一个元素的位置c.clear()移除所有元素，清空容器c.resize(num)将元素数量改为num（增加的元素用defalut构造函数产生，多余的元素被删除）c.resize(n

35、um,e)将元素数量改为num（增加的元素是e的副本）56vectorvector容器容器n vector容器示例n 用vector容器实现Person类的异质链表57dequedeque容器容器n deque模拟动态数组n deque的元素可以是任意类型T，但必须具备赋值和拷贝能力（具有public拷贝构造函数和重载的赋值操作符）n 必须包含的头文件#include n deque支持随机存取n deque支持在头部和尾部存储数据n deque不支持capacity和reserve操作58listlist容器容器n 使用双向链表管理元素n list的元素可以是任意类型T，但必须具备赋值和拷贝

36、能力n 必须包含的头文件#include n list不支持随机存取，因此不提供下标操作符n 在任何位置上执行元素的安插和移除都非常快。n 插入和删除不会导致指向其他元素的指针、引用、iterator失效。59总结：顺序容器总结：顺序容器顺序容器类的共同特征：n 元素既然有顺序就有顺序号（索引号）： 位置Pos，也就是可以通过顺序号（索引号）访问该元素 n 取得已知元素的顺序号 n 在指定位置(顺序号)处插入数据项 n 删除指定项后的Count项，或删除指定范围中的数据项n front第一个元素引用n back最后一个元素引用n push_back 在容器尾部插入一个新元素n pop_back

37、 在容器尾部删除一个元素60总结：顺序容器总结：顺序容器不同之处（各自的特长）：vector: 从后面快速插入，删除。直接访问任何元素deque: 从前面或后面快速插入，删除。 直接访问任何元素list:从任何地方快速地插入，删除。 访问元素不太便利61map/map/multimapmultimap容器容器n 使用平衡二叉树管理元素n 元素包含两部分(key,value)，key和value可以是任意类型n 必须包含的头文件#include n 根据元素的key自动对元素排序，因此根据元素的key进行定位很快，但根据元素的value定位很慢n 不能直接改变元素的key，可以通过operato

38、r 直接存取元素值n map中不允许key相同的元素，multimap允许key相同的元素62map/map/multimapmultimap容器容器n 内部存储结构749258111361012yyxyqywxzyqz63容器（容器（containercontainer）n 容器是用来保存数据的，是数据结构类的总称n 容器分为三种：p顺序容器p关联容器p容器适配器其中顺序和关联容器又统称为第一类容器64容器适配器容器适配器n 非第一类容器,其最大特点为不提供存放数据的实际数据结构的实现方法, 而是依赖于三种基础的容器(顺序容器)n 容器适配器不支持迭代器n 特别提供了pop, push 成员

39、函数,实现删除和插入的操作n 有三种容器适配器: pstack (后进先出)pqueue (先进先出)ppriority_queue(优先级队列)65stackstack容器容器n 后进先出（LIFO）#include n 核心接口ppush(value)将元素压栈ptop()返回栈顶元素，但不移除ppop()从栈中移除栈顶元素，但不返回n 实例：stackstacktop()pop()push()66s stacktack适配器适配器n stackp从基本数据结构的尾部插入或删除元素p后进先出p可以用任意一种顺序容器vector, list, deque实现p默认情况下，stack用deque实现p头文件pstack的操作：push()在stack顶端插入一个元素 （用基础容器的push_back实现）pop()从stack顶端删除一个元素 （用基础容器的pop_back实现）top()取得stack顶上元素的引用 （用基础容器的back实现） 67s stacktack的操作的操作n empty()确定stack是否为空 （用基础容器的empty实现）n size()取得stack的元素的个数 （用基础容器的size实现）68s stacktack应用实例应用实例stack.c69queuequeue容器容器n 先进先出（FIFO）#in