《程序设计实习第二十讲标准模板库stli.ppt》由会员分享，可在线阅读，更多相关《程序设计实习第二十讲标准模板库stli.ppt（49页珍藏版）》请在三一办公上搜索。
1、程序设计实习第二十讲 标准模板库 STL I,主讲教师：田永鸿2008年5月19日,2,课堂问题,下列代码是否存在错误，若存在，该如何改正？template class CTempfriend void myClass:func();private:T elementssize;public:CTemp(T arg);template void myClass:func()CTemp a(10);int i;for(i=0;i obj;obj.func();,3,课堂问题,有如下类模板定义 template class CTempfriend myClassA;friend myClassB;
2、private:T1 elementssize;public:CTemp(T arg);则myClassA、myClassB、myClassA、myClassA都是CTemp的友员类,4,课堂问题,找出下列代码中的错误之处，并解释a(10)（或b(8.9)、的含义）template class CTempfriend void func(int);private:T elementssize;public:CTemp(T arg);void func(int size)CTemp a(10);CTemp b(8.9);CTemp c(10);CTemp d(10);int i;for(i=0;
3、i50;i+)couta.elementsi“”b.elementsiendl;return;,5,提纲,1.引言2.STL中的基本概念3.容器概述4.迭代器5.算法简介6.顺序容器,6,概论,C+语言的核心优势之一就是便于软件的重用C+中有两个方面体现重用：1.面向对象的思想：继承和多态，标准类库2.泛型程序设计(generic programming)的思想：模板机制，以及标准模板库 STL,7,泛型程序设计,泛型程序设计，简单地说就是使用模板的程序设计法。将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对
4、象，则都不必重新实现数据结构，重新编写算法。标准模板库(Standard Template Library)就是一些常用数据结构和算法的模板的集合。主要由 Alex Stepanov 开发，于1998年被添加进C+标准有了STL，不必再从头写大多的标准数据结构和算法，并且可获得非常高的性能。,8,STL中的几个基本概念,容器：可容纳各种数据类型的数据结构。迭代器：可依次存取容器中元素的东西算法：用来操作容器中的元素的函数模板。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象。函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数
5、组到高度复杂容器的任何数据结构上使用。比如，数组int array100就是个容器，而 int*类型的指针变量就可以作为迭代器，可以为这个容器编写一个排序的算法,9,容器概述,可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构。容器分为三大类：1)顺序容器 vector：后部插入/删除，直接访问deque：前/后部插入/删除，直接访问list：双向链表，任意位置插入/删除2)关联容器set：快速查找，无重复元素multiset：快速查找，可有重复元素map：一对一映射，无重复元素，基于关键字查找multimap：一对一映射，可有重复元素，基于关键字查找前2者合称为第一类容器 3)容
6、器适配器stack：LIFOqueue：FIFOpriority_queue：优先级高的元素先出,10,容器概述,对象被插入容器中时，被插入的是对象的一个复制品。许多算法，比如排序，查找，要求对容器中的元素进行比较，所以，放入容器的对象所属的类，还应该实现=和 运算符。,11,顺序容器简介,1)vector 头文件 实际上就是个动态数组。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。2)deque 头文件 也是个动态数组，随机存取任何元素都能在常数时间完成(但性能次于vector)。在两端增删元素具有较佳的性能。3)list 头文件 双向链表，在任何位置增删元素都能在常数时
7、间完成。不支持随机存取。上述三种容器称为顺序容器，是因为元素的插入位置同元素的值无关。,12,关联容器简介,关联式容器内的元素是排序的，插入任何元素，都按相应的排序准则来确定其位置。关联式容器的特点是在查找时具有非常好的性能。1)set/multiset:头文件 set 即集合。set中不允许相同元素，multiset中允许存在相同的元素。2)map/multimap:头文件 map与set的不同在于map中存放的是成对的key/value。并根据key对元素进行排序，可快速地根据key来检索元素 map同multimap的不同在于是否允许多个元素有相同的key值。上述4种容器通常以平衡二叉树
8、方式实现，插入和检索的时间都是 O(logN),13,容器适配器简介,1)stack:头文件 栈。是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则2)queue:头文件 队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。按照先进先出的原则。3）priority_queue:头文件 优先级队列。最高优先级元素总是第一个出列,14,容器的共有成员函数,1)所有标准库容器共有的成员函数：相当于按词典顺序比较两个容器大小的运算符：=,=,=,!=empty:判断容器中是否有元素max_size:容器中最多能装多少元素size:容器中元素个数sw
9、ap:交换两个容器的内容,比较两个容器的例子：#include#include class A private:int n;public:friend bool operator v1;std:vector v2;v1.push_back(A(5);v1.push_back(A(1);v2.push_back(A(1);v2.push_back(A(2);v2.push_back(A(3);std:cout(v1 v2);return 0;,输出：0,若两容器长度相同、所有元素相等，则两个容器就相等，否则为不等。若两容器长度不同，但较短容器中所有元素都等于较长容器中对应的元素，则较短容器小于另
10、一个容器若两个容器均不是对方的子序列，则取决于所比较的第一个不等的元素,16,容器的成员函数,2)只在第一类容器中的函数：begin 返回指向容器中第一个元素的迭代器end 返回指向容器中最后一个元素后面的位置的迭代器rbegin 返回指向容器中最后一个元素的迭代器rend 返回指向容器中第一个元素前面的位置的迭代器erase 从容器中删除一个或几个元素clear 从容器中删除所有元素,Head,Tail,begin,rbegin,rend,end,17,迭代器,用于指向第一类容器中的元素。有const 和非 const两种。通过迭代器可以读取它指向的元素，通过非const迭代器还能修改其指向
11、的元素。迭代器用法和指针类似。定义一个容器类的迭代器的方法可以是：容器类名:iterator 变量名;或：容器类名:const_iterator 变量名;访问一个迭代器指向的元素：*迭代器变量名,18,迭代器,迭代器上可以执行+操作,以指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，则迭代器变成past-the-end值。使用一个past-the-end值的迭代器来访问对象是非法的，就好像使用NULL或未初始化的指针一样。,例如：#include#include using namespace std;int main()vector v;/一个存放int元素的向量，一开始
12、里面没有元素v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector:const_iterator i;/常量迭代器for(i=v.begin();i!=v.end();i+)cout*i,;cout endl;,vector:reverse_iterator r;/反向迭代器for(r=v.rbegin();r!=v.rend();r+)cout:iterator j;/非常量迭代器for(j=v.begin();j!=v.end();j+)*j=100;for(i=v.begin();i!=v.end();i+)c
13、out*i,;输出结果：1,2,3,4,4,3,2,1,100,100,100,100,21,迭代器,不同容器上支持的迭代器功能强弱有所不同。容器的迭代器的功能强弱，决定了该容器是否支持STL中的某种算法。例1：只有第一类容器能用迭代器遍历。例2：排序算法需要通过随机迭代器来访问容器中的元素，那么有的容器就不支持排序算法。,22,STL 中的迭代器,STL 中的迭代器按功能由弱到强分为5种：1.输入：Input iterators 提供对数据的只读访问。1.输出：Output iterators 提供对数据的只写访问 2.正向：Forward iterators 提供读写操作，并能一次一个地向
14、前推进迭代器。3.双向：Bidirectional iterators提供读写操作，并能一次一个地向前和向后移动。4.随机访问：Random access iterators提供读写操作，并能在数据中随机移动。编号大的迭代器拥有编号小的迭代器的所有功能，能当作编号小的迭代器使用。,23,不同迭代器所能进行的操作(功能）,所有迭代器：+p,p+输入迭代器：*p,p=p1,p=p1,p!=p1输出迭代器：*p,p=p1正向迭代器：上面全部双向迭代器：上面全部，-p,p-,随机访问迭代器：上面全部，以及：p+=i,p-=i,p+i：返回指向 p 后面的第i个元素的迭代器p-i：返回指向 p 前面的第
15、i个元素的迭代器pi:p 后面的第i个元素的引用p p1,p=p1,24,容器所支持的迭代器类别,容器迭代器类别vector随机deque随机list 双向set/multiset双向map/multimap双向stack不支持迭代器queue不支持迭代器priority_queue不支持迭代器,例如，vector的迭代器是随机迭代器，所以遍历 vector 可以有以下几种做法：vector v(100);vector:value_type i;/等效于写 int i;(P687)for(i=0;i:const_iterator ii;for(ii=v.begin();ii!=v.end();
16、ii+)cout*ii;/间隔一个输出：ii=v.begin();while(ii v.end()cout*ii;ii=ii+2;,而 list 的迭代器是双向迭代器，所以以下代码可以：list v;list:const_iterator ii;for(ii=v.begin();ii！v.end();ii+)cout*ii;以下代码则不行：for(ii=v.begin();ii v.end();ii+)cout*ii;/双向迭代器不支持 for(int i=0;i v.size();i+)cout vi;/双向迭代器不支持,27,算法简介,STL中提供能在各种容器中通用的算法，比如插入，删除，
17、查找，排序等。大约有70种标准算法。算法就是一个个函数模板。算法通过迭代器来操纵容器中的元素。许多算法需要两个参数，一个是起始元素的迭代器，一个是终止元素的后面一个元素的迭代器。比如，排序和查找有的算法返回一个迭代器。比如 find()算法，在容器中查找一个元素，并返回一个指向该元素的迭代器。算法可以处理容器，也可以处理C语言的数组,28,算法分类,变化序列算法copy,remove,fill,replace,random_shuffle,swap,.会改变容器非变化序列算法：adjacent-find,equal,mismatch,find,count,search,count_if,for
18、_each,search_n以上函数模板都在 中定义V2,P692（V5,P834）此外还有其他算法，比如中的算法,29,算法示例：find(),templateInIt find(InIt first,InIt last,const T first 和 last 这两个参数都是容器的迭代器，它们给出了容器中的查找区间起点和终点。这个区间是个左闭右开的区间，即区间的起点是位于查找范围之中的，而终点不是val参数是要查找的元素的值函数返回值是一个迭代器。如果找到，则该迭代器指向被找到的元素。如果找不到，则该迭代器指向查找区间终点。,#include#include#include using n
19、amespace std;main()int array10=10,20,30,40;vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector:iterator p;p=find(v.begin(),v.end(),3);if(p!=v.end()cout*p endl;,p=find(v.begin(),v.end(),9);if(p=v.end()cout not found endl;p=find(v.begin()+1,v.end()-2,1);if(p!=v.end()cout*p endl
20、;int*pp=find(array,array+4,20);cout*pp endl;输出：3not found320,32,顺序容器,除前述共同操作外，顺序容器还有以下共同操作：front():返回容器中第一个元素的引用back():返回容器中最后一个元素的引用push_back():在容器末尾增加新元素pop_back():删除容器末尾的元素比如，查 list:front 的help,得到的定义是：reference front();const_reference front()const;list有两个front函数,33,顺序容器,reference和 const_reference
21、 是typedef的类型，含义见P687对于 list,list:reference 实际上就是 double&list:const_reference 实际上就是 const double&对于 list,list:refrence 实际上就是 int&list:const_refreence 实际上就是 const int&,34,vector,支持随机访问迭代器，所有STL算法都能对vector操作。随机访问时间为常数。在尾部添加速度很快，在中间插入慢。实际上就是动态数组。,例1：int main()int i;int a5=1,2,3,4,5;vector v(5);cout v2(a
22、,a+5);/构造函数v2.insert(v2.begin()+2,13);/在begin()+2位置插入 13for(i=0;i v2.size();i+)cout v2i,;return 0;,输出：50,1,2,3,100,1,2,13,3,4,5,例2：int main()const int SIZE=5;int aSIZE=1,2,3,4,5;vector v(a,a+5);/构造函数try v.at(100)=7;catch(out_of_range e)cout output(cout,“*);copy(v.begin(),v.end(),output);v.erase(v.be
23、gin(),v.end();/等效于 v.clear();,if(v.empty()cout subscript1,52*3*4*5*empty1*2*3*4*5*,39,算法解释,ostream_iterator output(cout,“*);定义了一个 ostream_iterator 对象，可以通过cout输出以*分隔的一个个整数copy(v.begin(),v.end(),output);导致v的内容在 cout上输出copy 函数模板(算法）：template OutIt copy(InIt first,InIt last,OutIt x);本函数对每个在区间0,last-firs
24、t)中的N执行一次*(x+N)=*(first+N)，返回 x+N对于copy(v.begin(),v.end(),output);first 和 last 的类型是 vector:const_iteratoroutput 的类型是 ostream_iterator,关于 ostream_iterator,istream_iterator的例子int main()istream_iterator inputInt(cin);int n1,n2;n1=*inputInt;/读入 n1inputInt+;n2=*inputInt;/读入 n2cout outputInt(cout);*output
25、Int=n1+n2;cout endl;int a5=1,2,3,4,5;copy(a,a+5,outputInt);/输出整个数组 return 0;,41,程序运行后输入 78 90敲回车，则输出结果为：78,9016812345,42,list 容器,在任何位置插入删除都是常数时间，不支持随机存取。除了具有所有顺序容器都有的成员函数以外，还支持8个成员函数：push_front:在前面插入pop_front:删除前面的元素sort:排序(list 不支持STL 的算法sort)remove:删除和指定值相等的所有元素unique:删除所有和前一个元素相同的元素merge:合并两个链表，并
26、清空被合并的那个reverse:颠倒链表splice:在指定位置前面插入另一链表中的一个或多个元素,并在另一链表中删除被插入的元素,#include#include#include using std:list;using std:ostream;using std:cout;using std:endl;class A private:int n;public:A(int n_)n=n_;friend bool operator(const A,bool operatorvoid PrintList(const std:list,int main()list lst1,lst2;lst1.p
27、ush_back(1);lst1.push_back(3);lst1.push_back(2);lst1.push_back(4);lst1.push_back(2);lst2.push_back(10);lst2.push_front(20);lst2.push_back(30);lst2.push_back(30);lst2.push_back(30);lst2.push_front(40);lst2.push_back(40);cout 1);PrintList(lst1);cout endl;cout 2);PrintList(lst2);cout endl;lst2.sort();c
28、out 3);PrintList(lst2);cout endl;lst2.pop_front();cout 4);PrintList(lst2);cout endl;lst1.remove(2);/删除所有和A(2)相等的元素cout 5);PrintList(lst1);cout endl;lst2.unique();/删除所有和前一个元素相等的元素,cout:iterator p1,p2,p3;p1=std:find(lst1.begin(),lst1.end(),3);p2=std:find(lst2.begin(),lst2.end(),200);p3=std:find(lst2.b
29、egin(),lst2.end(),400);lst1.splice(p1,lst2,p2,p3);/将p2,p3)插入p1之前，/并从lst2中删除p2,p3)cout 11);PrintList(lst1);cout endl;cout 12);PrintList(lst2);cout endl;return 0;,47,输出：,1)1,3,2,4,2,2)40,20,10,30,30,30,40,3)10,20,30,30,30,40,40,4)20,30,30,30,40,40,5)1,3,4,6)20,30,40,7)1,3,4,20,30,40,8)9)40,30,20,4,3,1,11)40,30,20,4,200,300,3,1,12)100,400,48,deque 容器,所有适用于vector的操作都适用于dequedeque还有push_front（将元素插入到前面）和pop_front(删除最前面的元素）操作,49,作业,1.阅读V2版P757 的自测练习及答案;2.完成V2版P758 的20.14.3.上周的作业,
