《C++STL泛型编程1(长望班课件20140525) (1)》由会员分享，可在线阅读，更多相关《C++STL泛型编程1(长望班课件20140525) (1)（102页珍藏版）》请在金锄头文库上搜索。
1、1,C+STL泛型编程 （Generic Programming）,南京信息工程大学计算机与软件学院,长望程序设计竞赛班,2,为什么要采用泛型编程？,ACM竞赛中,需要用到数组、链表、字符串、栈、队列、平衡二叉树等数据结构，以及排序、搜索等算法； 若全部自行编写比较麻烦； ANSI C+中包含了C+ STL (Standard Template Library , 标准模板库,又称C+泛型库)，定义了常用的数据结构和算法，使用十分方便。 有了STL，不必再从头写大多的标准数据结构和算法，并且可获得非常高的性能。,但这不意味着我们不需要掌握基本数据结构与算法;相反,只有透彻理解了,才能更好的使用
2、泛型!,泛型程序设计,由Alexander Stepanov和David Musser创立，于1998年被添加进C+标准. 含义：编写不依赖于具体数据类型的程序. 目标：将程序写得尽可能通用 . 将算法从特定的数据结构中抽象出来，成为通用的. C+的模板为泛型程序设计奠定了关键的基础. STL (标准模板库, Standard Template Library)是泛型程序设计的一个范例.,代码重用(reuse)!,函数模板简介,4,【引例】交换2个整数和交换2个浮点数的C+程序:,/交换2个整数 void Swap(int ,int main() int a = 10, b=20; float
3、 c = 1.2, d=2.4; cout a= a b= b; cout c= c d= c; Swap(a,b); cout a= a b= b; Swap(c,d); cout c= c d= b ? a : b ; int main ( ) cout Max ( 3 , 5 ) is Max ( 3 , 5 ) endl ; cout Max ( y , e ) is Max ( y , e ) endl ; cout Max ( 9.3 , 0.5 ) is Max ( 9.3 , 0.5 ) b ? a : b ; ,double Max ( double a , double b
4、 ) return a b ? a : b ; ,编译器生成的 模板函数,函数模板实例化,函数模板的原理分析： 函数模板中声明了类型参数T，表示了一种抽象类型. 编译器检测到程序调用函数模板Max时，用其第一个实参类型替换掉模板中的T，同时建立一个完整的函数Max，并编译该新建的函数. 本例中，针对三种数据类型，生成了三种函数.,【练习1】编写一个对具有n个元素的数组a 求最小值的程序，要求将求最小值的函数设计成函数模板。,#include using namespace std; template T MinArray(T a,int n) int i; T mina=a0; for( i
5、= 1;i ai) mina=ai; return mina; ,int main() int arr1=1,3,0,2,7,6,4,5,2; double arr2=1.2,-3.4,6.8,9,8; coutarr1数组的最小值为： MinArray(arr1,9) endl; coutarr2数组的最小值为： MinArray(arr2,4) b ? a : b ; int main ( ) int a=3; float b=1.5; cout Max (a,b) is Max(a,b) endl ; return 0; ,错误！模板类型不能提供 类型的隐式转换,注意点2：在函数模板中允
6、许使用多个类型参数。在template定义部分的每个模板形参前必须有关键字class或typename.,#include using namespace std; template void myfunc(T1 x , T2 y) coutx, yy)? x : y;,8,模板优缺点,优点: 函数模板方法克服了C语言用大量不同函数名表示相似功能的弊端; 克服了宏定义不能进行参数类型检查的弊端; 克服了C+函数重载用相同函数名字重写几个函数的繁琐. 缺点: 调试比较困难. 一般先写一个特殊版本的函数 运行正确后，改成模板函数,16,17,【练习2】编写一个函数模板，它返回两个值中的较小者，同时
7、要求能正确处理字符串。 分析： 由于C+字符串比较的方法与字符型、数值型都不同，因此函数模板不适用于字符串比较； 这里设计一个函数模板template T min(T a,T b)，可以处理int、float和char 等数据类型； 为了能正确处理字符串，添加一个重载函数专门处理字符串比较，即char *min(char *a,char *b)。,#include #include template T min(T a,T b) return (ab?a:b); char *min(char *a,char *b) return (strcmp(a,b)0?a:b); void main()
8、double a=3.14, b=8.28; char s1=Bad,s2=Good; cout输出结果:endl; coutmin(a,b)endl; coutmin(s1,s2)endl; ,函数模板,函数重载,C+ STL,一、STL概述,STL是一个具有工业强度的，高效的C+程序库 包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法 STL主要包含了容器、算法、迭代器 库（library）是一系列程序组件的集合，它们可以在不同的程序中重复使用。,21,【引例】阅读以下程序:,#include #include using namespace std; int main() ve
9、ctor v; int i; for (i=0;i:iterator it=v.begin();it!=v.end();it+) cout*it,; cout=, = , != empty() : 判断容器中是否为空 max_size(): 容器中最多能装多少元素 size(): 容器中元素个数 s1.swap(s2)：交换两个容器的内容 构造函数、拷贝构造函数、析构函数,34,容器的共有成员函数(续),所有顺序容器和关联容器 共有的成员函数： begin()：返回指向容器中第一个元素的迭代器 end()：返回指向容器中最后一个元素后面的位置的迭代器 rbegin(): 返回指向容器中最后一个
10、元素的迭代器 rend(): 返回指向容器中第一个元素前面的位置的迭代器 erase(): 从容器中删除一个或几个元素 clear()： 清空容器,35,所有容器都具有的成员函数,顺序和关联容器共同支持的成员函数,【例1】创建两个整型向量容器，分别从尾端增加一些值，输出两个容器的元素数、两个容器的比较结果，交换两个容器后再输出一次。,38,#include #include using namespace std; int main() vector v1,v2; v1.push_back (5); v1.push_back (1); v2.push_back (1); v2.push_bac
11、k (2); v2.push_back (3); cout v2v2endl; return 0; ,声明2个向量,向量赋值,求元素数,向量内容比较,交换2个向量,1、vector向量容器,实际上就是动态数组。但它比数组更灵活，当添加数据时，vector的大小能够自动增加以容纳新的元素。 内存自动管理。可动态调整所占内存。 支持随机访问，随机访问时间为常数。 所有STL算法都能对vector操作。 在尾部添加速度很快，在中间插入慢。,39,(1) 创建vector对象,四种方式: 不指定容器的元素个数： vector 对象名； 例如： vector v; /创建整型向量v 指定容器大小： ve
12、ctor 对象名(n)； 例如： vector v(10); /创建整型向量v,10个元素 注意：元素下标09,初始化为0. 指定容器大小和元素初始值： vector 对象名(n,初值)； 例如： vector v(10,1); /创建整型向量v,10个元素,每个元素值均为1 由已有向量容器创建: vector 对象名(已有对象名)； 例如： vector v2(v1); /创建整型向量v1的副本v2,40,拷贝构造函数,创建vector向量,#include #include using namespace std; int main() vector v(10,1); for (vecto
13、r:iterator it=v.begin();it!=v.end();it+) cout*it,; coutendl; return 0; ,【例2】创建一个整型向量容器，输出全部元素值。,42,(2) 下标方式访问vector元素,可用“ ”运算符访问vector的元素；,【例3】用“ ”运算符为整型向量容器元素赋值，输出全部元素值。,#include #include using namespace std; int main() vector v(3); v0=10; v1=100;v2=-20; for (int i=0;i3;i+) coutvi,; coutendl; retur
14、n 0; ,43,vector(向量) 下标访问元素,注意： 下标操作仅能对确知已存的元素进行赋值和读取操作,vector ivec; /empty vector for( int ix=0; ix 100; +ix) ivecix = ix; /ivec has no element ,出错，向量中尚没有元素，不能访问！,(3) 用迭代器访问vector元素,如何使相同的算法能用于不同的数据结构? - 迭代器(算法与容器的”中间人”),45,容器类迭代器定义方法： 容器类名:iterator 变量名; 访问一个迭代器指向的元素： * 迭代器变量名 迭代器上可执行”+” , 指向容器中的下一个
15、元素。 如果迭代器到达了容器中的最后一个元素的后面，则迭代器变成past-the-end值。 使用一个past-the-end值的迭代器来访问对象是非法的,定义迭代器的关键字,46,对照理解,vector:iterator xHere = x.Begin(); vector:iterator xEnd = x.End(); for (; xHere != xEnd; xHere+) func_name( *xHere);,for (int i = 0; i x.Size(); i+) func_name(x.Get(i);,【例4】 #include #include using namespace st
