ACM竞赛中STL的应用课件.ppt

《ACM竞赛中STL的应用课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、在ACM竞赛中的应用STLACMMatrix_68目录泛型程序设计简介与迭代器的介绍常见的STL容器及其成员函数相关例题解析123泛型程序设计泛型程序设计，简单地说就是使用模板的程序设计法。将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。标准模板库(StandardTemplateLibrary)就是一些常用数据结构和算法的模板的集合。主要由AlexStepanov开发，于1998年被添加

2、进C++标准有了STL，不必再从头写大多的标准数据结构和算法，并且可获得非常高的性能。迭代器（iterator）可遍历STL容器内全部或部分元素的对象指出容器中的一个特定位置所有容器都提供获得迭代器的函数begin()end()半开区间[beg,end)的好处：1.为遍历元素时循环的结束时机提供了简单的判断依据（只要未到达end()，循环就可以继续）2.不必对空区间采取特殊处理（空区间的begin()就等于end()）常见的STL容器及其函数所有标准库共有成员函数Sort例题1：UVA10474WhereistheM

3、arble题目：题目意思就是给出两个数m和n下面输入m个数，再依次输入n个数，查找n个数在前面的m个数中是第几大思路很简单，排序加查找（也可以二分优化）。这里简述sort函数的用法头文件：格式：sort(vect.begin(),vect.end());sort(vect.begin(),vect.end(),less());第三个参数可以自定义，主要用于自定义类型的排序常见的STL容器STL容器类别序列式容器－排列次序取决于插入时机和位置关联式容器－排列顺序取决于特定准则listde

4、quevector序列式容器mapset关联式容器9序列式容器序列式容器顺序容器包含Vector，deque和list三种容器，其中vector和deque属于直接访问容器，list属于顺序访问容器。向量（vector）向量相当于一个动态数组，其可以动态存储元素，并提供对容器元素的随机访问。为了提高效率，vector并不是随着每一个元素的插入而增长自己，而是当vector要增长自己的时候，他分配的空间比当前所需的空间要多一些。这多一些的内存空间使需要添加新元素的时候不必再重新分配内存。与C++的内置数组相比较，除了动

5、态之外，向量容器支持向对象。常见的STL容器Vector（不定长数组）用法：vector<类型>名字;例如vectorve;vectorve;自己定义的结构体什么的也可以往里塞structPOINT{intx,y;};vectorve;基本操作ve.push_back(constvalue_type&val);作用是在数组后面增加一个元素。括号里填的是ve里装的东西ve.clear();清空ve里的所有元素。ve.empty();判断ve是否为空，如果是返回true，否则fal

6、seve.size();返回ve的长度。注意这里返回的类型是unsignedint,如果ve是空的ve.size()-1就会爆掉。使用的时候一定要小心（做TC的时候被坑了一次）ve.pop_back()删除数组里的最后一个元素。Vector（不定长数组）例题2：UVA101TheBlocksProblem题目：给你n个方块，有四种操作：1.moveaontob，把a和b上面的方块都放回原来位置，然后把a放到b上面；2.moveaoverb，把a上面的放回原处，然后把a放在b所在的方块堆的上面；3.pileaontob

7、，把b上面的放回原来位置，然后把a和a上面的方块整体放到b上面；4.pileaoverb，把a和a上面的方块整体放到b所在堆的上面。定义两个基本操作：1.将a上面的还原init_place(a)；2.将a和上面的（可以没有上面的）放到b上面pile_a_to_b(a,b)。那么上述的四组操作就变成下面了：1.moveaontob，init_place(a)；init_place(b)；pile_a_to_b(a,b)；2.moveaoverb，init_place(a)；pile_a_to_b(a,b)；3.pile

8、aontob，init_place(b)；pile_a_to_b(a,b)；4.pileaoverb，pile_a_to_b(a,b)。12关联式容器关联式容器包括set,multiset,map,multimap，内部元素有序排列，新元素插入的位置取决于它的值，查找速度快。关联容器是通过键(key)存储和读取元素的而顺序容器则通过元素在容器中