第7章_模板new

面向对象程序设计及C 主讲人 第七章模板 本章作业 作业 一 二 3 4 三 四 3 5 本章内容提要 模板的概念 定义和使用模板的方法模板类与类模板模板函数与函数模板泛型程序设计与C STL简介 本章内容安排 7 1模板的概念7 2函数模板与模板函数7 3类模板与模板类7 4泛型程序设计与C STL简介7 5程序实例 学生信息管理系统本章小结 结束本章 7 1模板的概念 模板是C 语言的一个重要特性 模板使得程序员能够快速建立具有类型安全的类库集合和函数集合 是通用程序设计的利器 它的实现 提供了重用程序源代码的有效方法 方便了更大规模的软件开发 若一个程序的功能是对任意类型的数据进行同样的处理 则将所处理的数据类型说明为参数 就可以把这个程序改写为模板模板分为类模板 classtemplate 和函数模板 functiontemplate voidswap int 这两个重载函数的功能完全相同 函数体代码相同 形式参数个数一样 唯一的区别在于形式参数的类型不同 template 这里的class不是定义类的标识 而是表明T是一个类型参数voidswap T 对函数进行抽象 模板 模板函数 模板类与对象之间的关系示意图 返回 7 2函数模板与模板函数 函数模板就是实现数据类型参数化的函数定义 得到一个函数族 当函数中的数据成员 函数的返回值类型需要用未知类型进行抽象时 就需要定义函数模板 在需要使用函数时 用实际的数据类型对类型参数自动实例化得到对应的模板函数 调用该函数完成特定功能 7 2 1函数模板的定义与模板函数的使用 1 函数模板的一般定义形式是 template函数返回类型函数名 形式参数表 函数体 其中template是一个声明模板的关键字 class在此只是借用此关键字表示其后是一个类型参数 类型形式参数表中是用来抽象类型的标识 将来可以用任何实际的类型 包括类类型 进行实例化 在使用函数模板时 关键字class后面的类型形式参数必须实例化 即用实际的数据类型实例化类型形式参数 根据实在参数类型 将生成一个具体的模板函数 该模板函数的函数体与函数模板的函数体完全相同 所以 在程序中真正执行的代码是模板函数的代码 在VC下运行example7 01 cpp NOTE 1 参数类型的实例化是隐式进行的 根据调用时最先遇到的实在参数的类型系统自动实例化类型参数 产生一个具体的模板函数 实例化时无需显式声明 2 函数模板的异常处理问题 在应用函数模板生成模板函数时 必须遵守参数类型一致性原则 若出现不一致情况 可采用强制类型转换等手段 3 在template语句与函数模板的定义语句之间不能插入其他语句 4 类型形式参数表 可以由多个参数类型组成 则每个类型前都必须由关键字class引导 在应用函数模板生成模板函数时 必须遵守参数类型一致性原则 若出现不一致情况 可采用强制类型转换等手段 思考题中出现的错误也可以在定义模板时杜绝这种错误的发生 即将每个形式参数的类型定义为不同的类型 2 函数模板的异常处理 模板的定义格式中 类型形式参数表 说明在定义模板时 类型参数是可以由多个参数类型组成的 每个类型前都必须由关键字class引导 7 2 2重载模板函数 模板函数类似于重载函数 但是它的要求更严格 例如 函数重载时在每个函数体中可以执行不同的任务 但是同一个函数模板实例化后的所有模板函数必须执行相同的任务 所以当它遇到执行的任务有所差异时 就不可以简单的套用函数模板了 但是可以像重载普通函数那样重载模板函数 在VC下运行example7 02 cpp函数char Max char a char b 中的函数名与函数模板的函数名相同 但操作不同 函数体中的比较采用了字符串比较函数 所以有必要用重载的方法把它们区分开来 这种情况就是重载模板函数 返回 7 3类模板与模板类 一个类模板如同函数模板一样 就是实现数据类型参数化的类定义 得到一个类族 当类中的数据成员 成员函数的参数或成员函数的返回值类型需要用未知类型进行抽象时 就需要定义类模板 在需要定义对象时 首先显式地将类模板中的未知类型实例化得到一个具体的模板类 再定义模板类的对象 这样 类中的数据成员 成员函数的参数及成员函数的返回值能够根据模板参数的匹配情况获得任意想要的数据类型 当然也可以是类类型 7 3 1类模板的定义 类模板的一般定义形式是 templateclass类名 类声明体 NOTE 在类模板外定义的成员函数 与一般类的成员函数类外定义形式相比 特别要注意两点 1 定义的最开始一定要有模板前缀template 此处与类模板定义开始处的前缀一定要保持一致 2 在成员函数名前面 必须要有 类名 前缀 与一般类的成员函数相比 在类名后多了一对尖括号括起的 类型名表 因为这里的类名不是一个真正的类 而是一个类模板 是带参数的类 因此要将所带的实在参数类型名表示在尖括号中 在VC下运行example7 03 cpp 7 3 2类模板的使用 建立类模板之后 可下列方式创建对象 类模板名对象名 其中 实际类型名是实在参数 与类模板中的类型形式参数相对应 此时 类模板名就是用实际类型对类型参数实例化后得到的模板类 对象名是该模板类的实例 7 3 3模板类的生成与使用 类模板与模板类的区别在于 类模板是模板的定义 不是一个实实在在的类 定义中用到通用的类型参数 而模板类是实实在在的类定义 是类模板的实例化 类定义中参数被实际类型所代替 对象属于某一个模板类 而类模板不能定义对象 example7 04 cpp自学或在VC 下运行程序 7 4泛型程序设计与C STL简介 泛型程序设计是以类型需求为中心的程序设计方法 STL是有惠普公司的AlexanderStepanov创建 他也因此被称为STL之父 在C 未标准化的时候他就发现有些算法并不依赖于数据结构的具体实现 而只是依赖于该结构的几个最基本的属性 7 4 2STL概述 STL的一个重要特点是数据结构和算法的分离 STL另一个重要特性是它不是面向对象的 由于STL是基于模板 内联函数的使用 追求的是运行的效率 避免了虚函数的开销 这使得生成的代码短小高效 7 4 3容器 vector STL容器提供了这样的方便 对最常用的数据结构提供了支持 这些模板的参数允许指定容器中元素的数据类型 可以将许多重复而乏味的工作简化 因此容器类作为通用元素收集器 就是容纳 包含一组元素或元素集合的对象 C 语言中的容器类可以包含混合类型的元素 当容器类包含不同类型的元素时 称为异类容器类 heterogenouscontainer 当容器类包含相同类型的元素时 称为同类容器类 homogenouscontainer 容器类库中包括7种基本容器 向量 列表 双端队列 集合 映射 栈队列其中vector list deque为顺序容器 set和map为关系式容器 stack和queue为容器适配器 即可以看作由其它容器实现的容器 1 顺序容器顺序容器是将同类型的对象集合按严格的线性关系组成起来 简单地说就是数组 STL提供了向量 列表和双端队列3个顺序容器 std vector向量容器std list列表容器std deque双向队列 2 顺序容器的接口除了所有容器公用的运算符和方法外 顺序容器还拥有一个插入和删除方法集 插入方法有 1 push front 和push back 分别将一个元素加入到容器的首部或尾部 2 insert 这个函数在不同的顺序容器中有不同的版本 不会使列表容器中的迭代器实现 但可以使向量和双端队列容器中的迭代器无效 会导致双端队列和向量内部的重定位 因此在插入和删除方法后面引用迭代器时要谨慎 3 通过使用赋值运算符向容器中添加元素 可以把一个容器赋值到另一容器 删除方法 1 pop front 和pop back 分别从容器的首部和尾部移走元素 2 erase L 移走由L指向的元素 而erase L1 L2 移走L1和L2之间的元素 3 clear 则移走容器中的所有元素 对每个删除方法在移走元素时都要调用析构函数 3 向量容器可以将向量 vector 想象成能在程序运行时改变长度的数组 向量的用途与数组相同 只是它的长度能在程序运行期间自由改变 向量容器可以用来实现队列 栈 列表和其他更加复杂的结构 事实上 向量容器还可以用来实现其他所有容器 使用向量容器之前必须包含头文件 运行example7 05演示容量可变的向量容器 4 容器重分配reserve STL中容器的内存分配方案必须应付两种相反的要求 一方面 容器不能预分配大容量的内存 因为将消弱系统性能 另一方面 让容器在存储少量元素时就重分配内存也是低效的 分配策略显得很重要 5 capacity 和size 向量的长度是向量中元素的个数 容量则是当前实际分配了内存的元素的个数 对于向量v来说 可以分别用成员函数v size 和v capacity 来了解它的长度和容量 size 返回容器现在存储元素的数量 capacity 返回容器不需重分配就能存储的元素的总数量 运行example7 06 cpp演示容器重分配即容量测定 6 成员函数at 重载运算符 使直接访问vector的元素成为可能 但是仍然不会检查引用是否是有效的元素 由于缺省运行期检查 从而保证了最快的访问速度 使用 符号也使程序更易读更直观 尽管如此 运行期检查在有些情况下也是不可避免的 使用成员函数at 来代替运算符 更安全 运行example7 07 cpp 7 front和back操作成员函数front 和back 分别访问容器开始和结尾的一个元素 成员函数push back 在容器的结尾附加一个元素 当容器耗尽它的空闲内存时 函数重分配内存再附加元素 成员函数pop back 将最后一个元素移出容器 运行example7 08 cpp 演示front与back的使用 8 容器赋值STL容器重载赋值运算符 因此允许同类型的容器互相赋值 每一个vector元素都必须是同样的大小 因为派生对象可能有额外的成员 它的大小可能比基类要大 不要将派生对象存储在vector中 但是可以通过存储派生对象指针到vector来达到多态 7 4 3迭代器 iterator 迭代器本质上不是指针 但不妨像那样想 并把它当作一个指针来使用 STL的每一个容器类模板中都定义了一组对应的迭代器类 使用迭代器 算法函数可以访问容器中指定位置的元素 而无需关心元素的具体类型 STL中主要的五种迭代器 正向迭代器 forwarditerator 双向迭代器 bidirectionaliterator 随机访问迭代器 randomaccessiterator 输入迭代器 inputiterator 输出迭代器 outputiterator 1 using声明STL中的每种容器类型都有它自己的迭代器类型 不过所有迭代器的基本使用方法都是相同的 讨论迭代器时 通常将 操作符应用于另一个级别 如 usingstd vector iterator 在这个例子中 标识符iterator命名了一种迭代器类型 所以 在这个using预编译指令的作用域中 以下语句是允许的 iteratorp 上述语句声明了具有iterator类型的p p就是一个迭代器 运行example7 09 cpp2 指针用作迭代器一个指针也是一种迭代器 example7 10 cpp显示了如何把指针作为迭代器用于STL的find 算法来搜索普通的数组 该例中find 函数接受三个参数 头两个定义了搜索的范围 由于数组名等同于指针 表达式iarray指向数组的第一个元素 而第二个参数iarray SIZE等同于past the end值 也就是数组中最后一个元素的后面位置 第三个参数是待定位的值 也就是50 find 函数返回和前两个参数相同类型的迭代器 这儿是一个指向整数的指针ip 3 容器中的迭代器两个典型的容器类方法是begin 和end 它们在大多数容器中表示整个容器范围 begin 返回指向容器第一个元素的迭代器 end 返回一个指向位于容器最后一个元素之后 past 的迭代器 其他一些容器还使用rbegin 和rend 方法提供反向迭代器 以按反向顺序指定对象范围 运行example7 11 cpp example7 12 cpp 4 逆向迭代器只要容器具有双向迭代器 就可以使用逆向迭代器来遍历一个容器中的所有元素 和正向迭代器一样 也必须先声明反向迭代器类型reserve iterator 常规形式如下 Usingste vector reserve iteratorrp for rp c rbegin rp c rend rp reserve iterator为逆向迭代器类型 rbegin 返回的是定位到最后一个元素的迭代器 rend 返回容器的第一个元素的前导位置 实际上这是该容器前后反转之后的end 5 常量迭代器间接访问运算符 已经为STL容器迭代器进行了重载 所以 p能生成位置p出的元素 尤其是对一个向量容器来说 p将允许更改位于p处的元素 但是并不是所有的迭代器都允许更改元素 使用常量迭代器 运算符 只能进行只读操作 不能通过向 p赋值来更改容器中的元素 7 4 5算法 STL标准模板库中的算法主要有三种类别 不改变序列的算法改变序列的算法排序算法 1 不改变序列的操作泛型算法find 是搜索一个容器 在其中定位一个元素在容器中的位置 可以作用于任何STL顺序容器类 find 接受三个参数 头两个是指向序列开头和结尾的迭代器 第三个参数是要查找的值 find 返回指向第一个与要查找值相匹配元素的迭代器 如果find 不能找到要求的值 它返回指向最后一个元素之后一个位置的迭代器 即第二个迭代器参数 运行example7 13 cpp example7 14 cpp 2 改变序列的操作copy 的第一个和第二个参数是标志序列开始和结尾的const迭代器 第三个参数指向要拷贝到的容器 remove vector iteratorfirst vector iteratorlast constT target 从范围 first last 中删除等于target的那些元素reserve vector iteratorfirst vector iteratorlast 将范围 first last 中的元素逆向排列replace vector iteratorfirst vector iteratorlast constT target1 onstT target2 将范围 first last 中的等于target1的那些元素置换为target2运行example7 15 cpp 3 排序操作4个排序算法 sort partial sort partial sort copy 和stable sort 4个二分查找算法 binary search lower bound uper bound 和equal range 2个用于合并有序区间的通用算法 merge 和inplace merge 4个最值算法 min max min element max element 3个与排列方式有关的算法 lexicographical compare next permutation 和prev permutation 5个用于有序序列上的集合操作的算法 includes set union set intersection set defference 和set symmetric difference 4个为堆的创建和操作提供的算法 make heap pop heap push heap 和sort heap 运行example7 16 cpp 7 4 6string类型 string类在名称同样为的一个库中定义 定义放在std命名空间 所以 要想使用string类 代码中必须包含以下语句 或其他等价的语句 includeusingnamespacestd 使用string类 可以采取与处理简单类型的值极为相似的方式来处理string值和string表达式 可以用 为string变量赋值 可用 来连接两个字符串 1 标准类stringstring有一个默认构造函数和多个重载构造函数 默认构造函数将string对象初始化成空字符串 string 默认构造函数 建立一个长度为0的串 string conststring 将对象str中的串从位置pos开始取n个字符 初始化string类的对象 string constchar s unsignedintn 用指针s所指向的字符串中的前那个字符初始化string类的对象string unsignedintn charc 将参数c中的字符重复n次 初始化string类的对象换句话说 string可以通过C字符串 通过其他string对象 通过C字符串的部分 通过字符序列 通过其他string的部分来初始化 运行example7 17 cpp 演示字符串的初始化 2 string类的I O可以用流插入操作符 和cin时 会忽略最初的空白符号 并在接受输入字符后遇到第一个空白字符就停止读入 运行example7 18 cpp 3 常用成员函数功能简介大小和容量函数一个C 字符串存在三种大小 a 现有的字符数 函数是size 和length 他们等效 empty 用来检查字符串是否为空 b max size 这个大小是指当前C 字符串最多能包含的字符数 很可能和机器本身的限制或者字符串所在位置连续内存的大小有关系 一般情况下可以不用关心它 应该大小足够使用 但是不够用的话 会抛出length error异常 c capacity 重新分配内存之前string所能包含的最大字符数 前文中的reserve 函数在此也起作用 为string重新分配内存 重新分配的大小由其参数决定 默认参数为0 这时候会对string进行非强制性缩减 元素存取可以使用下标操作符 和函数at 对元素包含的字符进行访问 但是应该注意的是操作符