C++STL泛型编程PPT课件

1,C+STL泛型编程 （Generic Programming）,2,为什么要采用泛型编程？,项目中,需要用到数组、链表、字符串、栈、队列、平衡二叉树等数据结构，以及排序、搜索等算法；若全部自行编写比较麻烦；ANSI C+中包含了C+ STL (Standard Template Library , 标准模板库,又称C+泛型库)，定义了常用的数据结构和算法，使用十分方便。有了STL，不必再从头写大多的标准数据结构和算法，并且可获得非常高的性能。,但这不意味着我们不需要掌握基本数据结构与算法;相反,只有透彻理解了,才能更好的使用泛型!,泛型程序设计,由Alexander Stepanov和David Musser创立，于1998年被添加进C+标准.含义：编写不依赖于具体数据类型的程序.目标：将程序写得尽可能通用 .将算法从特定的数据结构中抽象出来，成为通用的.C+的模板为泛型程序设计奠定了关键的基础. STL (标准模板库, Standard Template Library)是泛型程序设计的一个范例.,代码重用(reuse)!,4,函数模板模板函数的重载类模板堆栈类继承static成员友元,模板,函数模板简介,5,【引例】交换2个整数和交换2个浮点数的C+程序:,/交换2个整数void Swap(int ,int main() int a = 10, b=20; float 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 ; ,由实参类型实例化,char Max ( char a , char b ) return a b ? a : b ; ,double Max ( double a , double b ) return a b ? a : b ; ,编译器生成的模板函数,函数模板实例化,运行结果: Max(3,5) is 5Max(y, e) is y Max(9.3, 0.5) is 9.3,函数模板的原理分析： 函数模板中声明了类型参数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 = 1;i ai) mina=ai;return mina;,void 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：在函数模板中允许使用多个类型参数。在template定义部分的每个模板形参前必须有关键字class或typename.,#includeusing namespace std;templatevoid myfunc(T1 x , T2 y) coutx, yy)? x : y;,8,/错误，不允许有别的语句,模板优缺点,优点:函数模板方法克服了C语言用大量不同函数名表示相似功能的弊端;克服了宏定义不能进行参数类型检查的弊端;克服了C+函数重载用相同函数名字重写几个函数的繁琐.缺点: 调试比较困难.一般先写一个特殊版本的函数运行正确后，改成模板函数,17,18,【练习2】编写一个函数模板，它返回两个值中的较小者，同时要求能正确处理字符串。 分析：由于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() double a=3.14, b=8.28; char s1=Bad,s2=Good; cout输出结果:endl; coutmin(a,b)endl; coutmin(s1,s2)endl; ,函数模板,函数重载,运行结果: 3.14Bad,20,可以显式指定（explicitly specify），如：i=max(ia,5);d=max(da,6);,用函数模板求数组元素中最大值template Groap max(const Groap *r_array,int size) int i; Groap max_val=r_array0; for ( i=1; i max_val ) max_val=r_arrayi; return max_val; ,可读性更好。,21,函数模板可以重载, 形参表不同即可 例, 下面两个模板可以同时存在: template void print(T1 arg1, T2 arg2) cout void print(T arg1, T arg2) cout arg1 arg2endl; ,重载,22,例: 函数模板调用顺序,23,double Max(double a, double b) cout MyMax endl; return 0; ,template T Max( T a, T b ) cout Template Max 1 endl; return 0; ,template T Max( T a, T2 b ) cout Template Max 2 endl; return 0; ,24,void main() int i=4, j=5; Max( 1.2, 3.4 ); Max( i, j ); Max(1.2, 3);,25,匹配顺序C+编译器遵循以下优先顺序: Step 1: 先找参数完全匹配的普通函数(非由模板实例化而得的函数) Step 2: 再找参数完全匹配的模板函数 Step 3: 再找实参经过自动类型转换后能够匹配的普通函数 Step 4: 上面的都找不到, 则报错,26,void main() int i=4, j=5; Max( 1.2, 3.4 ); Max( i, j ); Max(1.2, 3);,/调用Max(double, double)函数,/调用第一个T Max(T a, T b)模板生成的函数,/调用第二个T Max(T a, T2 b)模板生成的函数,运行结果: MyMax Template Max 1 Template Max 2,27,可以在函数模板中使用多个类型参数, 可以避免二义性 template T1 myFunction( T1 arg1, T2 arg2) coutarg1“ ”arg2“n”; return arg1; myFunction( 5, 7 ); myFunction( 5.8, 8.4 ); myFunction( 5, 8.4 );,/ok：replace T1 and T2 with int,/ok: replace T1 and T2 with double,/ok: replace T1 with int, T2 with double,28,类模板的定义,C+的类模板的写法如下: template class 类模板名 成员函数和成员变量 ; 类型参数表的写法就是: class 类型参数1, class 类型参数2, ,29,类模板里的成员函数, 如在类模板外面定义时, template 返回值类型 类模板名:成员函数名(参数表) ,类模板的定义,30,用类模板定义对象的写法如下: 类模板名 对象名(构造函数实际参数表); 如果类模板有无参构造函数, 那么也可以只写: 类模板名 对象名;,类模板的定义,31,Pair类模板: template class Pair public: T1 key; /关键字 T2 value; /值 Pair(T1 k,T2 v) : key(k), value(v) ; bool operator ,类模板的定义,32,#include #includeusing namespace std;。void main() Pair stu(Tom, 19); Pair stu2(Jack, 20); if (stu.operator(stu2) ) cout stu.key stu.value;else cout stu.key stu2.value;,运行结果: Jack 20,Pair类模板的使用:,33,使用类模板声明对象 编译器由类模板生成类的过程叫类模板的实例化 编译器自动用具体的数据类型替换类模板中的类型参数, 生成模板类的代码 由类模板实例化得到的类叫模板类 为类型参数指定的数据类型不同, 得到的模板类不同,同一个类模板的两个模板类是不兼容的 Pair * p; Pair a; p = /wrong,34,#include using namespace std; template class A public: template void Func(T2 t) cout a; a.Func(K); ,若函数模板改为 template void Func(T t)coutt 将报错 “declaration of class T shadows template parm class T ”,程序输出: K,/成员函数模板,/成员函数模板 Func被实例化,函数模版作为类模板成员,35,template class Apublic:templatevoid Func(T2 t);templatetemplatevoid A:Func(T2 t) cout t;,void main() A a; a.Func(K); ,36,类模板的参数声明中可以包括非类型参数 template 非类型参数: 用来说明类模板中的属性 类型参数: 用来说明类模板中的属性类型, 成员操作的参数类型和返回值类型,类模板与非类型参数,37,template class CArray T arraysize; public: void Print( ) for(int i = 0; i size; +i) cout array i endl; ;,类模板与非类型参数,CArray a2; CArray a3;,38,CArray a2; CArray a3; 注意: CArray和CArray完全是两个类 这两个类的对象之间不能互相赋值,类模板与非类型参数,39,类模板派生出类模板 模板类 (即类模板中类型/非类型参数实例化后的类)派生出类模板 普通类派生出类模板 模板类派生出普通类,类模板与继承,派生,类模板,类模板,模板类,类模板,类模板,类模板,普通类,模板类,40,类模板从类模板派生,(1) template class A T1 v1; T2 v2; ; template class B : public A T1 v3; T2 v4; ;,template class C : public B T v5; ;,void main() B obj1; C obj2; ,41,void main() B obj1; C obj2; ,class B:public A int v3; double v4; ; class A double v1; int v2; ;,42,类模板从模板类派生,template class A T1 v1; T2 v2; ;template class B:public A T v; ;int main() B obj1; return 0; 自动生成两个模板类：?,43,template class A T1 v1; T2 v2; ; template class B:public A T v; ; int main() B obj1; return 0; 自动生成两个模板类：A和B,(2) 类模板从模板类派生,44,class A int v1; ; template class B : public A T v; ; int main() B obj1; return 0; ,(3) 类模板从普通类派生,45,(4)普通类从模板类派生,template class A T v1; int n; ;class B : public A double v; ;int main() B obj1; return 0; ,46,C+支持两种编译模式包含模式 ( Inclusion Model ) 把所有的定义一起放在头文件中，在调用的CPP中，包含相关的头文件分离模式 ( Separation Model ) (好像VC编译器不支持) / model.h template Type tMin( Type t1, Type t2 ); / model.cpp export template Type tMin( Type t1, Type t2 ); / test.cpp #include “model.h” int i, j; double d = min( i, j );,模板编译模式,47,1. 矩阵运算：矩阵转置与矩阵相乘函数模板。下标作为参数传递。,2.线性表是数据结构中的概念。数组中除第一个元素外，其他元素有且仅有一个直接前驱，第一个元素没有前驱；除最后一个元素外，其他元素有且仅有一个直接后继，最后一个元素无后继。这样的特性称为线性关系。所以称数组元素在一个线性表中。线性表实际包括顺序表（数组）和链表。,对顺序表的典型操作包括：计算表长度，寻找变量或对象x（其类型与表元素相同）在表中的位置（下标值），判断x是否在表中，删除x，将x插入列表中第i个位置，寻找x的后继，寻找x的前驱，判断表是否空，判断表是否满（表满不能再插入数据，否则会溢出，产生不可预知的错误），取第i个元素的值。,作业,48,堆栈类及其模板实现,class CStackpublic: CStack(int capcity = 20); CStack(); void ClearStack(); bool isEmpty(); bool isFull(); int StackLength(); char GetTop(); void Push(char e); void Pop();private: char* elemArray; int top; int capcity;,49,类模板与友员函数,函数、类、类的成员函数作为类模板的友元函数模板作为类模板的友元函数模板作为类的友元类模板作为类模板的友元,50,函数、类、类的成员函数作为类模板的友元,void Func1() class A ;class Bpublic: void Func() ;,template class Tmpl friend void Func1(); friend class A; friend void B:Func();,51,函数、类、类的成员函数作为类模板的友元,int main() Tmpl i; Tmpl f;return 0;,52,函数模板作为类模板的友元,#include #include using namespace std;template class Pairprivate: T1 key; /关键字 T2 value; /值public: Pair(T1 k,T2 v):key(k),value(v) ; bool operator ,53,函数模板作为类模板的友元,templatebool Pair:operator ,54,函数模板作为类模板的友元,int main()Pair student(Tom,29);Pair obj(12,3.14);cout ostream & operator & p)生成的函数，都被判断为Pair摸板类的友元,输出结果：(Tom,29) 12,3.14),55,函数模板作为类的友元,#include using namespace std;class A int v;public: A(int n):v(n) template friend void Print(const T ,template void Print(const T ,56,函数模板作为类的友元,int main() A a(4); Print(a); return 0;,从 template void Print(const T & p)生成的函数，都成为 A 的友元,输出结果：4,void Print(int a) cout a; a.Func (b);return 0;A 类，成了B类的友元。从A模版实例化出来的类，都是B实例化出来的类的友元,类模板作为类模板的友元,/用B替换A模板中的T,输出结果：5,59,类模板与static成员,#include using namespace std;template class A private:static int count;public: A() +count; A() - count; ;A( const A ,60,类模板与static成员,template int A:count = 0;template int A:count = 0;int main() A ia, ib; A da; ia.PrintCount(); ib.PrintCount(); da.PrintCount(); return 0;,输出结果：221,C+ STL,一、STL概述,STL是一个具有工业强度的，高效的C+程序库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法STL主要包含了容器、算法、迭代器库（library）是一系列程序组件的集合，它们可以在不同的程序中重复使用。,63,【引例】阅读以下程序:,#include #include using namespace std;void main() vector 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)：交换两个容器的内容 构造函数、拷贝构造函数、析构函数,76,容器的共有成员函数(续),所有顺序容器和关联容器 共有的成员函数： begin()：返回指向容器中第一个元素的迭代器 end()：返回指向容器中最后一个元素后面的位置的迭代器 rbegin(): 返回指向容器中最后一个元素的迭代器 rend(): 返回指向容器中第一个元素前面的位置的迭代器 erase(): 从容器中删除一个或几个元素 clear()： 清空容器,77,所有容器都具有的成员函数,顺序和关联容器共同支持的成员函数,【例1】创建两个整型向量容器，分别从尾端增加一些值，输出两个容器的元素数、两个容器的比较结果，交换两个容器后再输出一次。,80,#include #include using namespace std;int main() vector v1,v2; v1.push_back (5); v1.push_back (1); v2.push_back (1); v2.push_back (2); v2.push_back (3); cout v2v2endl; return 0;,声明2个向量,向量赋值,求元素数,向量内容比较,交换2个向量,1、vector向量容器,实际上就是动态数组。但它比数组更灵活，当添加数据时，vector的大小能够自动增加以容纳新的元素。内存自动管理。可动态调整所占内存。支持随机访问，随机访问时间为常数。所有STL算法都能对vector操作。在尾部添加速度很快，在中间插入慢。,81,(1) 创建vector对象,四种方式:不指定容器的元素个数：vector 对象名；例如： vector v; /创建整型向量v指定容器大小：vector 对象名(n)；例如： vector v(10); /创建整型向量v,10个元素注意：元素下标09,初始化为0.指定容器大小和元素初始值：vector 对象名(n,初值)；例如： vector v(10,1); /创建整型向量v,10个元素,每个元素值均为1由已有向量容器创建: vector 对象名(已有对象名)；例如： vector v2(v1); /创建整型向量v1的副本v2,82,拷贝构造函数,创建vector向量,#include #include using namespace std;int main() vector v(10,1); for (vector:iterator it=v.begin();it!=v.end();it+) cout*it,; coutendl; return 0;,【例2】创建一个整型向量容器，输出全部元素值。,84,(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; return 0;,85,vector(向量) 下标访问元素,注意：下标操作仅能对确知已存的元素进行赋值和读取操作,vector ivec; /empty vectorfor( int ix=0; ix 100; +ix) ivecix = ix; /ivec has no element,出错，向量中尚没有元素，不能访问！,(3) 用迭代器访问vector元素,如何使相同的算法能用于不同的数据结构? - 迭代器(算法与容器的”中间人”),87,容器类迭代器定义方法： 容器类名:iterator 变量名; 访问一个迭代器指向的元素： * 迭代器变量名迭代器上可执行”+” , 指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，则迭代器变成past-the-end值。使用一个past-the-end值的迭代器来访问对象是非法的,定义迭代器的关键字,88,对照理解,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 std;int main() vector v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector:const_iterator it1; /常量迭代器 for( it1 = v.begin();it1 != v.end();it1 + ) cout :reverse_iterator it2; /反向迭代器 for( it2 = v.rbegin();it2 != v.rend();it2+ ) cout * it2 ,; cout endl;,89,vector:iterator it3; /非常量迭代器for( it3 = v.begin();it3 != v.end();it3 + ) * it3 = 100; /重置向量for( it3 = v.begin();it3!= v.end();it3+ ) cout * it3 ,;cout =”、“=”、“!=”等比较运算符 可随机访问容器中的数据元素。,vector的迭代器,91,(4) 元素插入,push_back在尾部追加元素;insert方法可在vector任意位置插入元素.,【例5】向整型向量容器追加元素，输出全部元素值。,#include #include using namespace std;int main() vector v(10,1); v.push_back(100);v.psuh_back(-200); for (vector:iterator it=v.begin();it!=v.end();it+) cout*it,; coutendl; return 0;,尾部追加元素，vector容器自动分配内存； 可对空的vector追加，也可对已有元素的vector追加.,尾部元素追加,92,vector(向量)-添加,在尾端增删元素具有较佳的性能,93,指定位置插入元素,insert(iterator it,T t): 对vector容器在指定位置插入新元素,【例6】对整型向量容器插入元素，输出全部元素值。,#include #include using namespace std;int main() vector v(3); vector:iterator it; v0=10; v1=100;v2=-20; v.insert(v.begin(),50); /在最前面插入新元素50 v.insert(v.begin()+2,8); /在第2个元素之前插入新元素8 v.insert(v.end(),9); /在末尾插入新元素9 for (it=v.begin();it!=v.end();it+) cout*it,; coutendl; return 0;,注意：insert方法要求插入的位置，是迭代器位置，而不是下标！,94,通过迭代器随机访问元素,(5) 元素删除,pop_back删除向量最后一个元素；erase删除指定位置或一段区间的元素;clear方法删除所有元素.,【例7】向量容器删除元素方法示例。,#include #include using namespace std;int main() vector v(10); vector:iterator it; for(int i=0;i10;i+) vi=i; v.erase(v.begin()+3); /删除第3个元素，从0开始计数 for (it=v.begin();it!=v.end();it+) cout*it,; coutendl; v.erase(v.begin()+1,v.begin()+3); /删除第13个元素 for (it=v.begin();it!=v.end();it+) cout*it,; coutendl向量V中元素数：v.size()endl; v.clear(); /清空向量 coutendl向量V中元素数：v.size()endl; return 0;,区间删除,95,(6) 向量大小的有关操作,96,向量的大小,size() 和 resize(),vector vec(10, 42); /10 int, each has value 42cout vec.size() endl;vec.resize(15); /adds 5 elements of value 0 to the back of the vectorcout vec.size() endl;vec.resize(25, -1); / adds 10 elements of val