算法与程序设计竞赛 第五章 stl

《算法与程序设计竞赛 第五章 stl》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章STL专题古云：工欲善其事、必先利其器C++中的STLSTL(StandardTemplateLibrary，标准模板库）是C++语言标准中的重要组成部分。STL以模板类和模板函数的形式为程序员提供了各种数据结构和算法的精巧实现，程序员如果能够充分地利用STL，可以在代码空间、执行时间和编码效率上获得极大的好处。STL大致可以分为三大类：算法(algorithm)、容器(container)、迭代器(iterator)。STL容器是一些模板类，提供了多种组织数据的常用方法，例如vector(向量，类似于数组)、list(列表，类似于链表)、deque(双

2、向队列)、set(集合)、map(映象)、stack(栈)、queue(队列)、priority_queue(优先队列)等，通过模板的参数我们可以指定容器中的元素类型。STL算法是一些模板函数，提供了相当多的有用算法和操作，从简单如for_each（遍历）到复杂如stable_sort（稳定排序）。STL迭代器是对C中的指针的一般化，用来将算法和容器联系起来。几乎所有的STL算法都是通过迭代器来存取元素序列进行工作的，而STL中的每一个容器也都定义了其本身所专有的迭代器，用以存取容器中的元素。有趣的是，普通的指针也可以像迭代器一样工作。熟悉了STL后，你会发现

3、，很多功能只需要用短短的几行就可以实现了。通过STL，我们可以构造出优雅而且高效的代码，甚至比你自己手工实现的代码效果还要好。STL的另外一个特点是，它是以源码方式免费提供的，程序员不仅可以自由地使用这些代码，也可以学习其源码，甚至按照自己的需要去修改它。使用STL在C++标准中，STL被组织为以下的一组头文件（注意，是没有.h后缀的！）：algorithm/deque/functional/iterator/list/mapmemory/numeric/queue/set/stack/utility/vector当我们需要使用STL的某个功能时，需要嵌入相应

4、的头文件。但要注意的是，在C++标准中，STL是被定义在std命名空间中的。如下例所示：#includemain(){    std::stacks;    s.push(0);    ...    return1;}如果希望在程序中直接引用STL，也可以在嵌入头文件后，用usingnamespace语句将std命名空间导入。如下例所示：#includeusingnamespacestd;STL之一:pairSTL的头文件中描述了一个看上去非常简单的模板类pair，用来表示

5、一个二元组或元素对，并提供了按照字典序对元素对进行大小比较的比较运算符模板函数。例如，想要定义一个对象表示一个平面坐标点，则可以：pairp1;cin>>p1.first>>p1.second;pair模板类需要两个参数：首元素的数据类型和尾元素的数据类型。pair模板类对象有两个成员：first和second，分别表示首元素和尾元素。在中已经定义了pair上的六个比较运算符：<、>、<=、>=、==、!=，其规则是先比较first，first相等时再比较second，这符合大多数应用的逻辑。当然，也可以通过重

6、载这几个运算符来重新指定自己的比较逻辑。除了直接定义一个pair对象外，如果需要即时生成一个pair对象，也可以调用在中定义的一个模板函数：make_pair。make_pair需要两个参数，分别为元素对的首元素和尾元素。STL之二：vector在STL的头文件中定义了vector（向量容器模板类），vector容器以连续数组的方式存储元素序列，可以将vector看作是以顺序结构实现的线性表。当我们在程序中需要使用动态数组时，vector将会是理想的选择，vector可以在使用过程中动态地增长存储空间。vector模板类需要两

7、个模板参数，第一个参数是存储元素的数据类型，第二个参数是存储分配器的类型，其中第二个参数是可选的，如果不给出第二个参数，将使用默认的分配器。下面给出几个常用的定义vector向量对象的方法示例：vectors;定义一个空的vector对象，存储的是int类型的元素。vectors(n);定义一个含有n个int元素的vector对象。vectors(first,last);定义一个vector对象，并从由迭代器first和last定义的序列[first,last)中复制初值。vector的基本操作有：s[i]直接以下标方式访问容器中

8、的元素。s.front()返回首元素。