模板与标准模板库.ppt

第7章 模板与标准模板库,STL-灵活、可扩展、可重用的软件模块,上海大学机电工程与自动化学院 雷电,引言：对象管理,上海大学机电工程与自动化学院 雷电,对象管理,创建对象：占据内存使用对象：Set,Get,IO,change缓存(保存)对象：因为数据的产生与消费不同时不同步释放对象：不再占据内存内存区域：栈：自动局部变量，参变量堆：动态内存分配，只能通过指针间接访问。静态存储区：全局变量，静态变量，常数块,上海大学机电工程与自动化学院 雷电,对象管理-基于数组的方法,1.通过下标访问或遍历数组元素2.通过指针访问或遍历数组元素数组元素就是对象数组元素是对象的指针(地址)，当对象个数不确定且对象很大时采用此方法。1.确定的元素个数(数组长度)2.创建足够长的数组，元素个数不确定时。1）使用一个变量记录实际的元素个数2）不够时重新创建并复制原有的数据,上海大学机电工程与自动化学院 雷电,class CSame public:int type;.;例1：CSame gList2000;int N=0;。/添加新对象时的编程gList N.type=0 x100;N+;例2：CSame*gList 2000;int N=0;。/添加新对象时的编程gList N=new CSame;gList N-type=;N+;,上海大学机电工程与自动化学院 雷电,对象管理-基于链表 的方法,引言:基于数组的表在需要更灵活的处理方法时是不够的.,如一个定票系统.数组是一种定长结构,内存顺序存放.数组优点是访问一个元素方便,但在中间插入删除元素和变长操作严重影响性能.好的方案是:动态内存分配元素(结点).这些元素(结点),在内存非顺序存放,且有全局生命周期，都通过指针连接在一起.描述一个链表:,上海大学机电工程与自动化学院 雷电,一种新的存储模式，链条模型：,插入后：,删除后：,链表的长度可以无限增加（只限于内存大小），数据元素在内存中非连续存放,上海大学机电工程与自动化学院 雷电,结点,结点链表中的结点必须是结构体变量，结点的数据类型至少包含两部分信息：1)数据.2)下个结点的地址（指针）。,struct NODE ElemType data;struct NODE*next;,例:struct Student int num;float score;struct Student*next;,数据,头指针、尾指针 只要知道第一个结点的地址（指针）就可以访问到所有结点，指向第0个结点（头结点的）的指针称为头指针。已知头指针也就确定了整个链表。,单链表中最后结点（尾结点）的指针域值=NULL(即等于0)，不指向任何内存单元。,head,NULL,上海大学机电工程与自动化学院 雷电,标准C+类库概述,10年的争论，有了C+库的ANSI/ISO标准-Standard Template Library(STL),是ANSI/ISO C+最有特色、最实用的部分之一。STL包括：输入输出类容器类与ADT（抽象数据类型）算法存储管理错误处理语言环境,上海大学机电工程与自动化学院 雷电,7.1 模板的基本知识,使用面向对象方法构建软件系统，我们可以利用OO的特性，很好的解决纵向的问题，因为，OO的核心概念，如继承等，都是纵向结构的。但是，在软件系统中，往往有很多模块，或者很多类共享某个行为，或者说，某个行为存在于软件的各个部分中，这个行为可以看作是“横向”存在于软件之中.例：先进后出行为（栈）代码重用：垂直性：继承、多态水平性：模板（参数化）例：函数的参数其数据类型是参数化的。如：T a；例：数组类、队列类等，其中的元素的类型是参数化的。,上海大学机电工程与自动化学院 雷电,模板函数用关键字 template 描述的形式参数修饰函数 templateT1,T2,用来说明函数的参数类型。例：求两数中较大的数。templateT maxV(T a,T b)return ab?a:b;main()double a=maxV(0.1,0.2);int d=maxV(1,2);例：查找 templateint SeqSearch(T list,T key,int n)for(int i=0;in;i+)if(listi=key)return i;return-1;,上海大学机电工程与自动化学院 雷电,模板类1.模板类的定义：templateclass 类名;T1,T2,用来说明类中数据成员和成员函数的类型。2.模板类方法的外联式的实现：template 类型 类名:成员函数(.)3.创建模板类对象模板类不是实例类，模板类的模板参数必须有具体的实例类才能创建其对象，否则没有创建其对象的概念。模板类名 obj;模板类名*pobj=new模板类名;,上海大学机电工程与自动化学院 雷电,7.1-7.1.2 模板类，模板实例例：P258 Arraytempl.dsw7.1.3 模板的函数式参数例：P262 Array templ_ex.dsw,上海大学机电工程与自动化学院 雷电,7.2.7 断言(assert),用于调试，使用方法assert(表达式);当表达式为假，系统停止程序在该处，于是可检查调用栈各函数的执行的状态。当表达式为真，系统继续执行后面的代码。头文件#include 在其头文件前声明NDEBUG#define NDEBUG可关闭，即不执行assert语句，节省CPU。最后交付不再调试程序时才这样做。,上海大学机电工程与自动化学院 雷电,7.2 示例程序 模板Stack类,定义实现使用使用assert 用于调试Stack_Ex,模板参数还可以是实例类型例:template class Stack;Stack stack;,上海大学机电工程与自动化学院 雷电,7.3 标准模板库 STL,7.3.1 容器、算法、迭代器STL容器：对象的集合，通过由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，这些成员函数通过返回迭代子来指定元素在序列中的位置。序列式：vector,stack,queue,deque,list关联式：set,map特点：容器的大小动态变化，容器中的对象类型是参数化的。,上海大学机电工程与自动化学院 雷电,容器分为三大类：,上海大学机电工程与自动化学院 雷电,算法：对容器进行处理的函数，是模板函数.通用的算法更易于扩充。算法中采用函数对象（function object）引入不同情况下同一算法的差异。它没有使用继承和多态，避免了虚函数的开销，使STL效率更高。copy,sort,search,merge,上海大学机电工程与自动化学院 雷电,迭代子（iterator),迭代子（iterator):对容器中对象的遍历机制，表现如同指针，或是一种高级指针,是面向对象版本的指针，它提供了访问容器或序列中每个对象的方法。这样就可以把算法用于容器所管理的序列。,int A100;int*p=A;for(int i=0;i100;i+)*p=i;p+,vector A(100);vector:iterator p=A.begin();for(int i=0;i100;i+)*p=i;p+;,上海大学机电工程与自动化学院 雷电,各种迭代子可执行的操作,上海大学机电工程与自动化学院 雷电,所有容器通用的方法插入：insert(位置，对象)删除：erase(位置)，erase(位置1,位置2)清除所有元素：clear()所有容器通用的特殊方法首元素迭代子：begin()尾迭代子（最后一个元素的后继位置）：end()元素个数：size()判容器是否为空：empty()所有容器通用的特殊操作符：访问元素：*迭代子指向下个元素：迭代子+,上海大学机电工程与自动化学院 雷电,顺序容器:push_back 从尾压入数据 pop_back 从尾弹出数据 front 头数据引用 back 尾数据引用 若序列式 下标访问关联容器 关键字访问,上海大学机电工程与自动化学院 雷电,头文件,使用STL容器或容器适配器，要包含定义该容器模板类头文件。这些头文件的内容都在std名字空间域中，程序中必须加以说明。,上海大学机电工程与自动化学院 雷电,7.3.4 序列式容器 1）vector,矢量（vector）类提供了具有连续内存地址的数据结构。通过下标运算符 直接有效地访问矢量的任何元素。与数组不同，矢量的内存用尽时，矢量自动分配更大的连续内存区，将原先的元素复制到新的内存区，并释放旧的内存区。这是矢量类的优点。在这里内存分配是由分配子（allocator）完成。矢量可以用来实现队列、堆栈、列表和其他更复杂的结构。vector支持随机访问迭代子，具有最强的功能。vector的迭代子通常实现为vector元素的指针。,上海大学机电工程与自动化学院 雷电,优点：不用考虑越界，面向对象，有大量的方法支持各种操作。逻辑结构：构造函数vector()vector(int n)访问方法：*push_back,Insert,0,3,Size=4,上海大学机电工程与自动化学院 雷电,使用向量容器的声明如下：#includevector vi;/定义存放整形序列的向量容器对象vi，长度为0的空vectorvector vf(100);/存放实型序列的向量容器vector vch;/存放字符序列的向量容器vectorvstr;/存放字符串序列的向量容器矢量容器有多种构造函数。包括构造一个有n个元素的矢量，每个元素都是由元素缺省的构造函数所构造出来的，还可以为每个元素用同一个对象来赋初值。还包括拷贝构造函数，可以由一个已有的矢量容器对象来初始化新容器各元素的构造函数。,上海大学机电工程与自动化学院 雷电,7.3.4 序列式容器 2）deque,双端队列（deque）（double-ended queue）类。双端队列允许在队列的两端进行操作。以顺序表为基础，支持随机访问迭代子。双端队列有高度的灵活性，它放松了访问的限制，对象既可从队首进队，也可以从队尾进队，同样也可从任一端出队。除了可从队首和队尾移走对象外，也支持通过使用下标操作符“”进行访问。要增加存储空间时，可以在内存块中对deque两端分别进行分配。并且新分配的存储空间保存为指向这些块的指针数组，这样双端队列可以利用不连续内存空间。因此它的迭代子比vector的迭代子更加智能化。为双端队列分配的存储块，往往要等删除双端队列时才释放，它比重复分配（再分配和释放）更有效，但也更浪费内存。使用双端队列，必须包含头文件。,上海大学机电工程与自动化学院 雷电,逻辑结构：构造函数 deque()deque(int n)访问方法：push_back push_frontpop_back pop_back*,front,back,pop,push,上海大学机电工程与自动化学院 雷电,7.3.4 序列式容器 3）list,列表（list）是由双向链表（doubly linked list）组成的。我们也已经在有关链表的一节中介绍过了，它有两个指针域，可以向前也可以向后进行访问，但不能随机访问，即支持的迭代子类型为双向迭代子。使用起来很方便，与双链表类模板相似，但通用性更好，使用更方便。列表的定义在头文件中。,上海大学机电工程与自动化学院 雷电,逻辑结构：构造函数 list()访问方法：insert*,head,tail,上海大学机电工程与自动化学院 雷电,7.3.6 基本的关联式容器 map,关联容器（associative container）能通过关键字（search key）直接访问(存储和读取元素)。四个关联容器为：集合（set），多重集合（multiset），映射（map）和多重映射（multimap）。映射和多重映射类提供了操作与关键字相关联的映射值（mapped value）的方法。映射和多重映射的主要差别在于多重映射允许存放与映射值相关联的重复关键字，而映射只允许存放与映射值一一对应的单一关键字。多重映射和映射关联容器类用于快速存储和读取关键字与相关值（关键字/数值对，key/value pair）。如果保存学生的简明资料，要求按学号排序，使用映射关联容器（因为不会重号）是最合适的。如用姓名排序，因姓名可能重复，使用多重映射更为合适。使用时要用头文件。,上海大学机电工程与自动化学院 雷电,逻辑结构template class map;,key,value,value_type,pair,上海大学机电工程与自动化学院 雷电,map 使用,头文件#include using namespace std;类型迭代子:iterator,const_iterator map 元素类型：value_type，其定义：typedef pair value_type;template struct pair Type1 first;Type2 second;pair();pair(const Type1,上海大学机电工程与自动化学院 雷电,7.3.9 STL算法,特点：STL算法通过迭代子和模板实现的。通常只关心迭代子，不必知道容器的种类。算法只是间接通过迭代子操作容器元素。一个算法通常可用于多个不同的容器，所以称为泛型算法（generic algorithm）。算法函数中的参数：1）迭代子2）函数指针3）判断谓词4）自定义对象例:对容器中的元素反序。templatevoid reverse Biterator it1,Biterator it2);,上海大学机电工程与自动化学院 雷电,排序 sort#includetemplatevoid sort(It first,It last);(由void sort(It first,It last,Compare comp);例：vector v;.sort(v.begin(),v.end();,上海大学机电工程与自动化学院 雷电,查找 find#includetemplateIt find(It first,It last,const T,上海大学机电工程与自动化学院 雷电,拷贝copy#includetemplateoIt copy(iIt first1,iIt last1,oIt first2);将范围first1,last1)拷贝到first2,last2)。其中：last2=first2+last1-first1例：vector v(3);v0=0;v1=1;v2=2;vector u(3);copy(v.begin(),v.end(),u.begin();,上海大学机电工程与自动化学院 雷电,迭代 for_eachfor_each 比 for 循环是更加整洁，更易于使用，并且不容易意外错误#include template Func for_each(It first,It last,Func func);每次迭代（范围first,last)），取出迭代所指元素，作为参数，调用函数func。例：void dump(int i)cout v(10);for_each(v.begin(),v.end(),dump);,上海大学机电工程与自动化学院 雷电,7.4 示例程序 证券业绩报表,Stockstring symbol;double open;double close;long volume;double getGainLoss()；需求:1.读证券交易数据文件.2.不同排序方法的打印.3.查询解决方案(stockEx.dsw)1.证券交易数据存放在文件中,格式是s,o,c,v.2.采用STL.1).使用fstream读数据文件到STL容器中.2).采用deque 容器3).采用for_each,sort3.Stock类4.CApp类5.main,上海大学机电工程与自动化学院 雷电,C+11（最新正式标准）,auto关键词vector v;for(auto i=v.begin();i!=v.end();+i)code 空指针 nullptrvoid foo(char*);void foo(int);foo(NULL);/?歧义!foo(nullptr);/OK,上海大学机电工程与自动化学院 雷电,Lambda表达式,Lambda 表达式算得上是 C+11 新增特性中最激动人心的一个。同时有函数、类两者的优点，但又不需要预先声明-Lambda表达式(匿名的函数对象)基本特点：1.函数名匿名2.与父作用域数据传递,上海大学机电工程与自动化学院 雷电,Lambda 语法,捕获符(参数表)-返回类型 函数体 函数体可访问所在区域外部变量，由捕获符决定捕获符:不捕获任何外部变量=以值的形式捕获所有外部变量&以引用形式捕获所有外部变量=,x,&y x 以传值形式捕获，y 以引用形式捕获,其余变量以传值形式捕获-返回类型 可省（编译器自动推断）,上海大学机电工程与自动化学院 雷电,Lambda 例子,调用cout f2=(int x,int y)return x+y;int z=f1(1,2);int w=f2(1,2);,上海大学机电工程与自动化学院 雷电,与stl结合使用std:vector someList;int total=0;std:for_each(someList.begin(),someList.end(),上海大学机电工程与自动化学院 雷电,类中使用class Scale private:int _scale;public:Scale(int scale):_scale(scale)void ApplyScale(const vector,上海大学机电工程与自动化学院 雷电,模板中使用template void print_all(const vector,上海大学机电工程与自动化学院 雷电,