面向对象泛型技术

1、面向对象设计方法面向对象设计方法n9.1 泛型简介n9.2 C+中的泛型n9.3 STLn9.4 JAVA中的泛型n9.5 C+和JAVA中泛型的比较n9.6 泛型的好处第九章第九章 泛型技术泛型技术1.1.泛型泛型 泛型(Generic)，是指具有在多种数据类型上皆可操作的含意 。既编写的代码可以在不同的数据类型上重用。 实现对源代码进行重用，既不是通过继承和聚合重用对象代码 ，也不是代码的复制粘贴复用。 泛型编程(Generic Programming) 9.1 9.1 泛型简介泛型简介9.2.1 C+中泛型简介 在C+语言中称泛型为模板(template),模板由函数模板和类模板两部分组

2、成，以所处理的数据类型的说明作为参数的函数叫做函数模板，而以所处理的数据类型的说明作为参数的类就叫类模板。9.2 C+9.2 C+中的泛型中的泛型1. 示例：加法函数的重载int Add( int a, int b ) return a + b ;long Add(long a, long b ) return a + b ; 根据不同的数据类型进行多次重载，但是实现的代码都是一致的。.2 函数模板函数模板2. 函数模板的语法template Type Add( Type a, Type b ) return a + b ; 具体使用为：Add(10,100);Add(10.1

3、,23.4);.2 函数模板函数模板template : 关键字,总是放在模板的定义与声明的最前面 : 模板参数列表，如果有多个模板参数用逗号隔开；模板参数分模板类型参数和模板非类型参数(代表一个常量表达式)。class：关键字, 声明模板类型参数，用typename替代也可以。.2 函数模板函数模板template 例如：template Type Add( Type a, TypeB b ) return a + b ; 注意此时a和b是两种不同的变量类型.2 函数模板函数模板例如：template Type Add( Type a) ret

4、urn a + size ; 注意此时a是模板类型参数，而size是模板非类型参数。模板非类型参数是常整数（包括枚举值）或者指向外部链接对象的指针，不能是浮点数和类对象。.2 函数模板函数模板例如：template Type Add( Type a , int size) return a + size ; 注意此时a是模板类型参数，而size是函数参数.2 函数模板函数模板3. 模板函数的实例化 用系统实际的内置或用户定义类型将替换模板的类型参数。 具体见源代码示例。注意： 不论是内置类型还是用户自定义类型必须要支持模板函数内的操作。.2 函数

5、模板函数模板1.1.示例示例： List链表的实现链表的实现class ListIntpublic:void Add(int nValue);bool Insert(int nIndex, int nValue);int Remove(int nIndex); 只能满足整型链表的要求，要根据不同的数据类型编写多个链表类。9.2.3 9.2.3 类模板类模板2.类模板的定义template class Listpublic:void Add(T nValue);bool Insert(int nIndex, T nValue);T Remove(int nIndex);9.2.3 9.2.3 类

6、模板类模板3. 类模板方法的实现方式template void List :Add(T nValue).9.2.3 9.2.3 类模板类模板4. 类模板的实例化 用系统实际的内置或用户定义类型将替换模板的类型参数。List intList;List douList;注意： 不论是内置类型还是用户自定义类型必须要支持类模板内的操作。9.2.3 9.2.3 类模板类模板9.3.1 STL简介简介1. STL的含义的含义 STL：Standard Template Library，标准模板库,STL是泛型编程的实现品；STL就是一个数据结构和算法框架。 STL的设计目标就是将不同的算法和数据结构结合

7、起来，并获得最佳效率。9.3 STL9.3 STL2. STL与与C+标准程序库标准程序库 STL于1994年被纳入C+标准程序库。STL虽然加入C+标准库的时间相对较晚，但它却是C+标准程序库中最具革命性的部分，同时也是C+标准程序库中最重要的组成部分。9.3.1 STL简介3. STL内容 STL的代码从广义上讲分为三类： container(容器)、algorithm(算法)和iterator（迭代器），几乎所有的代码都采用了模板类和模板函数的方式。9.3.1 STL简介容器 对最常用的数据结构提供了支持 ：vector,list,set,map,stack和queue 。 遗憾的是标准

8、中没有支持哈希表。9.3.1 STL简介算法 STL提供了大约100个实现算法的模版函数 。其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。9.3.1 STL简介迭代器 迭代器在STL中用来将算法和容器联系起来，起着一种黏和剂的作用。几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的迭代器，用以存取容器中的元素。 9.3.1 STL简介1. 命名空间命名空间(namespace)std 当你采用不同的模块和程序库时，经常会出现名称冲突现象，这是因为不同的模块和程序库可能针对不同的对象使用相同的标识符. n

9、amespace可以解决该问题。 C+标准程序库中所以的标识符都统一到std这个命名空间。9.3.2 几个基本概念 使用c+标准程序库的标识符有三种方法可供选择：1 直接指定标识符使用std:cout std:hex 3.4 使用使用using declaration ，在文件头处申明，在文件头处申明如下：如下：using std:cout;using std:endl;cout std:hex 3.4 使用使用using declaration ，在文件头处申明，在文件头处申明如下：如下：using std:cout;using std:endl;cout std:hex 3.4 使用使用u

10、sing directive ，在文件头处申明如，在文件头处申明如下：下：using namespace std;cout hex 3.4 endl; 这种使用方式最简单，所有在使用该标识这种使用方式最简单，所有在使用该标识符，都不需要添加符，都不需要添加“std:”，但在大程序中可，但在大程序中可能会出现命名冲突。能会出现命名冲突。9.3.2 几个基本概念2. 头文件头文件 C+标准程序库中头文件没有扩展名，使用如下： #include #include 为了向下兼容，你也可以使用旧式的C+头文件： #include 9.3.2 几个基本概念3. 配置器配置器(Allocators) 配置器

11、用于处理内存配置和寻址，是一种特定的内存模型。9.3.2 几个基本概念1. 容器的分类容器的分类9.3.3 STL容器序列式容器序列式容器 每个元素均有固定的位置每个元素均有固定的位置-取决于插入的取决于插入的时机和地点，和元素值无关。时机和地点，和元素值无关。STL提供了提供了vector、list和和deque三个序列式容器。三个序列式容器。关联式容器关联式容器 元素位置取决于特定的排序准则和元素值，元素位置取决于特定的排序准则和元素值，和插入次序无关。和插入次序无关。STL提供了四个关联式容器：提供了四个关联式容器：set、multiset、map和和multimap。9.3.3 STL

12、容器2. vector Vector将其元素置于一个动态数组中加以将其元素置于一个动态数组中加以管理：它允许随机存取，也就是说你可以利用管理：它允许随机存取，也就是说你可以利用索引直接存取任何一个元素。索引直接存取任何一个元素。 在数组尾部增加元素或移除元素均非常快在数组尾部增加元素或移除元素均非常快速，但是在中部或头部安插元素就比较费事。速，但是在中部或头部安插元素就比较费事。 (见示例见示例)9.3.3 STL容器3. deque deque: double-ended queue, 双端队列。双端队列。它也是一个动态数组，但是可以向两端发展，它也是一个动态数组，但是可以向两端发展，因此无

13、论先头部还是尾部安插元素都是非常迅因此无论先头部还是尾部安插元素都是非常迅速。但如果在中间插入数据比较费事，因为要速。但如果在中间插入数据比较费事，因为要移动其他元素。移动其他元素。 (见示例见示例)9.3.3 STL容器4. list list, 双向链表，每个元素都有其前趋元素双向链表，每个元素都有其前趋元素和后继元素。和后继元素。List不提供随机存取，但是其在不提供随机存取，但是其在任何位置插入或删除元素速度快，效率高。任何位置插入或删除元素速度快，效率高。 (见示例见示例)9.3.3 STL容器5. set set的内部元素依据其值自动排序，每个元的内部元素依据其值自动排序，每个元素

14、值只能出现一次，不允许重复。素值只能出现一次，不允许重复。6. Multiset 和和set相同，只不过它允许重复元素。相同，只不过它允许重复元素。7.Map map的元素都是的元素都是“实值实值/键值键值”所形成的一所形成的一个对组，每个元素有一个键，是排序的基础。个对组，每个元素有一个键，是排序的基础。8. Multimap 和和map相同，只是允许重复键值。相同，只是允许重复键值。 9.3.3 STL容器1. STL容器的共同能力容器的共同能力 1 所有容器提供的都是所有容器提供的都是“Value语意语意”而非而非“reference语意语意”。也就是说容器进行。也就是说容器进行元素安插

15、操作时，内部实施的是拷贝操作，置元素安插操作时，内部实施的是拷贝操作，置于容器内。因此于容器内。因此STL容器的每一个元素都必须容器的每一个元素都必须能够被拷贝。能够被拷贝。-拷贝构造函数拷贝构造函数。 2 每个容器都有迭代器，利用迭代器就每个容器都有迭代器，利用迭代器就可以遍历容器里的每个元素。可以遍历容器里的每个元素。 9.3.4 容器的共同能力和操作 3 一般而言，各项操作并非绝对安全。一般而言，各项操作并非绝对安全。调用者必须确保传给操作函数的参数符合需求。调用者必须确保传给操作函数的参数符合需求。违反这些需求违反这些需求(例如使用非法索引例如使用非法索引)会导致未定会导致未定义的行为

16、。义的行为。 9.3.4 容器的共同能力和操作2. STL容器的共同操作容器的共同操作n初始化初始化n与大小相关的函数与大小相关的函数n比较比较n赋值赋值 9.3.4 容器的共同能力和操作提供容器默认初始化的构造函数。通常每个容提供容器默认初始化的构造函数。通常每个容器都有几个不同的构造函数，提供容器不同器都有几个不同的构造函数，提供容器不同的初始化方法的初始化方法将容器初始化为现有同类容器副本的构造函数将容器初始化为现有同类容器副本的构造函数撤消容器时，进行内存处理撤消容器时，进行内存处理判容器是否为空，空返回判容器是否为空，空返回true,true,不空返回不空返回falsefalse返回

17、容器中最多允许的元素量返回容器中最多允许的元素量返回容器当前元素量返回容器当前元素量默认构造函数默认构造函数拷贝构造函数拷贝构造函数析构函数析构函数empty()empty()max_size()max_size()size()size()说明说明标准库容器共有的函数标准库容器共有的函数将一个容器赋值拷贝给另一个同类容器将一个容器赋值拷贝给另一个同类容器交换两个容器的元素交换两个容器的元素如果前面的容器小于后面的容器，则返回如果前面的容器小于后面的容器，则返回true，否，否则返回则返回false，不适用于，不适用于priority_queue如果前面的容器小于等于后面的容器，则返回如果前面的

18、容器小于等于后面的容器，则返回true，否则返回，否则返回false，不适用于，不适用于priority_queue如果前面的容器大于后面的容器，则返回如果前面的容器大于后面的容器，则返回true，否，否则返回则返回false，不适用于，不适用于priority_queue如果前面的容器大于等于后面的容器，则返回如果前面的容器大于等于后面的容器，则返回true，否则返回，否则返回false，不适用于，不适用于priority_queue如果前面的容器等于后面的容器，则返回如果前面的容器等于后面的容器，则返回true，否，否则返回则返回false，不适用于，不适用于priority_queue如

19、果前面的容器不等于后面的容器，则返回如果前面的容器不等于后面的容器，则返回true，否则返回否则返回false，不适用于，不适用于priority_queueoperator=swap()operatoroperatoroperator=operator=operator!=说明说明标准库容器共有的函数标准库容器共有的函数获得指向被控序列开始处的迭代子，引用容器获得指向被控序列开始处的迭代子，引用容器第一个元素第一个元素获得指向被控序列末端的迭代子，引用容器最获得指向被控序列末端的迭代子，引用容器最后一个元素的后继位置后一个元素的后继位置获得指向被控序列末端的反转型迭代子，引用获得指向被控序列

20、末端的反转型迭代子，引用容器最后一个元素。实际上这是该容器前后容器最后一个元素。实际上这是该容器前后反转之后的反转之后的begin()获得指向被控序列开始处的反转型迭代子，引获得指向被控序列开始处的反转型迭代子，引用容器第一个元素的前导位置。实际上这是用容器第一个元素的前导位置。实际上这是该容器前后反转之后的该容器前后反转之后的end()从容器中清除一个或几个元素从容器中清除一个或几个元素从容器中清除所有元素从容器中清除所有元素begin()end()rbegin()rend()erase()clear()说明说明只在第一类容器中的只在第一类容器中的函数函数 vector 容器要求其元素必须有

21、可赋值和可容器要求其元素必须有可赋值和可拷贝属性。拷贝属性。1. 大小和容量大小和容量2. 操作函数操作函数3. 作为普通数组使用作为普通数组使用4. 异常处理异常处理5. 实例分析实例分析(见源代码见源代码)9.3.5 Vector 迭代器是一个可以遍历迭代器是一个可以遍历STL容器内全部或容器内全部或部分元素的对象。部分元素的对象。 支持支持* 、+、=、！、！= 、-、=操作符。操作符。 见示例见示例9.3.6 迭代器 STL提供了一些标准算法，包括搜寻、排提供了一些标准算法，包括搜寻、排序、拷贝、重新排序、修改、数值运算等十分序、拷贝、重新排序、修改、数值运算等十分基本而普遍的算法。基

22、本而普遍的算法。 算法并非容器类型的成员函数，而是一种算法并非容器类型的成员函数，而是一种搭配迭代器使用的全局函数。搭配迭代器使用的全局函数。 见示例。见示例。 9.3.7 算法算法分类n变化序列算法ncopy ,remove,fill,replace,random_shuffle,swap, 会改变容器n非变化序列算法：nadjacent-find, equal, mismatch,find ,count, search, count_if, for_each, search_nn以上函数模板都在 中定义n此外还有其他算法，比如中的算法算法示例：find()templateInIt find

23、(InIt first, InIt last, const find(InIt first, InIt last, const T& val);T& val); nfirst 和 last 这两个参数都是容器的迭代器，它们给出了容器中的查找区间起点和终点。n这个区间是个左闭右开的区间，即区间的起点是位于查找范围之中的，而终点不是算法示例：find()nval参数是要查找的元素的值n函数返回值是一个迭代器。如果找到，则该迭代器指向被找到的元素。如果找不到，则该迭代器指向查找区间终点。#include #include #include using namespace std;ma

24、in() int array10 = 10,20,30,40;vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector:iterator p;p = find(v.begin(),v.end(),3);if( p != v.end()cout * p endl;p = find(v.begin(),v.end(),9);if( p = v.end()cout not found endl;p = find(v.begin()+1,v.end()-2,1);if( p != v.end()cout *

25、p endl;int * pp = find( array,array+4,20);cout * pp endl;输出：3not found320 帮助程序员防止帮助程序员防止“被异常抛出时发生资源被异常抛出时发生资源泄露泄露”。void f() ClassA* ptr = new ClassA(); try . catch (.) throw; delete ptr; 9.3.8 智能指针有错误？正确为正确为void f() ClassA* ptr = new ClassA; try . catch (.) delete ptr; throw; delete ptr; 9.3.8 智能指针使

26、用智能指针使用智能指针#include void f()std:auto_ptr ptr(new ClassA);. 9.3.8 智能指针智能指针的使用方法智能指针的使用方法std:auto_ptr ptr1(new ClassA); /OKstd:auto_ptr ptr2 = new ClassA; /ERROR9.3.8 智能指针 可以当着是一种特殊的可以当着是一种特殊的vector容器。容器。9.3.9 string(字符串)使用使用STL技术修改技术修改main()函数中的代码，函数中的代码，使之成为异常安全的使之成为异常安全的Class Derivedpublic:void OnO

27、pen()/这里可能抛出异常这里可能抛出异常9.3.10 一道关于STL的面试题int main()Derived *pBase = NULL;pBase = new Derived();if (pBase != NULL)pBase- OnOpen();delete pBase;return 0;9.3.10 一道关于STL的面试题解决方法解决方法std:auto_ptr pBase(new Derived(); pBase-OnOpen(); 9.3.10 一道关于STL的面试题 STL仅仅是一个标准，有很多公司实现了这个标准，各具特点。 STLport 是一个跨平台可移植版本 ，应用比较

28、广泛。 / 9.3.11 STL选择 C+C+标准程序库自修教程与参考手标准程序库自修教程与参考手册册 泛型编程与泛型编程与STLSTL STL STL 源码剖析源码剖析 Effective STL Effective STL （STLSTL高效编程高效编程 ） C+ C+ 设计新思维设计新思维 9.3.12 C+泛型书籍推荐1. JDK1.4 1. JDK1.4 和和JDK1.5JDK1.5部分函数比较部分函数比较n 类类ArrayListArrayListn 接口接口Comparable Comparable 9.4 JAVA中的泛型2. 2. 泛型方法和泛型类的声明泛型方法和泛型类的声明public class Pair public class Pair . . . public T getMiddle(T a) 9.4 JAVA中的泛型3. 3. 类型变量的限定类型变量的限定 有时候类和方法需要类型变量进有时候类和方法需要类型变量进行一定的限制。行一定的限制。 例如：例如：9.4 JAVA中的泛型class ArrayAlg public static T min(T a) if (a = null | a.length = 0) return null; T smallest = a0; for (int i =