《STL库介绍与练习.ppt》由会员分享，可在线阅读，更多相关《STL库介绍与练习.ppt（41页珍藏版）》请在三一办公上搜索。
1、STL库介绍与练习,标准模板库（英文：Standard Template Library，缩写：STL），是一个C+软件库，也是C+标准程序库的一部分。模板是C+程序设计语言的一个比较新的重要特征，而标准模板库正是基于此特征。标准模板库使得C+编程语言在有了同Java一样强大的类库的同时，保有了更大的可扩展性。,什么是STL,STL是 C+的ANSI/ISO 标准的一部分,可以用于所有C+语言编译器和所有平台(Windows/Unix/Linux.)。STL的同一版本在任意硬件配置下都是可用的；STL 提供了大量的可复用软件组织。例如，程序员再也不用自己设计排序，搜索算法了，这些都已经是STL
2、的一部分了。嘎嘎，有意思吧。使用STL 的应用程序保证了得到的实现在处理速度和内存利用方面都是高效的，因为STL设计者们已经为我们考虑好了。使用STL编写的代码更容易修改和阅读，这是当然的啦。因为代码更短了，很多基础工作代码已经被组件化了；使用简单，虽然内部实现很复杂。虽然，STL的优点甚多，但是STL的语法实在令初学者人头疼，许多人望而却步。可是STL是每个C+程序设计者迟早都要啃的一块骨头。,为什么要使用STL,容器：可容纳各种数据类型的数据结构。迭代器：可依次存取容器中元素的东西算法：用来操作容器中的元素的函数模板。例如，STL用sort()来对一个vector中的数据进行排序，用fin
3、d()来搜索一个list中的对象。函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。比如，数组int array100就是个容器，而 int*类型的指针变量就可以作为迭代器，可以为这个容器编写一个排序的算法,STL 的组成,可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构。容器分为三大类：1)顺序容器 vector：后部插入/删除，直接访问deque：前/后部插入/删除，直接访问list：双向链表，任意位置插入/删除2)关联容器set：快速查找，无重复元素multiset：快速查找，可有重复元素map：一对一映射，无重复元素，基
4、于关键字查找multimap：一对一映射，可有重复元素，基于关键字查找前2者合称为第一类容器 3)容器适配器stack：LIFOqueue：FIFOpriority_queue：优先级高的元素先出,容器概述,对象被插入容器中时，被插入的是对象的一个复制品。许多算法，比如排序，查找，要求对容器中的元素进行比较，所以，放入容器的对象所属的类，还应该实现=和 运算符。,容器概述,常用举例,min max swap 的使用sort 的使用vector 的使用map 的使用set 的使用stack的使用queue的使用priority_queue的使用,#include#include#include#
5、includeusing namespace std;int main()int a=2,b=3;printf(%d%dn,max(a,b),min(a,b);swap(a,b);printf(%d%dn,a,b);system(pause);结果输出：3 23 2,min max swap 的使用,对数组使用sort排序，输入8 5 1 6 9#include#include#include#includeusing namespace std;int main()int a5;for(int i=0;i5;+i)scanf(%d,结果输出：1 5 6 8 9,sort 的使用,二级排序，坐
6、标排序，输入(2,3)(4,2)(1,7)(2,4)优先按x小的排序，x一样按y小的排序struct nodeint x,y;p4;bool cmp(node a,node b)if(a.x=b.x)return a.yb.y;return a.xb.x;,sort 的使用,sort 的使用,int main()for(int i=0;i4;+i)scanf(%d%d,结果输出：1 72 32 44 2,Int a=1,2,4,6;next_permutation(a,a+4)prev_permutation(a,a+4)sort(a,a+4)reverse(a,a+4)lower_bound
7、 返回大于等于指定元素的位置upper_bound 返回大于指定元素的位置Int a=1,2,4,6;Int ind=Lower_bound(a,a+4,4)-a;,其它常见算法,相当于数组，常用的添加、删除、清空、测长操作#include#include#include#includeusing namespace std;int main()vector a;for(int i=0;i5;+i)a.push_back(i);/把元素i按顺序放到a里 for(int i=0;ia.size();+i)/a.size()测量a的元素个数 printf(%d,ai);,vector 的使用,pu
8、ts();/vector容器指针指向第一个元素 vector:iterator it=a.begin();a.erase(it+2);/删除第三个 for(int i=0;ia.size();+i)printf(%d,ai);system(pause);结果输出：0 1 2 3 40 1 3 4,vector 的使用,对杂乱无序的字符串或数字做哈希匹配，可以重新编号，输入一些英文名字，给他们编号#include#include#include#includeusing namespace std;int main()map mp;string nm=abc,david,lucy,abc,app
9、,lucy;int index=1;for(int i=0;i6;+i)if(mpnmi=0)mpnmi=index+;/判断是否已经出现过，没出现过，就编号,map 的使用,map:iterator it;/map容器的指针 for(it=mp.begin();it!=mp.end();+it)coutfirstsecondendl;/按字典序输出每个的编号 system(pause);结果输出：abc 1app 4david 2lucy 3,map 的使用,set可以插入很多值，去掉重复元素，并可以查找#include#include#include#includeusing namesp
10、ace std;int main()set st;string nm=abc,david,lucy,abc,app,lucy;for(int i=0;i:iterator it;/set容器的指针 for(it=st.begin();it!=st.end();+it)cout*itendl;/按字典序输出 it=st.find(app);if(it!=st.end()cout find app endl;else cout cant find app endl;,set 的使用,/找到了就输出find，找不到就输出cant findit=st.find(bld);if(it!=st.end()
11、cout:iterator it=st.lower_bound(dad);it!=st.end();+it)cout*it;cout endl;结果输出：abcappdavidlucyfind appcant find blddavid lucy,set 的使用,stack几个主要函数：empty()堆栈为空则返回真pop()移除栈顶元素（不会返回栈顶元素的值）push()在栈顶增加size()返回栈中元素数目top()返回栈顶元素,stack的使用,例子：#include#include#include#includeusing namespace std;int main()int a=1
12、,3,5,7,9,11;stack st;int i;if(st.empty()for(i=0;i3;+i)st.push(ai);,stack的使用,stack的使用,for(int i=0;i2;+i)printf(%d,st.top();st.pop();printf(n);for(int i=3;i6;+i)st.push(ai);printf(The size of stack is%dn,st.size();int n=st.size();for(int i=0;in;+i)printf(%d,st.top();st.pop();printf(n);system(pause);,输
13、出结果：5 3The size of stack is 411 9 7 1请按任意键继续.,queue几个主要函数：empty()队列为空则返回真pop()移除队首元素push()在队尾增加元素size()返回队列元素数目front()返回队首元素back()返回队尾元素,queue的使用,例子：#include#include#include#includeusing namespace std;int main()int a=1,3,5,7,9,11;queue qu;int i;if(qu.empty()for(i=0;i3;+i)qu.push(ai);,queue的使用,printf
14、(Front is%d and Back is%dn,qu.front(),qu.back();for(int i=0;i2;+i)qu.pop();printf(Front is%d and Back is%dn,qu.front(),qu.back();for(int i=3;i6;+i)qu.push(ai);printf(The size of queue is%dn,qu.size();int n=qu.size();printf(Front is%d and Back is%dn,qu.front(),qu.back();for(int i=0;in-1;+i)qu.pop();p
15、rintf(Front is%d and Back is%dn,qu.front(),qu.back();system(pause);,queue的使用,输出结果：Front is 1 and Back is 5Front is 3 and Back is 5Front is 5 and Back is 5The size of queue is 4Front is 5 and Back is 11Front is 7 and Back is 11Front is 9 and Back is 11Front is 11 and Back is 11请按任意键继续.,queue的使用,stack
16、 和 queue 用法很相似不过原理不一样，前者是先进后出，后者是先进先出stack和queue的类型除了int,double,float等外，也可以也struct形式比如：struct node int x,y;a6;queue qu;,stack 简介,STL标准容器类简介,所有标准库共有函数,顺序容器和关联容器共有函数,#include#include#include using namespace std;#define out(x)(std:cerr q;q.push(3);q.push(2);out(q.top();out(q.top();out(q.size();输出结果：Lin
17、e 12:q.top():3Line 13:q.top():3Line 14:q.size():2,30,priority_queue,struct point int x,y;point(int xx,int yy):x(xx),y(yy);bool operator(const point,运算符重载,大家做一下,POJ 2442,#include#include using namespace std;int main()int a,b;while(2=scanf(%d%d,A,#include#include using namespace std;int a1000000;int m
18、ain()int cas,n;scanf(%d,H,#include#include using namespace std;char tmp65535;int main()while(gets(tmp)for(int i=0,c=0;tmpi;+i)if(tmpi=()+c;else if(tmpi=)-c;else if(tmpi=B)printf(%dn,c);break;return 0;,K,#include#include int main()int n,i,j,k,t,r23,stack13;char si13,so13;while(1=scanf(%d,M,#include#i
19、nclude#include#include#include using namespace std;#define out(x)(std:cerr b.x;return a.y b.y;,POJ 2442,int main()int t,m,n;scanf(%d,POJ 2442,int pt=0;while(pt n)Elem pr=st.top();st.pop();tmp+pt=pr.x;pospr.y+;st.push(Elem(anspr.y+numpospr.y,pr.y);for(int j=1;j=n;j+)ansj=tmpj;for(int i=1;i=n;i+)printf(%d%c,ansi,i=n?n:);return 0;,POJ 2442,对于上述讲的sort,vector,map,set,stack,queue其实还有很多其他功能，刚才只是介绍了些ACM竞赛上常用的操作，使用STL的模板库能使得代码简洁，易实现，正确性高，但同时STL实现的效率也比自己写的函数稍慢些。STL是把很多强大的数据结构函数写成了模板，会使用固然重要，但也得打好基础，先把数据结构学好，不能滥用，不然对提高编程没什么好处，尤其对ACM竞赛来说。实践的重要性。,总结,谢谢！,
