ACM程序设计(第2版)
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

第2章 C++STL泛型编 程

2.1 C++STL概述

在ACM竞赛中，需要用到数组、字符串、队列、堆栈、链表、平衡二叉检索树等数据结构和排序、搜索等算法，以提高程序的时间、空间运行效率。这些数据结构，如果都需要手工来编写，那是相当麻烦的事情。

幸运的是，ANSI C++中包含了一个C++ STL（Standard Template Library），即C++标准模板库，又称C++泛型库，它在std命名空间中定义了常用的数据结构和算法，使用起来十分方便。

2.1.1 C++STL的实现版本

C++STL的实现版本主要有HP STL、SGI STL、STLport、P.J.Plauger STL和Rouge Wave STL等五种。

HP STL是Alexandar Stepanov（1950年生于莫斯科，被称为STL之父）在惠普Palo Alto实验室工作时，与Meng Lee合作完成的，它是C++STL的第一个实现版本，而且是开放源码，其他版本的C++STL，一般是以HP STL为蓝本来实现的。

SGI STL是由Silicon Graphics Computer Systems公司参照HP STL实现的，主要设计者仍然是Alexandar Stepanov，被Linux的C++编译器GCC所采用。SGI STL是开源软件，可以在http://www.sgi.com/网站上下载。

STLport是俄国人Boris Fomitchev建立的一个free项目，它是开放源码的，主要目的是使SGI STL的基本代码都适用于VC++和C++Builder等多种编译器，源码可以在http://www.stlport.com/ 网站上下载。

P.J.Plauger STL是由P.J.Plauger参照HP STL实现的，被Visual C++编译器所采用，它不是开源的。头文件在C:\Program Files\Microsoft Visual Studio\VC98\Include文件夹下，文件名不带“.h”。

Rouge Wave STL是Rouge Wave公司参照HP STL实现的，用于Borland C++编译器中，当然，它也不是开源的。

2.1.2 C++STL组件

STL提供三种类型的组件：容器、迭代器和算法，它们都支持泛型程序设计标准。

容器主要有两类：顺序容器和关联容器。顺序容器（vector、list、deque和string等）是一系列元素的有序集合。关联容器（set、multiset、map和multimap）包含查找元素的键值。

迭代器的作用是遍历容器。

STL算法库包含四类算法：排序算法、不可变序算法、变序性算法和数值算法。

2.1.3 C++STL泛型编程示例

用vector向量容器装入10个整数，然后，使用迭代器iterator和accumulate算法统计出这10个元素的和。

采用VC++6.0编制的泛型程序如下：

        #include "stdafx.h"
        //cin和cout需要
        #include <iostream>
        //向量需要
        #include <vector>
        //accumulate算法需要
        #include <numeric>
        using namespace std;

       int main(int argc, char * argv[])
        {
          //定义向量v
          vector<int> v;
          int i;
          //赋值
          for(i=0; i<10; i++)
          {
              //尾部元素扩张方式赋值
              v.push_back(i);
          }
          //使用iterator迭代器顺序遍历所有元素
          for(vector<int>::iterator it=v.begin(); it! =v.end(); it++)
          {
              //输出迭代器当前位置上的元素值
              cout<<*it<<" ";
          }
          cout<<endl; //回车换行
          //统计并输出向量所有元素的和
          cout<<accumulate(v.begin(), v.end(),0)<<endl;
          return 0;
        }

程序运行后的结果如图2-1所示。

图2-1 程序运行结果

2.1.4 VC++ 6.0泛型编程

在Microsoft Visual C++ 6.0中，C++STL泛型头文件在C:\Program Files\Microsoft Visual Studio\VC98\Include文件夹下，文件名中不带“.h”的文件都是，如图2-2所示。

图2-2 VC++ 6.0中的C++STL泛型头文件

如果要使用vector向量容器，那么，只需要在程序中加入“#include <vector>”头文件包含语句即可。这里的vector就是指C:\Program Files\Microsoft Visual Studio\VC98\Include\vector文件。其他的C++STL容器、算法都是这样使用。

C++STL泛型都定义在std命名空间中，所以，必须在头文件声明的最后加上一句“using namespace std;”。

另外，1.2节也曾提到过，Visual Studio .NET 2008的C++头文件在C:\Program Files\Microsoft Visual Studio 9.0\VC\Include文件夹中。

如果使用Visual Studio .NET 2008的VC++来编写Win32控制台程序，那么，C++STL头文件包含语句和“using namespace std;”语句需要写在stdafx.h文件里，否则，会出现编译错误。

本章接下来详细介绍C++STL各种常用的容器、迭代器和算法。

上一章目录下一章