C++第九章函数模板.ppt

《C++第九章函数模板.ppt》由会员分享，可在线阅读，更多相关《C++第九章函数模板.ppt（89页珍藏版）》请在装配图网上搜索。

1、C+语言程序设计 清华大学 郑莉 1 本章主要内容 模板 群体类 群体数据的组织 深度探索 C+语言程序设计 清华大学 郑莉 2 第一部分： 模板 函数模板 类模板 C+语言程序设计 清华大学 郑莉 3 函数模板 函数模板可以用来创建一个通用功能的函数，以 支持多种不同形参，进一步简化重载函数的函数 体设计。 定义方法 ： template 函数定义 模板 参数表的内容 类型参数： class（或 typename） 标识符 常量参数：类型说明符 标识符 模板参数： template class 标识符 函 数 模 板 C+语言程序设计 清华大学 郑莉 4 求绝对值函数的模板 #include

2、 using namespace std; template T abs(T x) return x 0? -x : x; int main() int n = -5; double d = -5.5; cout abs(n) endl; cout abs(d) endl; return 0; 函 数 模 板 运行结果： 5 5.5 C+语言程序设计 清华大学 郑莉 5 求绝对值函数的模板分析 编译器从调用 abs()时实参的类型，推 导出函数模板的类型参数。例如，对 于调用表达式 abs(n)，由于实参 n为 int型，所以推导出模板中类型参数 T 为 int。 当类型参数的含义确定后，编译

3、器将 以函数模板为样板，生成一个函数： int abs(int x) return x 0 ? x : x; 函 数 模 板 C+语言程序设计 清华大学 郑莉 6 类模板的作用 使用类模板使用户可以为类声明一 种模式，使得类中的某些数据成员、 某些成员函数的参数、某些成员函数 的返回值，能取任意类型（包括基本 类型的和用户自定义类型）。 类 模 板 C+语言程序设计 清华大学 郑莉 7 类模板的声明 类模板： template class 类名 类成员声明 如果需要在类模板以外定义其成员 函数，则要采用以下的形式： template 类型名 类名 :函 数名（参数表） 类 模 板 C+语言程序

4、设计 清华大学 郑莉 8 例 9-2 类模板应用举例 #include #include using namespace std; / 结构体 Student struct Student int id; /学号 float gpa; /平均分 ; 类 模 板 template class Store /类模板：实现对任意类型数据进行存取 private: T item; / item用于存放任意类型的数据 bool haveValue; / haveValue标记 item是否已被 存入内容 public: Store(); / 缺省形式（无形参）的构造函数 T /提取数据函数 void p

5、utElem(const T /存入数据函数 ; /以下实现各成员函数。 template /缺省构造函数的实现 Store:Store(): haveValue(false) 9 template /提取数据函数的实现 T exit(1); /使程序完全退出，返回到操作系统。 return item; / 返回 item中存放的数据 template /存入数据函数的实现 void Store:putElem(const T item = x; / 将 x值存入 item 10 int main() Store s1, s2; s1.putElem(3); s2.putElem(-7); c

6、out s1.getElem() s2.getElem() endl; Student g = 1000, 23 ; Store s3; s3.putElem(g); cout The student id is s3.getElem().id endl; Store d; cout Retrieving object D. ; cout d.getElem() endl /由于 d未经初始化 ,在执行函数 D.getElement()过程中导致程序终 止 return 0; 11 C+语言程序设计 清华大学 郑莉 12 第二部分： 群 体数据 线性群体 线性群体的概念 直接访问群体 -数组类

7、 顺序访问群体 -链表类 栈类 队列类 C+语言程序设计 清华大学 郑莉 13 群体的概念 群体 是指由多个数据元素组成的集 合体。群体可以分为两个大类： 线性群 体 和 非线性群体 。 线性群体中的元素按位置排列有序， 可以区分为第一个元素、第二个元素等。 非线性群体不用位置顺序来标识元 素。 C+语言程序设计 清华大学 郑莉 14 线性群体的概念 线性群体中的元素次序与其位置关 系是对应的。在线性群体中，又可按照 访问元素的不同方法分为 直接访问 、 顺 序访问 和 索引访问 。 在本章我们只介绍直接访问和顺序 访问。 第一个元素 第二个元素 第三个元素 最后一个元素 C+语言程序设计 清

8、华大学 郑莉 15 数组 静态数组是具有固定元素个数的群体，其 中的元素可以通过下标直接访问。 缺点：大小在编译时就已经确定，在运 行时无法修改。 动态数组由一系列位置连续的，任意数量 相同类型的元素组成。 优点：其元素个数可在程序运行时改变。 vector就是用类模板实现的动态数组。 动态数组类模板：例 9-3（ Array.h） 直 接 访 问 的 线 性 群 体 #ifndef ARRAY_H #define ARRAY_H #include template /数组类模板定义 class Array private: T* list;/用于存放动态分配的数组内存首地址 int size

9、; /数组大小（元素个数） public: Array(int sz = 50); /构造函数 Array(const Array /拷贝构造函数 Array(); /析构函数 Array /重载 =“ T /重载 ” const T operator T * (); /重载到 T*类型的转换 operator const T * () const; int getSize() const; /取数组的大小 void resize(int sz); /修改数组的大小 ; 16 动态数组类模板程序 C+语言程序设计 清华大学 郑莉 17 数组类模板模板的构造函数 / 构造函数 template

10、Array:Array(int sz) /sz为数组大小（元素个数），应当非负 assert(sz = 0); / 将元素个数赋值给变量 size size = sz; /动态分配 size个 T类型的元素空间 list = new T size; 直 接 访 问 的 线 性 群 体 C+语言程序设计 清华大学 郑莉 18 数组 类模板的 拷贝构造函数 /拷贝构造函数 template Array:Array(const Array /为对象申请内存并进行出错检查 list = new Tsize;/ 动态分配 n个 T类型的元素空间 /从对象 X复制数组元素到本对象 for (int i =

11、 0; i size; i+) listi = a.listi; 直 接 访 问 的 线 性 群 体 C+语言程序设计 清华大学 郑莉 19 浅拷贝 list size a a的数组元素 占用的内存 拷贝前 list size a a的数组元素 占用的内存 拷贝后 list size b int main() Array a(10); . Array b(a); . template Array:Array( const Array list = x.list; C+语言程序设计 清华大学 郑莉 20 深拷贝 list size a a的数组元素 占用的内存 拷贝前 list size a a

12、的数组元素 占用的内存 拷贝后 list size b b的数组元素 占用的内存 C+语言程序设计 清华大学 郑莉 21 数组 类 模板 的 重载 =运算符函数 /重载 “=” 运算符 template Array /删除数组原有内存 size = rhs.size; /设置 本对象的数组大小 list = new Tsize; /重新分配 n个元素的内存 /从对象 X复制数组元素到本对象 for (int i = 0; i size; i+) listi = rhs.listi; return *this; /返回当前对象的引用 直 接 访 问 的 线 性 群 体 C+语言程序设计 清华大学

13、 郑莉 22 数组 类模板的 重载下标操作符函数 template T /越界检查 return listn; /返回下标为 n的数组元素 template const T /越界检查 return listn; /返回下标为 n的数组元素 直 接 访 问 的 线 性 群 体 C+语言程序设计 清华大学 郑莉 23 为什么有的函数返回引用 如果一个函数的返回值是一个对象的 值，就不应成为左值。 如果返回值为引用。由于引用是对象 的别名，通过引用当然可以改变对象 的值。 直 接 访 问 的 线 性 群 体 C+语言程序设计 清华大学 郑莉 24 重载指针转换操作符 template Array:

14、operator T * () return list; /返回私有数组的首地址 template Array:operator const T * () const return list; /返回私有数组的首地址 直 接 访 问 的 线 性 群 体 C+语言程序设计 清华大学 郑莉 25 指针转换运算符的作用 #include using namespace std; void read(int *p, int n) for (int i = 0; i pi; int main() int a10; read(a, 10); return 0; #include Array.h #incl

15、ude using namespace std; void read(int *p, int n) for (int i = 0; i pi; int main() Array a(10); read(a, 10); return 0; 直 接 访 问 的 线 性 群 体 C+语言程序设计 清华大学 郑莉 26 Array类的应用 例 9-4求范围 2N中的质数， N在程序 运行时由键盘输入。 直 接 访 问 的 线 性 群 体 #include #include #include Array.h using namespace std; int main() Array a(10); / 用

16、来存放质数的数组，初始状态有 10个元素。 int n, count = 0; cout = 2 as upper limit for prime numbers: ; cin n; for (int i = 2; i = n; i+) bool isPrime = true; for (int j = 0; j count; j+) if (i % aj = 0) /若 i被 aj整除，说明 i不是质数 isPrime = false; break; if (isPrime) if (count = a.getSize() a.resize(count * 2); acount+ = i;

17、for (int i = 0; i count; i+) cout setw(8) ai; cout endl; return 0; 27 C+语言程序设计 清华大学 郑莉 28 链表 链表是一种动态数据结构，可以用来 表示顺序访问的线性群体。 链表是由系列 结点 组成的，结点可以 在运行时动态生成。 每一个结点包括 数据域 和指向链表中 下一个结点的 指针 （即下一个结点的 地址）。如果链表每个结点中只有一 个指向后继结点的指针，则该链表称 为单链表。 顺 序 访 问 的 线 性 群 体 C+语言程序设计 清华大学 郑莉 29 单链表 data1 data2 data3 datan NULL

18、 head rear 顺 序 访 问 的 线 性 群 体 C+语言程序设计 清华大学 郑莉 30 单链表的结点类模板 template class Node private: Node *next; public: T data; Node(const T void insertAfter(Node *p); Node *deleteAfter(); Node *nextNode() const; ; 顺 序 访 问 的 线 性 群 体 C+语言程序设计 清华大学 郑莉 31 在结点之后插入一个结点 data1 data2 p data template void Node:insertAft

19、er(Node *p) /p节点指针域指向当前节点的后继节点 p-next = next; next = p; /当前节点的指针域指向 p 顺 序 访 问 的 线 性 群 体 C+语言程序设计 清华大学 郑莉 32 删除结点之后的结点 顺 序 访 问 的 线 性 群 体 data1 data2 data3 Node *Node:deleteAfter(void) Node *tempPtr = next; if (next = 0) return 0; next = tempPtr-next; return tempPtr; tempPtr C+语言程序设计 清华大学 郑莉 33 链表的基本操

20、作 生成结点 插入结点 查找结点 删除结点 遍历链表 清空链表 顺 序 访 问 的 线 性 群 体 C+语言程序设计 清华大学 郑莉 34 链表类模板 (例 9-6) 顺 序 访 问 的 线 性 群 体 #ifndef LINKEDLIST_H #define LINKEDLIST_H #include Node.h template class LinkedList private: /数据成员： Node *front, *rear Node *prevPtr, *currPtr; int size; int position; Node *newNode(const T void fre

21、eNode(Node *p); void copy(const LinkedList public: LinkedList(); LinkedList(const LinkedList LinkedList(); LinkedList int getSize() const; bool isEmpty() const; void reset(int pos = 0 void next(); bool endOfList() const; int currentPosition(void) const; void insertFront(const T void insertRear(const

22、 T void insertAt(const T void insertAfter(const T T deleteFront(); void deleteCurrent(); T const T ; #endif /LINKEDLIST_H C+语言程序设计 清华大学 郑莉 35 链表类应用举例 (例 9-7) 顺 序 访 问 的 线 性 群 体 /9_7.cpp #include #include LinkedList.h using namespace std; int main() LinkedList list; for (int i = 0; i item; list.insert

23、Front(item); cout List: ; list.reset(); while (!list.endOfList() cout list.data() ; list.next(); cout endl; int key; cout key; list.reset(); while (!list.endOfList() if (list.data() = key) list.deleteCurrent(); list.next(); cout List: ; list.reset(); while (!list.endOfList() cout list.data() ; list.

24、next cout endl; return 0; C+语言程序设计 清华大学 郑莉 36 特殊的线性群体 栈 栈是只能从一端访问的线性群体， 可以访问的这一端称栈顶，另一端称栈 底。 an a2 a1 入栈 出栈 栈顶 栈底 特 殊 的 线 性 群 体 栈 C+语言程序设计 清华大学 郑莉 37 栈的应用举例 表达式处理 b a / a/b+c*d (a) t1 + a/b+c*d t1=a/b (b) d c t1 * + a/b+c*d (c) t3 a/b+c*d t3=t1+t2 (e) t2 t1 + a/b+c*d t2=c*d (d) 特 殊 的 线 性 群 体 栈 C+语言程

25、序设计 清华大学 郑莉 38 栈的基本状态 栈空 栈中没有元素 栈满 栈中元素个数达到上限 一般状态 栈中有元素，但未达到栈满状态 特 殊 的 线 性 群 体 栈 栈顶 an a1 a0 入栈 出栈 数组下标 max n 1 0 一般状态 栈顶 入栈 出栈 数组下标 初始状态（栈空） max n 1 0 栈顶 amax an a1 a0 入栈 出栈 数组下标 max n 1 0 栈满状态 39 C+语言程序设计 清华大学 郑莉 40 栈的基本操作 初始化 入栈 出栈 清空栈 访问栈顶元素 检测栈的状态（满、空） 特 殊 的 线 性 群 体 栈 C+语言程序设计 清华大学 郑莉 41 栈类模板

26、(例 9-8) 特 殊 的 线 性 群 体 栈 /Stack.h #ifndef STACK_H #define STACK_H #include template class Stack private: T listSIZE; int top; public: Stack(); void push(const T T pop(); void clear(); const T bool isEmpty() const; bool isFull() const; ; /类的实现略 C+语言程序设计 清华大学 郑莉 42 栈的应用 例 9.9 一个简单的整数计算器 实现一个简单的整数计算器，能够

27、进行加、 减、乘、除和乘方运算。使用时算式采用后缀 输入法，每个操作数、操作符之间都以空白符 分隔。例如，若要计算 3+5则输入 3 5 +。 乘方运算符用 表示。每次运算在前次结果 基础上进行，若要将前次运算结果清除，可键 入 c。当键入 q时程序结束。 Calculator.h Calculator.cpp 9_9.cpp 特 殊 的 线 性 群 体 栈 /Calculator.h #ifndef CALCULATOR_H #define CALCULATOR_H #include Stack.h / 包含栈类模板定义文件 class Calculator /计算器类 private: S

28、tack s; / 操作数栈 void enter(double num); /将操作数 num压入栈 /连续将两个操作数弹出栈，放在 opnd1和 opnd2中 bool getTwoOperands(double void compute(char op); /执行由操作符 op指定的运算 public: void run(); /运行计算器程序 void clear(); /清空操作数栈 ; #endif /CALCULATOR_H 43 /Calculator.cpp #include Calculator.h #include #include #include using name

29、space std; /工具函数，用于将字符串转换为实数 inline double stringToDouble(const string /字符串输入流 double result; stream result; return result; void Calculator:enter(double num) /将操作数 num压入栈 s.push(num); 44 bool Calculator:getTwoOperands(double return false; opnd1 = s.pop(); /将右操作数弹出栈 if (s.isEmpty() /检查栈是否空 cerr Missi

30、ng operand! endl; return false; opnd2 = s.pop(); /将左操作数弹出栈 return true; 45 void Calculator:compute(char op) /执行运算 double operand1, operand2; bool result = getTwoOperands(operand1, operand2); if (result) /如果成功，执行运算并将运算结果压入栈 switch(op) case +: s.push(operand2 + operand1); break; case -: s.push(operand

31、2 - operand1); break; case *: s.push(operand2 * operand1); break; case /: if (operand1 = 0) /检查除数是否为 0 cerr Divided by 0! endl; s.clear(); /除数为 0时清空栈 else s.push(operand2 / operand1); break; case : s.push(pow(operand2, operand1); break; default: cerr Unrecognized operator! endl; break; cout = s.peek

32、() str, str != q) switch(str0) case c: s.clear(); break; case -: /遇 -需判断是减号还是负号 if (str.size() 1) enter(stringToDouble(str); else compute(str0); break; case +:/遇到其它操作符时 case *: case /: case : compute(str0); default: /若读入的是操作数，转换为整型后压入栈 enter(stringToDouble(str); break; void Calculator:clear() /清空操作数

33、栈 s.clear(); 47 /9_9.cpp #include Calculator.h int main() Calculator c; c.run(); return 0; 48 C+语言程序设计 清华大学 郑莉 49 特殊的线性群体 队列 队列是只能向一端添加元素，从另 一端删除元素的线性群体 a1 a2 an-1 an 队头 队尾 入队 出队 a0 C+语言程序设计 清华大学 郑莉 50 队列的基本状态 队空 队列中没有元素 队满 队列中元素个数达到上限 一般状态 队列中有元素，但未达到队满状态 特 殊 的 线 性 群 体 队 列 a0 a1 an-1 an 队头 队尾 入队 出队

34、 数组下标 0 1 n-1 n max (一般状态 ) 队头 队尾 入队 出队 数组下标 0 1 n-1 n max (队空状态 ) a0 a1 an-1 an amax 队头 队尾 入队 出队 数组下标 0 1 n-1 n max (队满状态 ) 元素移动方向 元素移动方向 51 C+语言程序设计 清华大学 郑莉 52 循环队列 在想象中将数组弯曲成环形，元素 出队时，后继元素不移动，每当队尾达 到数组最后一个元素时，便再回到数组 开头。 特 殊 的 线 性 群 体 队 列 1 2 3 4 m-1 m-2 m-3 0 am am+1 am+2 a3 队头 队尾 a4 am-2 am-3 am

35、-1 队满状态 元素个数 =m 1 2 3 4 m-1 m-2 m-3 0 队尾 队头 队空状态 元素个数 =0 队尾 1 2 3 4 m-1 m-2 m-3 0 a0 a1 a2 a3 队头 一般状态 53 C+语言程序设计 清华大学 郑莉 54 第三部分： 群 体数据的组织 插入排序 选择排序 交换排序 顺序查找 折半查找 C+语言程序设计 清华大学 郑莉 55 排序（ sorting） 排序 是计算机程序设计中的一种重要操作， 它的功能是将一个 数据元素 的任意序列，重 新排列成一个按 关键字 有序的序列。 数据元素： 数据的基本单位。在计算机中通常作 为一个整体进行考虑。一个数据元素可

36、由若干数 据项组成。 关键字： 数据元素中某个数据项的值，用它可以 标识（识别）一个数据元素。 在排序过程中需要完成两种基本操作： 比较两个数的大小 调整元素在序列中的位置 群 体 数 据 的 组 织 C+语言程序设计 清华大学 郑莉 56 内部排序与外部排序 内部排序： 待排序的数据元素存放在 计算机内存中进行的排序过程。 外部排序： 待排序的数据元素数量很 大，以致内存存中一次不能容纳全部 数据，在排序过程中尚需对外存进行 访问的排序过程。 群 体 数 据 的 组 织 C+语言程序设计 清华大学 郑莉 57 内部排序方法 插入排序 选择排序 交换排序 群 体 数 据 的 组 织 C+语言程

37、序设计 清华大学 郑莉 58 插入排序的基本思想 每一步将一个待排序元素按其关键字值的大小插入到已排 序序列的适当位置上，直到待排序元素插入完为止。 初始状态： 5 4 10 20 12 3 插入操作： 1 4 4 5 10 20 12 3 2 10 4 5 10 20 12 3 3 20 4 5 10 20 12 3 4 12 4 5 10 12 20 3 5 3 3 4 5 10 12 20 C+语言程序设计 清华大学 郑莉 59 直接插入排序 在插入排序过程中，由于寻找插入位置的 方法不同又可以分为不同的插入排序算法， 这里我们只介绍最简单的直接插入排序算 法。 例 9-11 直接插入排

38、序函数模板（ 9_11.h） 群 体 数 据 的 组 织 template void insertionSort(T a, int n) int i, j; T temp; for (int i = 1; i 0 j-; aj = temp; 直接插入排序函数模板（ 9_11.h） 60 C+语言程序设计 清华大学 郑莉 61 选择排序的基本思想 每次从待排序序列中选择一个关键字最小的元素， （当需要按关键字升序排列时），顺序排在已排序序列的 最后，直至全部排完。 5 4 10 20 12 3 初始状态： 3 4 10 20 12 5 3 4 10 20 12 5 第 i 次选择后，将选出的那

39、个记录与第 i 个记录做 交换 。 3 4 5 20 12 10 . . C+语言程序设计 清华大学 郑莉 62 直接选择排序 在选择类排序方法中，从待排序序列 中选择元素的方法不同，又分为不同 的选择排序方法，其中最简单的是通 过顺序比较找出待排序序列中的最小 元素，称为直接选择排序。 例 9-12 直接选择排序函数模板（ 9- 12.h） 群 体 数 据 的 组 织 template void mySwap(T x = y; y = temp; template void selectionSort(T a, int n) for (int i = 0; i n - 1; i+) int

40、leastIndex = i; for (int j = i + 1; j n; j+) if (aj aleastIndex) leastIndex = j; mySwap(ai, aleastIndex ); 直接选择排序函数模板（ 9-12.h） 63 C+语言程序设计 清华大学 郑莉 64 交换排序的基本思想 两两比较待排序序列中的元素，并 交换不满足顺序要求的各对元素，直到 全部满足顺序要求为止。 群 体 数 据 的 组 织 C+语言程序设计 清华大学 郑莉 65 最简单的交换排序方法 起泡排序 对具有 n个元素的序列按升序进行起泡排序的 步骤： 首先将第一个元素与第二个元素进行比较

41、，若为逆 序，则将两元素交换。然后比较第二、第三个元素， 依次类推，直到第 n-1和第 n个元素进行了比较和交 换。此过程称为第一趟起泡排序。经过第一趟，最 大的元素便被交换到第 n个位置。 对前 n-1个元素进行第二趟起泡排序，将其中最大元 素交换到第 n-1个位置。 如此继续，直到某一趟排序未发生任何交换时，排 序完毕。对 n个元素的序列，起泡排序最多需要进 行 n-1趟。 群 体 数 据 的 组 织 C+语言程序设计 清华大学 郑莉 66 起泡排序举例 对整数序列 8 5 2 4 3 按升序排序 8 5 2 4 3 5 2 4 3 8 2 4 3 5 8 2 3 4 5 8 2 3 4

42、5 8 初 始 状态 第 一 趟 结果 第 二 趟 结果 第 三 趟 结果 第 四 趟 结果 小 的 逐 渐 上 升 每 趟 沉 下 一 个 最 大 的 群 体 数 据 的 组 织 C+语言程序设计 清华大学 郑莉 67 例 9-13 起泡排序函数模板 template void mySwap(T x = y; y = temp; template void bubbleSort(T a, int n) int i = n 1; while (i 0) int lastExchangeIndex = 0; for (int j = 0; j i; j+) if (aj + 1 aj) mySw

43、ap(aj, aj + 1); lastExchangeIndex = j; i = lastExchangeIndex; 群 体 数 据 的 组 织 C+语言程序设计 清华大学 郑莉 68 顺序查找 其基本思想 从序列的首元素开始 ， 逐个元素与待查 找的关键字进行比较 ， 直到找到相等的 。 若整个序列中没有与待查找关键字相等 的元素 ， 就是查找不成功 。 顺序查找函数模板 例 9-14 群 体 数 据 的 组 织 template int seqSearch(const T list, int n, const T i n; i+) if (listi = key) return i;

44、 return -1; 顺序查找函数模板 69 C+语言程序设计 清华大学 郑莉 70 折半查找的基本思想 对于已按关键字排序的序列，经过 一次比较，可将序列分割成两部分，然 后只在有可能包含待查元素的一部分中 继续查找，并根据试探结果继续分割， 逐步缩小查找范围，直至找到或找不到 为止。 群 体 数 据 的 组 织 C+语言程序设计 清华大学 郑莉 71 折半查找举例 用折半查找法，在下列序列中查找值为 21的元素： L=1 5 13 19 21 37 56 64 75 80 88 92 H=11 M =INT(L+H)/2)=6 5 13 19 21 37 L=1 H=M-1=5 M=IN

45、T(L+H)/2)=3 M 21 37 H L=M+1=4 L M=INT(L+H)/2)=4 M C+语言程序设计 清华大学 郑莉 72 例 9-15 折半查找函数模板 template int binSearch(const T list, int n, const T int high = n - 1; while (low = high) int mid = (low + high) / 2; if (key = listmid) return mid; else if (key listmid) high = mid 1; else low = mid + 1; return -1;

46、 群 体 数 据 的 组 织 C+语言程序设计 清华大学 郑莉 类模板 vs 类 类模板不能表示具体的数据类型，但类模板的实 例化类是数据类型 例：如要使 reverse函数接收 Array的参数 void reverse(Array 错误 ！ Array是模板，不能当作一个数据类型。 void reverse(Array 正确。 Array是数据类型。 template reverse (Array 正确。 T虽未定，但 Array表示的是一个类模板实例。 同 一模板在不同参数下的实例是完全无关的类型 彼此不兼容，无法相互赋值 通过 Store的对象调用的成员函数，无法直接 访问 Store

47、对象的私有成员 73 深 度 探 索 C+语言程序设计 清华大学 郑莉 函数模板 vs 函数 函数模板本身不是函数 编译器不会为函数模板本身生成目标代码 只有函数模板的实例能被调用 例：考虑下列模板 template void outputArray(const T *array, int count); 若 a是 int数组， outputArray(a, 10)等价于 outputArray(a, 10)，被调用的是 outputArray实例 74 深 度 探 索 C+语言程序设计 清华大学 郑莉 隐含实例化 模板 的实例化 根据 函数模板生成具体的函数、或根据 类模板生成具体的类的 过

48、程 隐含实例化 编译器会自动按需对模板实例化 所有会被使用的模板实例会被生成 对类模板的隐含实例化并不意味着对它 成员函数的定义也进行实例化，当类模 板成员函数会被使用时，才会被实例化 75 深 度 探 索 C+语言程序设计 清华大学 郑莉 多文件结构中模板的组织 模板实例化机制带来的新问题 不能把下面与模板相关的定义放在源文件中 函数模板的定义 类模板成员函数 类模板静态数据成员 解决方法 把与模板相关的定义放在头文件中 最通 常的解决办法 编译器有特殊处理，保证不会有连接冲突 使用 export关键字 编译器支持不好 使用模板的显式实例化机制 76 深 度 探 索 C+语言程序设计 清华大

49、学 郑莉 显式实例化 语法形式 template 实例化目标的声明 ; 作用 一 个模板实例无论是否在本编译单元中被使用，都 会被生成 例 template void outputArray(const int *array, int count); template class Store; 在多文件结构中的用途 使用在程序中可能会被用到的各种参数对模板显式 实例化，使得与模板相关的定义可以放在源文件中 77 深 度 探 索 C+语言程序设计 清华大学 郑莉 为模板定义特殊的实现 为什么要定义特殊的实现？ 模板抓住了算法与数据结构上的共性，但忽 略了类型的个性 设计 出的模板对于具体的数据类

50、型而言未必 具有最好的效率 例： Stack类模板 如果以 bool作为类型参数，则有 7/8的空间 浪费 Stack中的 list数组占 32个字节， 实际上 4个字节就够 78 深 度 探 索 C+语言程序设计 清华大学 郑莉 模板的特化 什么是特化 为一个模板在特定 参数下提供特殊定 义 既适用于类模板， 又适用于函数模板 对 Stack特化的类定义 template class Stack private: unsigned list; int top; public: Stack(); void push(bool item); bool pop(); void clear(); b

51、ool peek() const; bool isEmpty() const; bool isFull() const; ; 79 深 度 探 索 /特化类的部分成员函数定义 void Stack:push(bool item) assert(!isFull(); +top; list = (list 1) | (item ? 1 : 0); bool Stack:pop() assert(!isEmpty(); bool result = (list list = 1; -top; return result; 80 C+语言程序设计 清华大学 郑莉 类模板的偏特化 对 Stack 特化的问

52、题 适用范围过窄， SIZE必须是 32 类模板的偏特化 将一部分参数固定， 而使另一部分参数可 变，设计特殊的定义 只适用于类模板 对 Stack偏特化的类 定义 template class Stack private: enum UNIT_BITS = sizeof(unsigned) * 8, ARRAY_SIZE = (SIZE - 1) / UNIT_BITS + 1 ; unsigned listARRAY_SIZE; int top; public: Stack(); void push(bool item); bool pop(); void clear(); bool pe

53、ek() const; bool isEmpty() const; bool isFull() const; ; 81 深 度 探 索 /偏特化类的部分成员函数定义 template void Stack:push(bool item) assert(!isFull(); int index = +top / UNIT_BITS; listindex = (listindex 1) | (item ? 1 : 0); template bool Stack:pop() assert(!isEmpty(); int index = top- / UNIT_BITS; bool result =

54、(listindex listindex = 1; return result; 82 C+语言程序设计 清华大学 郑莉 类模板的偏特化 偏特化不仅允许将一部分模板参数固定，还 允许将某一个模板参数所能表示的类型范围 缩窄，例 template class X ; 原模板， T可以是所有类型参数 template class X ; 针对指针类型进行偏特化 template class X ; 针对常指针类型进行偏特化 对于 X，后两个偏特化版本皆能匹 配，但由于第二个更为特殊，会被选中 83 深 度 探 索 C+语言程序设计 清华大学 郑莉 函数模板的重载 函数模板不支持偏特 化，但可重载，

55、从而 完成与类模板偏特化 类似的功能 若对函数模板的一次 使用能与多个函数模 板匹配，最特殊的那 个会被选中 例：针对参数为指针 类型的情形，为myMax定义特殊实 现 template T myMax(T a, T b) return (a b) ? a : b; template T *myMax(T *a, T *b) return (*a *b) ? a : b; 84 深 度 探 索 C+语言程序设计 清华大学 郑莉 模板元编程 什么是模板元编程 在模板实例化的同时利用编译器完成一 些计算任务 模板元编程可以把一些通常在运行时 才能计算的任务提前到编译时，从而： 提高程序运行效率 提

56、供一些方便 例：模板元编程的计算结果可以作为静态数 组的大小 85 深 度 探 索 C+语言程序设计 清华大学 郑莉 例：编译时计算 n! template struct Factorial /计算 N的阶乘 enum VALUE = N * Factorial:VALUE ; ; template struct Factorial /设定 N = 0时 N的阶乘 enum VALUE = 1 ; ; 86 深 度 探 索 C+语言程序设计 清华大学 郑莉 Factorial的分析 Factorial的使用 例： int s Factorial:VALUE ; Factorial:VALUE的

57、计算过程 首先试图实例化 Factorial； 要计算 Factorial的 VALUE，需实例化 Factorial，然后是 Factorial 实例化 Factorial时，由于 Factorial:VALUE的值已确定， Factorial的 VALUE值可计算，完成实例化； Factorial到 Factorial的实例化相继完成 87 C+语言程序设计 清华大学 郑莉 88 例：整数次乘方的展开 template struct Power template static T value(T x) return x * Power:value(x); ; template struct Power template static T value(T x) return x; ; template inline T power(T v) return Power:value(v); C+语言程序设计 清华大学 郑莉 89 小结与复习建议 主要内容 模板、群体类和群体数据的组织 达到的目标 理解模板的作用，学会简单的应用。 以群体类以及查找、排序算法为综合例题，对 前面章节的内容进行全面复习； 掌握一些常用的数据结构和算法，能够解决一 些略复杂的问题，也为下一章学习 C+标准模 板库打下基础。 实验任务 实验九