三十分钟掌握STL-教程

三十分钟掌握三十分钟掌握STL-教程教程

三十分钟掌握STL-教程

三十分钟掌握STL 这是本小人书。原名是《using stl》，不知道是谁写的。不过我倒觉得很有趣，所以化了两个晚上把它翻译出来。我没有对翻译出来的内容校验过。如果你没法在三十分钟内觉得有所

收获，那么赶紧扔了它。文中我省略了很多东西。心疼那，浪费我两个晚上。 译者：kary contact:karymay@163.net STL概述 STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但

这种分离确实使得STL变得非常通用。例如，由于STL的sort()函数是完全通用的，你可以用它来操作几乎任何数据集合，包括链表，容器和数组。 要点 STL算法作为模板函数提供。为了和其他组件相区

别，在本书中STL算法以后接一对圆括弧的方式表示，例如sort()。 STL另一个重要特性是它不是面向对象的。为了具有足够通用性，STL主要依赖于模板而不是封装，继承和虚函数（多态性）——OOP

的三个要素。你在STL中找不到任何明显的类继承关系。这好像是一种倒退，但这正好是使得STL的组件具有广泛通用性的底层特征。另外，由于STL是基于模板，内联函数的使用使得生成的代码短小高

效。 提示 确保在编译使用了STL的程序中至少要使用-O优化来保证内联扩展。STL提供了大量的模板类和函数，可以在OOP和常规编程中使用。所有的STL的大约50个算法都是完全通用的，而且不依赖

文件。该表并不完整，对于其他头文件，我将在本章和后面的两章中介绍。 表 1. STL头文件和容器

类 #include Container Class <deque> deque <list> list <map> map, multimap <queue> queue, priority_queue <set> set, multiset <stack> stack <vector> vector, vector<bool> 名字空间 你的编译器可能

不能识别名字空间。名字空间就好像一个信封，将标志符封装在另一个名字中。标志符只在名字空间中存在，因而避免了和其他标志符冲突。例如，可能有其他库和程序模块定义了sort()函数，为了避免

和STL地sort()算法冲突，STL的sort()以及其他标志符都封装在名字空间std中。STL的sort()算法编译为std::sort()，从而避免了名字冲突。 尽管你的编译器可能没有实现名字空间，你仍然可以使用他们。

为了使用STL，可以将下面的指示符插入到你的源代码文件中，典型地是在所有的#include指示符的后面： using namespace std; 迭代器 迭代器提供对一个容器中的对象的访问方法，并且定义了容器中

对象的范围。迭代器就如同一个指针。事实上，C++的指针也是一种迭代器。但是，迭代器不仅仅是指针，因此你不能认为他们一定具有地址值。例如，一个数组索引，也可以认为是一种迭代器。 迭代

器有各种不同的创建方法。程序可能把迭代器作为一个变量创建。一个STL容器类可能为了使用一个特定类型的数据而创建一个迭代器。作为指针，必须能够使用*操作符类获取数据。你还可以使用其他

数学操作符如++。典型的，++操作符用来递增迭代器，以访问容器中的下一个对象。如果迭代器到达了容器中的最后一个元素的后面，则迭代器变成past-the-end值。使用一个past-the-end值得指针来

访问对象是非法的，就好像使用NULL或为初始化的指针一样。 提示 STL不保证可以从另一个迭代器来抵达一个迭代器。例如，当对一个集合中的对象排序时，如果你在不同的结构中指定了两个迭代

器，第二个迭代器无法从第一个迭代器抵达，此时程序注定要失败。这是STL灵活性的一个代价。STL不保证检测毫无道理的错误。 迭代器的类型 对于STL数据结构和算法，你可以使用五种迭代器。下

#include <algorithm>

using namespace std;

#define SIZE 100

int iarray[SIZE];

int main()

{

iarray[20] = 50;

int* ip = find(iarray, iarray + SIZE, 50);

if (ip == iarray + SIZE)

cout << "50 not found in array" << endl;

iarray[20] = 50;

int* ip = find(iarray, iarray + SIZE, 50);

find()函数接受三个参数。头两个定义了搜索的范围。由于C和C++数组等同于指针，表达式iarray指向数组的第一个元素。而第二个参数iarray + SIZE等同于past-the-end 值，也就是数组中最后一个元素

的后面位置。第三个参数是待定位的值，也就是50。find()函数返回和前两个参数相同类型的迭代器，这儿是一个指向整数的指针ip。 提示 必须记住STL使用模板。因此，STL函数自动根据它们使用的数

据类型来构造。 为了判断find()是否成功，例子中测试ip和 past-the-end 值是否相等：

if (ip == iarray + SIZE) ...

如果表达式为真，则表示在搜索的范围内没有指定的值。否则就是指向一个合法对象的指针，这时可以用下面的语句显示：:

cout << *ip << " found in array" << endl;

测试函数返回值和NULL是否相等是不正确的。不要象下面这样使用：

int* ip = find(iarray, iarray + SIZE, 50);

#include <algorithm>

#include <vector>

using namespace std;

vector<int> intVector(100);

void main()

{

intVector[20] = 50;

vector<int>::iterator intIter =

find(intVector.begin(), intVector.end(), 50);

if (intIter != intVector.end())

常量迭代器 和指针一样，你可以给一个迭代器赋值。例如，首先申明一个迭代器：

vector<int>::iterator first;

该语句创建了一个vector<int>类的迭代器。下面的语句将该迭代器设置到intVector的第一个对象，并将它指向的对象值设置为123：:

first = intVector.begin();

*first = 123;

这种赋值对于大多数容器类都是允许的，除了只读变量。为了防止错误赋值，可以申明迭代器为：

const vector<int>::iterator result;

result = find(intVector.begin(), intVector.end(), value);

if (result != intVector.end())

*result = 123; // ???

InputIterator first, InputIterator last, const T& value) {

while (first != last && *first != value) ++first;

return first;

}

注意 在find()算法中，注意如果first和last指向不同的容器，该算法可能陷入死循环。 输出迭代器 输出迭代器缺省只写，通常用于将数据从一个位置拷贝到另一个位置。由于输出迭代器无法读取对象，因

此你不会在任何搜索和其他算法中使用它。要想读取一个拷贝的值，必须使用另一个输入迭代器（或它的继承迭代器）。 Listing 3. outiter.cpp

#include <iostream.h>

#include <algorithm> // Need copy()

#include <vector> // Need vector

using namespace std;