《第十部分C标准模板库本部分以自学为主教学课件》由会员分享，可在线阅读，更多相关《第十部分C标准模板库本部分以自学为主教学课件（28页珍藏版）》请在金锄头文库上搜索。
1、第十章第十章 C+C+标准模板库标准模板库本章以自学为主本章以自学为主仲恺农业技术学院仲恺农业技术学院 计算科学系计算科学系 胡小健胡小健高级语言程序设计（C+)STL与泛型算法与泛型算法主要内容主要内容l泛型程序设计泛型程序设计l与标准模板库有关的概念和术语与标准模板库有关的概念和术语lC+C+标准模板库中的容器标准模板库中的容器l迭代器迭代器l标准标准C+C+库中的算法库中的算法l函数对象函数对象 2STL与泛型算法与泛型算法泛型程序设计泛型程序设计l将程序写得尽可能通用将程序写得尽可能通用 ，即：将算法从特定，即：将算法从特定的数据结构中抽象出来，成为通用的（可针的数据结构中抽象出来，成
2、为通用的（可针对各种数据类型）对各种数据类型）lC+C+的模板为泛型程序设计奠定了关键的基础的模板为泛型程序设计奠定了关键的基础 lSTL是泛型程序设计的一个范例是泛型程序设计的一个范例 容器容器(container)迭代器迭代器(iterator)算法（算法（algorithms）函数对象（函数对象（function object）四个最关键的组件四个最关键的组件3STL与泛型算法与泛型算法本章重点本章重点l群体数据的类型多且处理复杂。不过，不是群体数据的类型多且处理复杂。不过，不是所有的程序员都要从头开始自行设计所需要所有的程序员都要从头开始自行设计所需要的类型及算法。的类型及算法。lSt
3、andard Template LibraryStandard Template Library是已有的经是已有的经典优秀的模板，本章的重点是如何使用典优秀的模板，本章的重点是如何使用现有的现有的STLSTL。重点理解本章例重点理解本章例10-110-1至例至例10-1510-15的所有例题，的所有例题，请自行学习，请自行学习，不明白的，要求查找不明白的，要求查找MSDNMSDN（考试重点）（考试重点）：ReferenceCC+Language and C+Libraries Standard C+Library Reference或或上网查找上网查找。试卷中本章内容均是本章的例题及布置的练习
4、（两道试卷中本章内容均是本章的例题及布置的练习（两道大题），大题），4STL与泛型算法与泛型算法命名空间（命名空间（NamespaceNamespace）的引入）的引入l在缺省情况下，在全局域中声明的每个对象、函数、类型或在缺省情况下，在全局域中声明的每个对象、函数、类型或模板都引入了一个全局实体模板都引入了一个全局实体(global entity).在全局名字空在全局名字空间域引入的全局实体必须有唯一的名字。间域引入的全局实体必须有唯一的名字。l例如：函数和对象不能有相同的名字，无论它们是否在同一例如：函数和对象不能有相同的名字，无论它们是否在同一程序文本文件中被声明。程序文本文件中被声明。
5、l如果程序中使用一个库，必须保证程序中的全局实体的名字如果程序中使用一个库，必须保证程序中的全局实体的名字不能与库中的全局实体名字冲突。如果程序是由许多厂商提不能与库中的全局实体名字冲突。如果程序是由许多厂商提供的库构成，则很难保证各种库会将许多名字引入到全局字供的库构成，则很难保证各种库会将许多名字引入到全局字空间域中。在组合不同厂商的库时，就怎样才能确保程序中空间域中。在组合不同厂商的库时，就怎样才能确保程序中的全局实体不会与这些库中声明的全局实体名冲突？名字冲的全局实体不会与这些库中声明的全局实体名冲突？名字冲突问题也被称为：全局名字空间污染突问题也被称为：全局名字空间污染(global
6、 namespace pollution)l程序员可以通过使用全局实体名字很长或在名字前加特殊的程序员可以通过使用全局实体名字很长或在名字前加特殊的字符序列前缀，从而避免这些问题，但这样是个累赘。字符序列前缀，从而避免这些问题，但这样是个累赘。l而名字空间正是解决此类问题而引入的一种机制。而名字空间正是解决此类问题而引入的一种机制。5STL与泛型算法与泛型算法命名空间（命名空间（NamespaceNamespace）的引入）的引入l库的作者可定义一个名字空间，从而库中的所有引入的实体库的作者可定义一个名字空间，从而库中的所有引入的实体都隐藏在该名字空间之中。如：都隐藏在该名字空间之中。如：ln
7、amespace cplusplus_primer class matrix void inverse (matrix &) . l在一个名字空间中声明的实体如：函数，对象、类、类模板在一个名字空间中声明的实体如：函数，对象、类、类模板和类型声明等都被称为名字空间的成员（和类型声明等都被称为名字空间的成员（namespace member）。用户声明的名字空间中的每个名字必须是名）。用户声明的名字空间中的每个名字必须是名字空间内的唯一实体。但不同用户声明的名字空间引入了不字空间内的唯一实体。但不同用户声明的名字空间引入了不同的域，所以两个不同的名字空间可以有相同的名字成员。同的域，所以两个不同
8、的名字空间可以有相同的名字成员。如：如：namespace DisneyFeatureAnimation class matrix . void inverse (matrix &).l在程序中我们可以用既定修饰名来使用名字空间的成员。在程序中我们可以用既定修饰名来使用名字空间的成员。6STL与泛型算法与泛型算法命名空间（命名空间（NamespaceNamespace）的引入）的引入void func (DisneyFeatureAnimation:Matrix &m) DisneyFeatrueAnimation:inverse(m);void main () cplusplus:Matri
9、x m1; .如果：如果：using namespace DisneyFeatureAnimationvoid main () Matrix m1; cplusplus:Matrix m2; .7STL与泛型算法与泛型算法命名空间（命名空间（NamespaceNamespace）l一个命名空间将不同的标识符集合在一个命名作用一个命名空间将不同的标识符集合在一个命名作用域（域（named scope）内）内为了解决命名冲突为了解决命名冲突例如，声明一个命名空间例如，声明一个命名空间NS：namspace NS class File; void Fun (); . . . . . . 则引用标识符
10、的方式如下，则引用标识符的方式如下，NS: File obj;NS: Fun ();l没有声明命名空间的标识符都处于无名的命名空间没有声明命名空间的标识符都处于无名的命名空间中中8STL与泛型算法与泛型算法l可以用可以用using来指定命名空间来指定命名空间例如，经过以下声明：例如，经过以下声明：using NS:File; /或或 using NS;/在当前作用域中就可以直接引用在当前作用域中就可以直接引用Fileusing namespace std;命名空间命名空间std中所有标识符都可直接引用中所有标识符都可直接引用l在新的在新的C+标准程序库中，所有标识符都声标准程序库中，所有标识符
11、都声明在命名空间明在命名空间std中，头文件都不使用扩展中，头文件都不使用扩展名名命名空间（命名空间（NamespaceNamespace）有关命名空间（有关命名空间（NamespaceNamespace） 详见详见C+ PrimerC+ Primer9STL与泛型算法与泛型算法容器容器l容器类是容纳、包含一组元素或元素集合的对容器类是容纳、包含一组元素或元素集合的对象。象。l异类容器类与同类容器类异类容器类与同类容器类l顺序容器与关联容器顺序容器与关联容器l七种基本容器：七种基本容器：向量（向量（vector） 双端队列（双端队列（deque）列表（列表（list） 集合（集合（set）多重
12、集合（多重集合（multiset） 映射（映射（map）多重映射（多重映射（multimap）10STL与泛型算法与泛型算法容器的接口容器的接口l通用容器运算符通用容器运算符=，!=，=，=，=l方法（函数）方法（函数）迭代方法迭代方法lbegin()，end()，rbegin()，rend()访问方法访问方法size()，max_size()，swap()，empty()11STL与泛型算法与泛型算法适配器适配器l适配器是一种适配器是一种接口类接口类为已有的类提供新的接口为已有的类提供新的接口。目的是简化、约束、使之安全、隐藏或者改变目的是简化、约束、使之安全、隐藏或者改变被修改类提供的服务
13、集合。被修改类提供的服务集合。l三种类型的适配器：三种类型的适配器：容器适配器容器适配器l用来扩展用来扩展7种基本容器，它们和顺序容器相结种基本容器，它们和顺序容器相结合构成栈、队列和优先队列容器合构成栈、队列和优先队列容器迭代器适配器迭代器适配器函数对象适配器函数对象适配器。12STL与泛型算法与泛型算法迭代器迭代器迭代器是面向对象版本的指针，它们提迭代器是面向对象版本的指针，它们提供了访问容器、序列中每个元素的方法。供了访问容器、序列中每个元素的方法。13STL与泛型算法与泛型算法算法算法lC+标准模板库标准模板库中包括中包括70多个算法多个算法其中包括查找算法，排序算法，消除算法，其中包
14、括查找算法，排序算法，消除算法，记数算法，比较算法，变换算法，置换算法记数算法，比较算法，变换算法，置换算法和容器管理等等。和容器管理等等。l这些算法的一个最重要的特性就是它们的这些算法的一个最重要的特性就是它们的统一性统一性，并且可以广泛用于不同的对并且可以广泛用于不同的对象和内置的数据类型象和内置的数据类型。l使用时必须指名模板参数。使用时必须指名模板参数。14STL与泛型算法与泛型算法顺序容器顺序容器顺序容器的接口顺序容器的接口:插入方法插入方法 push_front(), push_back(), insert(), “=”删除方法删除方法lpop() ，erase()，clear()
15、迭代访问方法迭代访问方法l使用迭代器使用迭代器其它顺序容器访问方法（不修改访问方法）其它顺序容器访问方法（不修改访问方法）lfront()，back()，下标，下标 运算符运算符15STL与泛型算法与泛型算法顺序容器顺序容器向量向量l向量属于顺序容器，用于容纳不定长向量属于顺序容器，用于容纳不定长线性序列（即线性群体），提供对序线性序列（即线性群体），提供对序列的快速随机访问（也称直接访问）列的快速随机访问（也称直接访问）l向量是动态结构，它的大小不固定，向量是动态结构，它的大小不固定，可以在程序运行时增加或减少。可以在程序运行时增加或减少。16#include /10_1.cpp#inclu
16、de #include using namespace std ;void main(void) vector A(10); int n; int primecount = 0, i, j; cout=2 as upper limit: ; cin n; A primecount+ = 2;17 for(i = 3; i n; i+) if (primecount = A.size() ) A.resize ( primecount + 10); if (i % 2 = 0) continue; j = 3; while (j i/2) Aprimecount+ = i; for (i = 0
17、; iprimecount; i+) /输出质数 coutsetw(5)Ai; if (i+1) % 10 = 0) cout endl; coutendl;17STL与泛型算法与泛型算法#include #includeusing namespace std;void main() typedef vector IntArray; IntArray array; array.push_back( 1 ); array.push_back( 2 ); array.push_back( 2 ); array.push_back( 3 ); array.push_back( 2 ); array.
18、push_back( 2 ); array.push_back( 2 ); array.push_back( 5 ); for( IntArray:iterator itor=array.begin(); itor!=array.end(); +itor ) cout*itor ; coutendl; for(itor=array.begin(); itor!=array.end(); +itor ) if( 2 = *itor ) / 删除array数组中所有值为2的元素 array.erase( itor ); coutendlarray.size()endl; for( itor=arr
19、ay.begin(); itor!=array.end(); +itor ) cout*itor ; coutendl; 18STL与泛型算法与泛型算法顺序容器顺序容器双端队列双端队列l双端队列是一种放松了访问权限的队列。双端队列是一种放松了访问权限的队列。元素可以从队列的两端入队和出队，也元素可以从队列的两端入队和出队，也支持通过下标操作符支持通过下标操作符“ ”进行直接访进行直接访问。问。重点掌握（要求同前）：重点掌握（要求同前）： P338 P338 例例10-210-219STL与泛型算法与泛型算法顺序容器顺序容器列表列表l列表主要用于存放双向链表，可以从任意一列表主要用于存放双向链表
20、，可以从任意一端开始遍历。列表还提供了拼接端开始遍历。列表还提供了拼接（splicing）操作，将一个序列中的元素从）操作，将一个序列中的元素从插入到另一个序列中。插入到另一个序列中。20#include /10_3.cpp#include using namespace std ;void main(void) list Link;/构造一个用于存放整数链表 int i, key, item; for(i=0;i item; Link.push_front(item); coutList: ; / 输出链表21 list:iterator p=Link.begin(); while(p!=
21、Link.end( ) ) /输出各节点数据直到链表尾 cout *p ; p+; /使P指向下一个节点 cout endl key; Link.remove(key); cout List: ; / 输出链表 p=Link.begin();/ 使P重新指向表头 while( p!=Link.end() ) cout *p ; p+; / 使P指向下一个节点 21STL与泛型算法与泛型算法容器适配器容器适配器l容器适配器是用来扩展容器适配器是用来扩展7种基本容器的种基本容器的l栈容器栈容器使用适配器与一种基础容器相结合来实现使用适配器与一种基础容器相结合来实现l队列容器队列容器使用适配器与一种
22、基础容器相结合来实现的先使用适配器与一种基础容器相结合来实现的先进先出数据结构。进先出数据结构。重点掌握（要求同前）：重点掌握（要求同前）： P341 P341 例例10-410-4P342P342例例10-510-522STL与泛型算法与泛型算法什么是迭代器什么是迭代器l迭代器是面向对象版本的指针迭代器是面向对象版本的指针指针可以指向内存中的一个地址指针可以指向内存中的一个地址迭代器可以指向容器中的一个位置迭代器可以指向容器中的一个位置lSTL的的每一个容器类模版中，都每一个容器类模版中，都定义了一组对应的迭代器类定义了一组对应的迭代器类l使用迭代器，算法函数可以访问使用迭代器，算法函数可以
23、访问容器中指定位置的元素，而无需容器中指定位置的元素，而无需关心元素的具体类型。关心元素的具体类型。23迭代器的类型迭代器的类型l输入迭代器输入迭代器可以用来从序列中读取数据可以用来从序列中读取数据l输出迭代器输出迭代器允许向序列中写入数据允许向序列中写入数据l前向迭代器前向迭代器既是输入迭代器又是输出迭代器，并且可以对序列既是输入迭代器又是输出迭代器，并且可以对序列进行单向的遍历进行单向的遍历l双向迭代器双向迭代器与前向迭代器相似，但是在两个方向上都可以对数与前向迭代器相似，但是在两个方向上都可以对数据遍历据遍历l随机访问迭代器随机访问迭代器也是双向迭代器，但能够在序列中的任意两个位置也是双
24、向迭代器，但能够在序列中的任意两个位置之间进行跳转。之间进行跳转。24STL与泛型算法与泛型算法迭代器适配器迭代器适配器l迭代器适配器是用来扩展（或调整）迭代器迭代器适配器是用来扩展（或调整）迭代器功能的类。它本身也被称为迭代器，只是这功能的类。它本身也被称为迭代器，只是这种迭代器是通过改变另一个迭代器而得到的种迭代器是通过改变另一个迭代器而得到的l逆向迭代器逆向迭代器通过重新定义递增运算和递减运算，使其行为正通过重新定义递增运算和递减运算，使其行为正好倒置好倒置l插入型迭代器插入型迭代器将赋值操作转换为插入操作。通过这种迭代器，将赋值操作转换为插入操作。通过这种迭代器，算法可以执行插入行为而
25、不是覆盖行为算法可以执行插入行为而不是覆盖行为25STL与泛型算法与泛型算法迭代器相关的辅助函数迭代器相关的辅助函数ladvance()函数函数将迭代器的位置增加，增加的幅度由参数决将迭代器的位置增加，增加的幅度由参数决定定lDistance()函数函数返回迭代器之间的距离返回迭代器之间的距离l函数函数iter_swap()交换两个迭代器所指向的元素值交换两个迭代器所指向的元素值重点掌握（要求同前）：重点掌握（要求同前）： P344 P344 例例10-610-6P346P346例例10-710-726STL与泛型算法与泛型算法标准标准C+C+库中的算法库中的算法l算法本身是一种函数模板算法本
26、身是一种函数模板l不可变序列算法（不可变序列算法（Non-mutating algorithms）不直接修改所操作的容器内容的算法不直接修改所操作的容器内容的算法l可变序列算法（可变序列算法（Mutating algorithms）可以修改它们所操作的容器的元素。可以修改它们所操作的容器的元素。l排序相关算法排序相关算法l数值算法数值算法重点掌握（要求同前）：重点掌握（要求同前）： P349 P349 例例10-810-8P353P353例例10-910-9 P357 P357例例10-10 P36010-10 P360例例10-11 10-11 P360 P360例例10-1210-1227
27、STL与泛型算法与泛型算法函数对象函数对象l一个行为类似函数的对象，它可以不需参数，也一个行为类似函数的对象，它可以不需参数，也可以带有若干参数，其功能是获取一个值，或者可以带有若干参数，其功能是获取一个值，或者改变操作的状态。改变操作的状态。l任何普通的函数和任何重载了调用运算符任何普通的函数和任何重载了调用运算符operator()的类的对象都满足函数对象的特征的类的对象都满足函数对象的特征lSTL中也定义了一些标准的函数对象，如果以功中也定义了一些标准的函数对象，如果以功能划分，可以分为算术运算、关系运算、逻辑运能划分，可以分为算术运算、关系运算、逻辑运算三大类。为了调用这些标准函数对象，需要包算三大类。为了调用这些标准函数对象，需要包含头文件含头文件。重点掌握（要求同前）：重点掌握（要求同前）： P361 P361 例例10-1310-13P362P362例例10-1410-14 P363 P363例例10-1510-1528
