《C完整PPT课件第10章泛型程序设计与C标准模板库.ppt》由会员分享，可在线阅读，更多相关《C完整PPT课件第10章泛型程序设计与C标准模板库.ppt（24页珍藏版）》请在金锄头文库上搜索。
1、第十章第十章 C+标准模板库标准模板库泛型程序设计泛型程序设计将程序写得尽可能通用将程序写得尽可能通用 将算法从特定的数据结构中抽象出来，成为通用的将算法从特定的数据结构中抽象出来，成为通用的C+的模板为泛型程序设计奠定了关键的基础的模板为泛型程序设计奠定了关键的基础 STL是泛型程序设计的一个范例是泛型程序设计的一个范例 容器容器(container)迭代器迭代器(iterator)算法（算法（algorithms）函数对象（函数对象（function object）第十章第十章 C+标准模板库标准模板库命名空间（命名空间（Namespace）一个命名空间将不同的标识符集合在一个命名作用域一
2、个命名空间将不同的标识符集合在一个命名作用域（named scope）内）内为了解决命名冲突为了解决命名冲突例如，声明一个命名空间例如，声明一个命名空间NS：namspace NS class File;void Fun (); 则引用标识符的方式如下，则引用标识符的方式如下，NS: File obj;NS: Fun ();没有声明命名空间的标识符都处于无名的命名空间中没有声明命名空间的标识符都处于无名的命名空间中概念和术语第十章第十章 C+标准模板库标准模板库命名空间（命名空间（Namespace）可以用可以用using来指定命名空间来指定命名空间例如，经过以下声明：例如，经过以下声明：us
3、ing NS:File;在当前作用域中就可以直接引用在当前作用域中就可以直接引用Fileusing namespace std;命名空间命名空间std中所有标识符都可直接引用中所有标识符都可直接引用在新的在新的C+标准程序库中，所有标识符都声标准程序库中，所有标识符都声明在命名空间明在命名空间std中，头文件都不使用扩展中，头文件都不使用扩展名名概念和术语第十章第十章 C+标准模板库标准模板库容器容器容器类是容纳、包含一组元素或元素集合的容器类是容纳、包含一组元素或元素集合的对象。对象。异类容器类与同类容器类异类容器类与同类容器类顺序容器与关联容器顺序容器与关联容器七种基本容器：七种基本容器：
4、向量（向量（vector）、双端队列（）、双端队列（deque）、）、列表（列表（list）、集合（）、集合（set）、多重集合）、多重集合（multiset）、映射（）、映射（map）和多重映）和多重映射（射（multimap）概念和术语第十章第十章 C+标准模板库标准模板库容器的接口容器的接口通用容器运算符通用容器运算符=，!=，=，=，=方法（函数）方法（函数）迭代方法迭代方法begin()begin()，end()end()，rbeginrbegin()()，rend()rend()访问方法访问方法size()size()，max_sizemax_size()()，swap()swap
5、()，empty()empty()第十章第十章 C+标准模板库标准模板库适配器适配器适配器是一种接口类适配器是一种接口类为已有的类提供新的接口。为已有的类提供新的接口。目的是简化、约束、使之安全、隐藏或者目的是简化、约束、使之安全、隐藏或者改变被修改类提供的服务集合。改变被修改类提供的服务集合。三种类型的适配器：三种类型的适配器：容器适配器容器适配器用来扩展用来扩展7种基本容器，它们和顺序容器相结种基本容器，它们和顺序容器相结合构成栈、队列和优先队列容器合构成栈、队列和优先队列容器迭代器适配器迭代器适配器函数对象适配器。函数对象适配器。概念和术语第十章第十章 C+标准模板库标准模板库迭代器迭代
6、器迭代器是面向对象版本的指针，它们提供了访问迭代器是面向对象版本的指针，它们提供了访问容器、序列中每个元素的方法。容器、序列中每个元素的方法。概念和术语第十章第十章 C+标准模板库标准模板库算法算法C+标准模板库中包括标准模板库中包括70多个算法多个算法其中包括查找算法，排序算法，消除算法，记数算其中包括查找算法，排序算法，消除算法，记数算法，比较算法，变换算法，置换算法和容器管理法，比较算法，变换算法，置换算法和容器管理等等。等等。这些算法的一个最重要的特性就是它们的统一性，并这些算法的一个最重要的特性就是它们的统一性，并且可以广泛用于不同的对象和内置的数据类型。且可以广泛用于不同的对象和内
7、置的数据类型。概念和术语第十章第十章 C+标准模板库标准模板库顺序容器顺序容器顺序容器的接口顺序容器的接口插入方法插入方法push_front()，push_back()，insert()，运算符，运算符“=”删除方法删除方法pop() ，erase()，clear()迭代访问方法迭代访问方法使用迭代器使用迭代器其它顺序容器访问方法（不修改访问方法）其它顺序容器访问方法（不修改访问方法）front()，back()，下标，下标运算符运算符容 器第十章第十章 C+标准模板库标准模板库顺序容器顺序容器向量向量向量属于顺序容器，用于容纳不定长线性序列（即线向量属于顺序容器，用于容纳不定长线性序列（即
8、线性群体），提供对序列的快速随机访问（也称直接性群体），提供对序列的快速随机访问（也称直接访问）访问）向量是动态结构，它的大小不固定，可以在程序运行向量是动态结构，它的大小不固定，可以在程序运行时增加或减少。时增加或减少。例例10-1求范围求范围2N中的质数，中的质数，N在程序运行时由键盘输入。在程序运行时由键盘输入。容 器/10_1.cpp/10_1.cpp#include #include #include #include #include #include /包含向量容器头文件包含向量容器头文件using namespace std ;using namespace std ;void
9、 void main(voidmain(void) ) vector vector A(10); A(10); intint n; n; intint primecountprimecount = 0, i, j; = 0, i, j; coutcout=2 as upper limit: ;=2 as upper limit: ; cincin n; n; AprimecountAprimecount+ = 2;+ = 2;11 for(ifor(i = 3; i n; i+) = 3; i n; i+) if ( if (primecountprimecount = = A.sizeA.s
10、ize()() A.resize(primecountA.resize(primecount + 10); + 10); if (i % 2 = 0) if (i % 2 = 0) continue; continue; j = 3; j = 3; while (j = i/2 & i % j != 0) while (j i/2) if (j i/2) AprimecountAprimecount+ = i;+ = i; for (i = 0; i for (i = 0; iprimecountprimecount; i+)/; i+)/输出质数输出质数 coutcoutsetw(5)set
11、w(5)AiAi; ; if (i+1) % 10 = 0) / if (i+1) % 10 = 0) /每输出每输出1010个数换行一次个数换行一次 coutcout endlendl; ; coutcoutendlendl; ; 12第十章第十章 C+标准模板库标准模板库顺序容器顺序容器双端队列双端队列双端队列是一种放松了访问权限的队列。元素可以从双端队列是一种放松了访问权限的队列。元素可以从队列的两端入队和出队，也支持通过下标操作符队列的两端入队和出队，也支持通过下标操作符“”进行直接访问。进行直接访问。例例10-2使用双端队列容器保存双精度数值序列使用双端队列容器保存双精度数值序列容
12、器第十章第十章 C+标准模板库标准模板库顺序容器顺序容器列表列表列表主要用于存放双向链表，可以从任意一端开始遍列表主要用于存放双向链表，可以从任意一端开始遍历。列表还提供了拼接（历。列表还提供了拼接（splicing）操作，将一个）操作，将一个序列中的元素从插入到另一个序列中。序列中的元素从插入到另一个序列中。例例10-3 改写例改写例9-7从键盘输入从键盘输入10个整数，用这些整数值作为结点数个整数，用这些整数值作为结点数据，生成一个链表，按顺序输出链表中结点的据，生成一个链表，按顺序输出链表中结点的数值。然后从键盘输入一个待查找整数，在链数值。然后从键盘输入一个待查找整数，在链表中查找该整
13、数，若找到则删除该整数所在的表中查找该整数，若找到则删除该整数所在的结点（如果出现多次，全部删除），然后输出结点（如果出现多次，全部删除），然后输出删除结点以后的链表。在程序结束之前清空链删除结点以后的链表。在程序结束之前清空链表。表。容 器/10_3.cpp/10_3.cpp#include #include #include #include using namespace std ;using namespace std ;void void main(voidmain(void) ) list list Link; Link;/构造一个列表用于存放整数链表构造一个列表用于存放整数链表
14、intint i, key, item; i, key, item; for(ifor(i=0;i 10;i+)/ =0;i item;item; Link.push_front(itemLink.push_front(item);); coutcoutList: ; / List: ; / 输出链表输出链表15 listlist:iteratoriterator p= p=Link.beginLink.begin(); (); while(pwhile(p!=!=Link.endLink.end()/()/输出各节点数据，直到链表尾输出各节点数据，直到链表尾 coutcout *p ; *p
15、 ; p+; / p+; /使使P P指向下一个节点指向下一个节点 coutcout endlendl; ; coutcout key; key; Link.remove(keyLink.remove(key); ); coutcout List: ; / List: ; / 输出链表输出链表 p=p=Link.beginLink.begin();();/ / 使使P P重新指向表头重新指向表头 while(pwhile(p!=!=Link.endLink.end()() coutcout *p ; *p ; p+; / p+; / 使使P P指向下一个节点指向下一个节点 coutcout e
16、ndlendl; ; 16第十章第十章 C+标准模板库标准模板库容器适配器容器适配器容器适配器是用来扩展容器适配器是用来扩展7种基本容器的种基本容器的栈容器栈容器使用适配器与一种基础容器相结合来实现使用适配器与一种基础容器相结合来实现例例10-4：应用标准库中的：应用标准库中的deque顺序容器生成一个顺序容器生成一个整数栈整数栈stack。队列容器队列容器使用适配器与一种基础容器相结合来实现的先进先使用适配器与一种基础容器相结合来实现的先进先出数据结构。出数据结构。例例10-5：应用标准库中的：应用标准库中的deque顺序容器生成一个顺序容器生成一个整数标准队列整数标准队列Queue。容 器
17、第十章第十章 C+标准模板库标准模板库什么是迭代器什么是迭代器迭代器是面向对象版本的指针迭代器是面向对象版本的指针指针可以指向内存中的一个地址指针可以指向内存中的一个地址迭代器可以指向容器中的一个位置迭代器可以指向容器中的一个位置STL的每一个容器类模版中，都定义了一组对应的迭的每一个容器类模版中，都定义了一组对应的迭代器类。使用迭代器，算法函数可以访问容器中指代器类。使用迭代器，算法函数可以访问容器中指定位置的元素，而无需关心元素的具体类型。定位置的元素，而无需关心元素的具体类型。迭代器第十章第十章 C+标准模板库标准模板库迭代器的类型迭代器的类型输入迭代器输入迭代器可以用来从序列中读取数据
18、可以用来从序列中读取数据输出迭代器输出迭代器允许向序列中写入数据允许向序列中写入数据前向迭代器前向迭代器既是输入迭代器又是输出迭代器，并且可以对序列进行单既是输入迭代器又是输出迭代器，并且可以对序列进行单向的遍历向的遍历双向迭代器双向迭代器与前向迭代器相似，但是在两个方向上都可以对数据遍历与前向迭代器相似，但是在两个方向上都可以对数据遍历随机访问迭代器随机访问迭代器也是双向迭代器，但能够在序列中的任意两个位置之间进也是双向迭代器，但能够在序列中的任意两个位置之间进行跳转。行跳转。迭代器第十章第十章 C+标准模板库标准模板库迭代器适配器迭代器适配器迭代器适配器是用来扩展（或调整）迭代器功能的类。
19、它本身迭代器适配器是用来扩展（或调整）迭代器功能的类。它本身也被称为迭代器，只是这种迭代器是通过改变另一个迭代器也被称为迭代器，只是这种迭代器是通过改变另一个迭代器而得到的而得到的逆向迭代器逆向迭代器通过重新定义递增运算和递减运算，使其行为正好倒置通过重新定义递增运算和递减运算，使其行为正好倒置插入型迭代器插入型迭代器将赋值操作转换为插入操作。通过这种迭代器，算法可以将赋值操作转换为插入操作。通过这种迭代器，算法可以执行插入行为而不是覆盖行为执行插入行为而不是覆盖行为例例10-6应用逆向迭代器和后插迭代器来操作向量容器中的元素应用逆向迭代器和后插迭代器来操作向量容器中的元素迭代器第十章第十章
20、C+标准模板库标准模板库迭代器相关的辅助函数迭代器相关的辅助函数advance()函数函数将迭代器的位置增加，增加的幅度由参数决定将迭代器的位置增加，增加的幅度由参数决定Distance()函数函数返回迭代器之间的距离返回迭代器之间的距离函数函数iter_swap()交换两个迭代器所指向的元素值交换两个迭代器所指向的元素值例例10-7用三个迭代器辅助函数来操作列表容器中的元素。用三个迭代器辅助函数来操作列表容器中的元素。迭代器第十章第十章 C+标准模板库标准模板库标准标准C+库中的算法库中的算法算法本身是一种函数模板算法本身是一种函数模板不可变序列算法不可变序列算法（Non-mutating
21、algorithmsNon-mutating algorithms）不直接修改所操作的容器内容的算法不直接修改所操作的容器内容的算法可变序列算法可变序列算法（Mutating algorithmsMutating algorithms）可以修改它们所操作的容器的元素。可以修改它们所操作的容器的元素。排序相关算法排序相关算法数值算法数值算法算 法第十章第十章 C+标准模板库标准模板库算法应用举例算法应用举例例例10-9应用不可变序列算法对数据序列进行分析应用不可变序列算法对数据序列进行分析例例10-10以可变序列算法对数据序列进行复制，生成，删除，以可变序列算法对数据序列进行复制，生成，删除，替
22、换，倒序，旋转等可变性操作。替换，倒序，旋转等可变性操作。例例10-11 应用排序相关算法对序列进行各项操作应用排序相关算法对序列进行各项操作例例10-12应用数值算法对数据序列进行操作应用数值算法对数据序列进行操作算 法第十章第十章 C+标准模板库标准模板库函数对象函数对象一个行为类似函数的对象，它可以不需参数，也可以一个行为类似函数的对象，它可以不需参数，也可以带有若干参数，其功能是获取一个值，或者改变操带有若干参数，其功能是获取一个值，或者改变操作的状态。作的状态。任何普通的函数和任何重载了调用运算符任何普通的函数和任何重载了调用运算符operator()的类的对象都满足函数对象的特征的类的对象都满足函数对象的特征STL中也定义了一些标准的函数对象，如果以功能划中也定义了一些标准的函数对象，如果以功能划分，可以分为算术运算、关系运算、逻辑运算三大分，可以分为算术运算、关系运算、逻辑运算三大类。为了调用这些标准函数对象，需要包含头文件类。为了调用这些标准函数对象，需要包含头文件。
