C++模板Template的使用详解

　　Template 的基本观念

　　是#define 的延伸, 但比#define 安全, 不必担心传入有副作用的参数.

　　适用于演算法固定, 与数据型别无关的场合. function template 范例: swap, bsearch, sort, ... class template 范例("containers"): stack, queue, BST, heap, ...

　　缺点: 因为重复产生程序码, 因此大幅度增加编译时间及可执行档的大小.

　　语法: 以保留字"template" 开头, 以角括弧表示参数列

　　Function Template

　　例:

template   
 
　　void swap(T & x, T & y)  
 
　　{  
 
　　T temp;  
 
　　temp = x;  
 
　　x = y;  
 
　　y = temp;  
 
　　}  

　　之后即可直接使用:

int a, b;  
 
　　char * p, * q;  
 
　　double x, y;  
 
　　...  
 
　　swap(a, b);  
 
　　swap(p, q);  
 
　　swap(x, y);  

　　

　　注意: swap只是一个函数的样版,不是一个函数;应该把函数样版后面的< ... >视为完整函数名称的一部分. (其实如果从函数的实际参数就可以判断出template的参数,那么template的实际参数可以省略.)

　　specialization: 一般化的template 函数无法满足特殊需要时, 可单独定义特殊的函数, 将适时取代template. 例如字串拷贝.

　　Class Template:请参考 heap3.cc

　　例: template class stack { ... };

　　使用方式:

　　stack a;

　　stack b;

　　stack c;

　　如果把member function的定义写到class定义外,则T top() const { return data[1]; }将变成(深呼吸...): template T heap::top() const { return s[top]; }

　　分析:样版声明函数传回值类别的成员函数() ...

　　template可以复合使用,例如将一个变量声明成由"名称-属性对照表"所构成的堆叠: stack> symbol_table;

　　再谈Container

　　其实Container分为两大类:先前介绍的vector, list, dequeue, heap等等叫做Sequence containers;另一大类叫做 Associative containers :例如字典dictionary (或称map)的观念,方便用户以key查询value的数据结构,可以应用于symbol table, database, ...等等地方.

　　不论是那种container, 都适合声明成为样版, 因为它们都是拿来装其他数据结构用的. 在数据结构课程当中所学的大概都是container.

　　Associative Container

　　请参考dictionary.cc程序范例,与Standard Template Library里面的map 使用范例 .编译: g++ -Wall stl_test.cc。一篇很棒的STL讲义

　　最简单的字典: 以正整数为key 的字典即退化为一般??的数组.

　　Dictionary/Map 提供的基本功能:

　　新增: 输入key, value. 应检查key 是否与既有数据重复.

　　删除: 输入key. 应检查是否有既有数据符合key.

　　修改: 输入key. 应检查是否有既有数据符合key.

　　查询: 输入key. 程序接口应考虑找不到的状况.

　　实作方式: unsorted array, sorted array, unsorted linked list, sorted linked list, BST, Balanced BST, ...

　　Q:试比较各个功能(operation)在各种实作方式下所花的时间.

　　范例程序的bug: 字串是否相等的比较不应该用== 或!= 而应该用strcmp. Q: 但是为什么执行起来没有问题呢?

　　作业:

　　在dictionary.cc 中加入copy constructor 与assignment operator.

　　试以其他数据结构实作dictionary.

　　增加modify 功能.

　　完全修改接口, 使用operator [] 把增、改、查的功能合而为一. 新的接口要能满足上述基本功能的需求. (原程序不行)

　　写一个程序, 读入姓名、学号、四项成绩, 建立两个dictionaries, 一个可用以根据姓名(char const *) 查询整笔记录; 另一个可用以根据学号(char const *) 查询整笔记录.注意"个人数据" 本身就可以当做一个class.

　　其他

　　注意: template 的声明和定义都放在.h 档里.

　　template的参数可以不只一个,也可以不是class.例: template void copy(S a[], T b[], int n) ...例: template class Tree { ... };

　　如何理解template复杂的语法? 把template名称连同template的实际参数视为一个完整单独的单位 (即函数名称或类别名称),例如: swap与stack

　　注意定义template class, template function, template member 语法之不同: 前二者在template < ... > 之后即已进入template 的scope, 所以类别或函数名称后面可以不写< ... > (写了也没有错); 但是定义template member 时compiler 无法自动判断template 的参数究竟是要给类别用, 还是要给成员用, 所以类别名称必须完整写出(即必须加上< ... >). 之后的部分已进入类别的势力范围, 故??可把整个类别名称省略掉.