C++强化培训课件(2)—泛型编程与STL

模板的引入 程序设计中 当参与运算的数的值会随实际情况而变化时 就使用变量来代替这个数 同理 当处理的数据类型随实际情况变化时 可以将数据类型作为可变的部分 类型参数 从程序中抽取出来 当出现真实的数据类型时 再用具体的数据类型代替 模板就是为解决这个问题而产生C 中对数据进行处理的主体可以是函数 也可以是类 因此模板包括函数模板 类模板 模板 在C 标准库中 几乎所有的代码都是模板代码 模板是一种参数化的多态工具 所谓参数化的多态性 是指将程序所处理的对象的类型参数化 使一段程序代码可以用于处理多不同类型的对象 采用模板编程 可以为各种逻辑功能相同而数据类型不同的程序提供一种代码共享的机制 继承和组合提供了重用对象代码的方法 而模板提供了重用源代码的方法 问题 考虑求两数中大值函数max a b 对于a b的不同类型 都有相同的处理形式 returna b a b 用已有方法解决 1 宏替换 definemax a b a b a b 问题避开类型检查 2 重载问题需要许多重载版本 3 使用函数模板 模板分类 函数模板 functiontemplate 类模板 classtemplate 函数模板 对不同类型的数据执行相似的操作函数重载函数模板函数重载 代码冗余增加编程负担程序的维护问题 如功能修改 函数模板 C 提供的函数模板可以定义一个对任何类型变量进行操作的函数函数模板为所有的函数提供唯一的一段函数代码 增强了函数设计的通用性使用函数模板的方法是先说明函数模板 然后实例化成相应的模板函数进行调用执行函数模板不是函数 不能被执行置换代码中的类型参数得到模板函数 实例化实例化后的模板函数是真正的函数 可以被执行 函数模板的定义 函数模板的一般说明形式如下 template返回值类型函数名 模板函数形参表 函数定义体 函数模板的定义以关键字template开头template之后中是函数模板的参数列表函数模板的参数是类型参数 其类型为class或typenametemplatetemplate 函数模板的定义 模板的参数定义之后是函数模板的定义 是一个将类型参数作为某种类型使用的函数函数模板的参数名在模板中作为一种类型使用 可以用于函数的形参 函数返回值和函数的局部变量模板的每个形式参数要在函数的参数列表中至少出现一次形式参数名的作用域局限于函数模板的范围内 函数模板的定义示例 include defineSIZE8templatevoidsortArray ElementTypeb intlen for intpass 0 passb i ElementTypehold hold b pass b pass b i b i hold templatevoiddisplayArray ElementTypeb intlen for intindex 0 index len 1 index if index len 1 cout b index t elsecout b index endl 函数模板的使用 函数模板规定了对数据的处理流程某些数据类型 模板的参数 要等到模板实例化时再确定具体的类型函数模板的实例化由编译器来完成根据函数调用的实参类型确定模板形参的具体类型用相应的类型替换函数模板中的模板参数完成函数模板的实例化 函数模板的使用示例 voidmain intai SIZE 18 35 36 61 9 112 77 12 doubleaf SIZE 12 1 23 8 3 7 16 0 9 1 12 12 7 7 56 3 cout Beforesorting n ai t displayArray ai SIZE sortArray ai SIZE cout Aftersorting n ai t displayArray ai SIZE cout Beforesorting n af t displayArray af SIZE sortArray af SIZE cout Aftersorting n af t displayArray af SIZE 重载函数模板 C 语言允许一个函数模板可以使用多个模板参数或者重载一个函数模板用户可以用非模板函数重载一个同名的函数模板 类模板 类模板 将类定义中的数据类型参数化类模板实际上是函数模板的推广 可以用相同的类模板来组建任何类型的对象集合 类模板的定义 templateclass 类说明体 template 形参表 成员函数定义体 template 形参表 成员函数定义体 template 形参表 成员函数定义体 类模板的定义示例 tstack h 类模板的定义templateclassStack public Stack int 8 省缺栈元素的树数目为8 Stack delete data intpop ElementType 类模板的定义示例 stack cpp 类模板的实现templateStack Stack ints size s 0 s 8 data newElementType size memNum 0 templateintStack pop ElementType templateintStack push ElementTypemem if memNum size return0 data memNum mem return1 使用类模板 类模板的实例化 用具体的数据类型替换模板的参数以得到具体的类 模板类 模板类也可以实例化为对象用下列方式创建类模板的实例 类名对象名称 类模板的使用示例 include include tstack h intmain StackdoubleStack 6 doublef 3 14 cout PushingelementsintodoubleStack n while doubleStack push f cout f f f cout nStackisfull Cannotpush f ontothedoubleStack cout nPoppingelementsfromdoubleStack n while doubleStack pop f cout f 类模板的使用示例 coutintStack inti 1 cout nPushingelementsintointStack n while intStack push i cout i i cout nStackisfull push i failed cout n nPoppingelementsfromintStack n while intStack pop i cout i cout nStackisempty Cannotpop n return0 派生类模板 通过继承可以产生派生类通过继承同样可产生派生的类模板几种不同的派生 从一般类派生出类模板从类模板中派生出类模板 从一般类派生出类模板 一般类 其中不使用类型参数的类 作基类 派生出类模板 其中要使用类型参数 基本语法 classCB CB为一般类 templateclassCA publicCB 被派生出的CA为类模板 使用了类型参数TTt 私有数据为T类型的public 从类模板派生出类模板 类模板作基类 派生出新的类模板 但仅基类中用到类型参数T 而派生的类模板中不使用T 基本语法 templateclassCB CB为类模板Tt 私有数据为T类型的public Tgett 用到类型参数Treturnt templateclassCA publicCB CA为类模板 其基类CB为类模板 将被 传递 给基类CB 本派生类中并不使用该类型参数Tdoublet1 私有数据成员 从类模板派生出类模板 类模板作基类 派生出新的类模板 且基类与派生类中均使用同一个类型参数TtemplateclassCB CB为类模板 其中使用了类型参数T 它将作为类模板CA的基类Tt 数据成员为T类型的public Tgett 用到类型参数Treturnt templateclassCA publicCB CA为类模板 其基类CB也为类模板 注意 类型参数T将被 传递 给基类CB 本派生类中也将使用这同一个类型参数TTt1 数据为T类型的public 从类模板派生出类模板 类模板作基类 派生出新的类模板 但基类中使用类型参数T2 而派生类中使用另一个类型参数T1 而不使用T2 templateclassCB CB为类模板 其中使用了类型参数T2 它将作为类模板CA的基类T2t2 数据为T2类型的public templateclassCA publicCB CA为类模板 其基类CB也为类模板 注意 类型参数T2将被 传递 给基类CB 本派生类中还将使用另一个类型参数T1T1t1 数据为T1类型的public 类模板继承示例 ifndefCMYSTRING H defineCMYSTRING H pragmawarning disable 4786 includeusingnamespacestd classCMyString publicbasic string public voidTrim voidLTrim voidRTrim CMyString CMyString constchar s endif 类模板继承示例 include CMyString h voidCMyString LTrim string size typelen if len this size 0 return this erase 0 this find first not of t 0 voidCMyString RTrim string size typelen if len size 0 return this erase this find last not of t 1 类模板继承示例 CMyString CMyString basic string CMyString CMyString constchar s basic string s voidCMyString Trim LTrim RTrim include CMyString h includeusingnamespacestd voidmain CMyStringstr1 tHelloWorld str1 Trim cout str1 endl 派生类和模板 为了运行的效率 类模板是相互独立的 即独立设计 没有使用继承的思想 对类模板的扩展是采用适配子 adapter 来完成的 通用性是模板库的设计出发点之一 这是由泛型算法和函数对象等手段达到的 派生类的目标之一也是代码的复用和程序的通用性 最典型的就是MFC 派生类的优点是可以由简到繁 逐步深入 程序编制过程中可以充分利用前面的工作 一步步完成一个复杂的任务 模板追求的是运行效率 而派生追求的是编程的效率 泛型程序设计 将程序写得尽可能通用将算法从特定的数据结构中抽象出来 成为通用的C 的模板为泛型程序设计奠定了关键的基础 什么是STL STL StandardTemplateLibrary 即标准模板库 是一个高效的C 程序库 被容纳于C 标准程序库 C StandardLibrary 中 是ANSI ISOC 标准中最新的也是极具革命性的一部分包含了诸多在计算机科学领域里常用的基本数据结构和基本算法 为广大C 程序员们提供了一个可扩展的应用框架 高度体现了软件的可复用性 什么是STL 从逻辑层次来看 在STL中体现了泛型化程序设计的思想 genericprogramming 在这种思想里 大部分基本算法被抽象 被泛化 独立于与之对应的数据结构 用于以相同或相近的方式处理各种不同情形从实现层次看 整个STL是以一种类型参数化 typeparameterized 的方式实现的基于模板 template STL历史 1971 DavidR Musser开始倡导GenericProgramming概念1979 AlexanderStepanov创造STL1987 Alex和Musser开发出一套Adalibrary Alex先后在AT T及HP实验室以C及C 实验大量的体系结构和算法形式 1992 MengLee加入称为另一位主要贡献者1993 11 Alex于ANSI ISOC 会议展示1994夏 STL被纳入C 标准 STL组件 Container 容器 各种基本数据结构Adapter 适配器 可改变containers或functionobject接口的一种组件Algorithm 算法 各种基本算法如sort search 等Iterator 迭代器 连接containers和algorithmsFunctionobject 函数对象 Allocator 分配器 容器 容器类是容纳 包含一组元素或元素集合的对象异类容器类与同类容器类顺序容器与关联容器七种基本容器 向量 vector 双端队列 deque 列表 list 集合 set 多重集合 multiset 映射 map 和多重映射 multimap 标准容器的成员绝大部分都具有共同的名称 类型成员 类型成员 类型成员 类型成员 类型成员 类型成员 适配器 适配器是一种接口类为已有的类提供新的接口目的是简化 约束 使之安全 隐藏或者改变被修改类提供的服务集合三种类型的适配器容器适配器 用来扩展7种基本容器 它们和顺序容器相结合构成栈 队列和优先队列容器迭代器适配器函数对象适配器 迭代器 迭代器是面向对象版本的指针 它们提供了访问容器 序列中每个元素的方法 算法 C 标准模板库中包括70多个算法其中包括查找算法 排序算法 消除算法 记数算法 比较算法 变换算法 置换算法和容器管理等等这些算法的一个最重要的特性就是它们的统一性 并且可以广泛用于不同的对象和内置的数据类型 顺序容器 顺序容器的接口插入方法push front push back insert 运算符 删除方法pop erase clear 迭代访问方法使用迭代器其他顺序容器访问方法 不修改访问方法 front back 下标 运算符 顺序容器 向量 vector 向量属于顺序容器 用于容纳不定长线性序列 即线性群体 提供对序列的快速随机访问 也称直接访问 数据结构很像一个数组 所以与其他容器相比 vector能非常方便和高效访问单个元素 支持随机访问迭代子向量是动态结构 它的大小不固定 可以在程序运行时增加或减少与数组不同 向量的内存用尽时 向量自动分配更大的连续内存区 将原先的元素复制到新的内存区 并释放旧的内存区 这是向量类的优点 头文件 include vector的使用 include include include 包含向量容器头文件usingnamespacestd voidmain vectorA 10 intn intprimecount 0 i j cout 2asupperlimit cin n A primecount 2 for i 3 i n i if primecount A size A resize primecount 10 vector的使用 if i 2 0 continue j 3 while ji 2 A primecount i for i 0 i primecount i 输出质数cout setw 5 A i if i 1 10 0 每输出10个数换行一次cout endl cout endl 顺序容器 双端队列 deque 双端队列是一种放松了访问权限的队列 元素可以从队列的两端入队和出队 也支持通过下标操作符 进行直接访问与向量的对比 功能上 和向量没有多少区别 性能上 在双端队列起点上的插入和删除操作快头文件 include 顺序容器 列表 list 列表主要用于存放双向链表 可以从任意一端开始遍历 列表还提供了拼接 splicing 操作 将一个序列中的元素从插入到另一个序列中对比 元素的插入和删除操作对list而言尤为高效与vector和deque相比 对元素的下标访问操作的低效是不能容忍的 因此list不提供这类操作头文件 include list的使用 include includeusingnamespacestd intmain listLink 构造一个列表用于存放整数链表inti key item for i 0 i item Link push front item cout iteratorp Link begin list的使用 while p Link end 输出各节点数据 直到链表尾cout key Link remove key cout List 输出链表p Link begin 使P重新指向表头while p Link end cout p p 使P指向下一个节点 cout endl 如何选择顺序容器 三种成员中的任何一种都无法在所有操作的性能上优于其他两种需要频繁在序列内部位置上进行插入和 或删除操作且不需要过多地在序列内部进行长距离跳转 应该选择 链表仅仅出于可动态改变大小的原因 应该选择 向量和双端队列 关联容器 通过保存在数据项中的索引项 尽可能快速检索数据项STL标准库中只包含有序关联容器set multiset map multimapset multiset 数据项就是索引项 multiset允许出现重复的索引项 map multimap 数据项是由索引项和其他某种类型的数据组成的一对数据 multimap允许出现重复的索引项 关联容器 map 增加和删除节点对迭代器的影响很小 对于迭代器来说 可以修改实值 而不能修改key自动建立Key value的对应 key和value可以是任意你需要的类型 根据key值快速查找记录 查找的复杂度基本是Log N 如果有1000个记录 最多查找10次 1 000 000个记录 最多查找20次 map的构造函数 使用map得包含map类所在的头文件 includemap对象是模板类 需要关键字和存储对象两个模板参数 mappersonnel 用int作为索引 存储string对象 map的成员函数 map类已经对 操作符进行了重载插入2时 先在enumMap中查找主键为2的项 没发现 然后将一个新的对象插入enumMap 键是2 值是一个空字符串 插入完成后 将字符串赋为 Two 但是该方法会将每个值都赋为缺省值 然后再赋为显示的值 如果元素是类对象 则开销比较大 可以用以下insert 来避免开销 map的成员函数 下标操作符给出了获得一个值的最简单方法 CStringtmp enumMap 2 但是 只有当map中有这个键的实例时才对 否则会自动插入一个实例 值为初始化值 我们可以使用Find 和Count 方法来发现一个键是否存在 查找map中是否包含某个关键字条目用find 方法 传入的参数是要查找的key通过map对象的方法获取的iterator数据类型是一个std pair对象 包括两个数据iterator first和iterator second分别代表关键字和存储的数据 从map中删除元素 移除某个map中某个条目用erase 该成员方法的定义如下iteratorerase iteratorit 通过一个条目对象删除iteratorerase iteratorfirst iteratorlast 删除一个范围size typeerase constKey map的使用 include include includeusingnamespacestd voidmain maptrans map typedefmap value typevalType trans map insert valType 001 grateful trans map insert valType 002 them trans map insert valType 003 because trans map insert valType 004 no trans map insert valType 005 says trans map insert valType 006 thanks trans map insert valType 007 was map的使用 trans map insert valType 008 suppose map iteratorit cout Hereisourtransformationmap n n for it trans map begin it trans map end it cout key it first t value it second n cout FindKey 005 endl it trans map find 105 if it trans map end cout notfound endl else cout key it first t value it second n 关联容器 multimap multimap除了元素对的关键字不是唯一外 与map相似头文件 include 关联容器 set set可以被视为只有关键字而没有相关的元素值的map 因此set的用户接口也发生了微小的变化 成员类型中没有 typedefKeyvalue type typedefCmpvalue compare操作中没有元素的下标访问操作头文件 include 关联容器 multiset multiset除了关键字不是唯一外 与set相似头文件 include 迭代器 迭代器是面向对象版本的指针指针可以指向内存中的一个地址迭代器可以指向容器中的一个位置STL的每一个容器类模版中 都定义了一组对应的迭代器类 使用迭代器 算法函数可以访问容器中指定位置的元素 而无需关心元素的具体类型 elem 0 elem 1 elem n 1 begin end 迭代器的类型 输入迭代器可以用来从序列中读取数据输出迭代器允许向序列中写入数据前向迭代器既是输入迭代器又是输出迭代器 并且可以对序列进行单向的遍历双向迭代器与前向迭代器相似 但是在两个方向上都可以对数据遍历随机访问迭代器也是双向迭代器 但能够在序列中的任意两个位置之间进行跳转 迭代器的类型表 迭代器的使用 include includeusingnamespacestd intmain inti key listintList list iteratorit cout key intList push front key cout datalist endl it intList end while 1 cout width 6 cout it if it intList begin break return0 函数对象 一个行为类似函数的对象 它可以没有参数 也可以带有若干参数 其功能是获取一个值 或者改变操作的状态 任何普通的函数和任何重载了调用运算符operator 的类的对象都满足函数对象的特征 STL中也定义了一些标准的函数对象 如果以功能划分 可以分为算术运算 关系运算 逻辑运算三大类 为了调用这些标准函数对象 需要包含头文件 已集成的函数对象 可以自己编写一个函数作为算法的参数 自定义函数对象 includeusingnamespacestd classCFunObj public voidoperator cout hello functionobject endl intoperator inti cout hello functionobjectother endl returni 1 private intdat voidmain CFunObjfo fo cout fo 1 endl CFunObj 标准C 库中的算法 算法本身是一种函数模板不可变序列算法 non mutatingalgorithms 不直接修改所操作的容器内容的算法可变序列算法 mutatingalgorithms 可以修改它们所操作的容器的元素 算法部分主要由头文件 和组成 STL算法的头文件 是所有STL头文件中最大的一个 它是由一大堆模版函数组成的 可以认为每个函数在很大程度上都是独立的 其中常用到的功能范围涉及到比较 交换 查找 遍历操作 复制 修改 移除 反转 排序 合并等等 体积很小 只包括几个在序列上面进行简单数学运算的模板函数 包括加法和乘法在序列上的一些操作 中则定义了一些模板类 用以声明函数对象 标准函数 标准函数 标准函数 标准函数 标准函数 标准函数 泛型算法示例 include include include include include includeusingnamespacestd intmain intia 1 2 3 4 5 7 9 11 vectoriv ia ia 8 累加 52cout accumulate iv begin iv end 10 endl 相邻差值adjacent difference iv begin iv end iv begin 复制到ostream iterator去 每列印一个元素 即加上一个空格 泛型算法示例 copy iv begin iv end ostream iterator cout 11111222 计算元素值为2的个数