数据结构课件STL

《数据结构课件STL》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、C++模板与STL库介绍提纲1.概论2.模板机制的介绍3.STL中的基本概念4.容器概述5.迭代器6.算法简介概论C++语言的核心优势之一就是便于软件的重用C++中有两个方面体现重用：1.面向对象的思想：继承和多态，标准类库2.泛型程序设计(genericprogramming)的思想：模板机制，以及标准模板库STL泛型程序设计泛型程序设计，简单地说就是使用模板的程序设计法。将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算

2、法。标准模板库(StandardTemplateLibrary)就是一些常用数据结构和算法的模板的集合。主要由AlexStepanov开发，于1998年被添加进C++标准有了STL，不必再从头开始编写繁多的标准数据结构和算法，并且一样可获得非常高的性能。模板引子1.假如设计一个求两参数最大值的函数，在实践中我们可能需要定义四个函数：intmax(inta,intb){return(a>b)?a,b;}longmax(longa,longb){return(a>b)?a,b;}doublemax(doublea,doubleb){return(a>

3、b)?a,b;}charmax(chara,charb){return(a>b)?a,b;}2.这些函数几乎相同，唯一的区别就是形参类型不同3.需要事先知道有哪些类型会使用这些函数，对于未知类型这些函数不起作用模板的概念所谓模板是一种使用无类型参数来产生一系列函数或类的机制。若一个程序的功能是对某种特定的数据类型进行处理，则可以将所处理的数据类型说明为参数，以便在其他数据类型的情况下使用，这就是模板的由来。模板是以一种完全通用的方法来设计函数或类而不必预先说明将被使用的每个对象的类型。通过模板可以产生类或函数的集合，使它们操作不同的数据类型，从而

4、避免需要为每一种数据类型产生一个单独的类或函数。模板分类函数模板(functiontemplate)是独立于类型的函数可产生函数的特定版本类模板(classtemplate)跟类相关的模板，如vector可产生类对特定类型的版本，如vector7求最大值模板函数实现1.求两个数最大值，使用模板templateTmax(Ta,Tb){return(a>b)?a,b;}2.template<模板形参表><返回值类型><函数名>（模板函数形参表）{//函数定义体}8模板工作方式函数模板只是说明，不能直接执行，需要实例化为模板函

5、数后才能执行在说明了一个函数模板后，当编译系统发现有一个对应的函数调用时，将根据实参中的类型来确认是否匹配函数模板中对应的形参，然后生成一个重载函数。该重载函数的定义体与函数模板的函数定义体相同，它称之为模板函数9#includetemplateTmin(Ta[],intn){inti;Tminv=a[0];for(i=1;ia[i])minv=a[i];}returnminv;}编写一个对具有n个元素的数组a[]求最小值的程序，要求将求最小值的函数设计成函数模板。voidmai

6、n(){inaa[]={1,3,0,2,7,6,4,5,2};doubleb[]={1.2,-3.4,6.8,9,8};cout<<”a数组的最小值为：”<

7、，改成模板函数11STL中的几个基本概念容器：可容纳各种数据类型的多元素数据结构。迭代器：可依次存取容器中元素的东西(指针？下标?)算法：用来操作容器中的元素的函数模板。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象。函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。比如，数组intarray[100]就是个容器，而int*类型的指针变量就可以作为迭代器，可以为这个容器编写一个排序的算法容器概述可以用于存放各种类型的数据（基本类型的变量，

8、对象等）的数据结构。容器分为三大类：1)顺序容器vector：后部插入/删除，直接访问deque：前/后部插入/删除，直接访问list：