《三十分钟掌握stl》由会员分享，可在线阅读，更多相关《三十分钟掌握stl（23页珍藏版）》请在金锄头文库上搜索。
1、三十分钟掌握 STL 译者：kary 电子书制作：冷寒生 contact: 这是本小人书。原名是using stl，不知道是谁写的。不过我倒觉得很有趣，所以化了两个晚上把它翻译出来。我没有对翻译出来的内容校验过。如果你没法在三十分钟内觉得有所收获，那么赶紧扔了它。文中我省略了很多东西。心疼那，浪费我两个晚上。 STL 概述 STL 的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但这种分离确实使得 STL 变得非常通用。例如，由于 STL 的 sort()函数是完全通用的，你可以用它来操作几乎任何数据集合，包括链表，容器和数组。 要点 STL 算法作为模板函数提供。为了和其他组件相
2、区别，在本书中 STL 算法以后接一对圆括弧的方式表示，例如 sort()。 STL 另一个重要特性是它不是面向对象的。 为了具有足够通用性，STL 主要依赖于模板而不是封装，继承和虚函数（多态性）OOP 的三个要素。你在 STL 中找不到任何明显的类继承关系。这好像是一种倒退，但这正好是使得 STL 的组件具有广泛通用性的底层特征。另外，由于 STL 是基于模板，内联函数的使用使得生成的代码短小高效。 提示 确保在编译使用了 STL 的程序中至少要使用-O 优化来保证内联扩展。STL 提供了大量的模板类和函数，可以在 OOP和常规编程中使用。所有的 STL 的大约 50 个算法都是完全通用的
3、，而且不依赖于任何特定的数据类型。下面的小节说明了三个基本的 STL 组件： 1） 迭代器提供了访问容器中对象的方法。例如，可以使用一对迭代器指定 list 或 vector 中的一定范围的对象。迭代器就如同一个指针。事实上，C+的指针也是一种迭代器。但是，迭代器也可以是那些定义了 operator*()以及其他类似于指针的操作符地方法的类对象。 2） 容器是一种数据结构，如 list，vector，和 deques ，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器。 3） 算法是用来操作容器中的数据的模板函数。例如，STL 用 sort()来对一个 vector 中的
4、数据进行排序，用 find()来搜索一个 list 中的对象。函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。 头文件 为了避免和其他头文件冲突， STL 的头文件不再使用常规的.h 扩展。为了包含标准的 string 类，迭代器和算法，用下面的指示符： #include #include #include 如果你查看 STL 的头文件，你可以看到象 iterator.h 和 stl_iterator.h 这样的头文件。由于这些名字在各种 STL 实现之间都可能不同，你应该避免使用这些名字来引用这些头文件。为了确保可移植性，使用相应的没有.
5、h 后缀的文件名。表 1列出了最常使用的各种容器类的头文件。该表并不完整，对于其他头文件，我将在本章和后面的两章中介绍。 表 1. STL 头文件和容器类 #include Container Class deque list map, multimap queue, priority_queue set, multiset stack vector, vector 名字空间 你的编译器可能不能识别名字空间。名字空间就好像一个信封，将标志符封装在另一个名字中。标志符只在名字空间中存在，因而避免了和其他标志符冲突。例如，可能有其他库和程序模块定义了 sort()函数，为了避免和 STL 地 so
6、rt()算法冲突，STL 的 sort()以及其他标志符都封装在名字空间 std 中。STL 的 sort()算法编译为 std:sort()，从而避免了名字冲突。 尽管你的编译器可能没有实现名字空间，你仍然可以使用他们。为了使用 STL，可以将下面的指示符插入到你的源代码文件中，典型地是在所有的#include 指示符的后面： using namespace std; 迭代器 迭代器提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围。迭代器就如同一个指针。事实上，C+的指针也是一种迭代器。但是，迭代器不仅仅是指针，因此你不能认为他们一定具有地址值。例如，一个数组索引，也可以认为是一
7、种迭代器。 迭代器有各种不同的创建方法。程序可能把迭代器作为一个变量创建。一个 STL 容器类可能为了使用一个特定类型的数据而创建一个迭代器。作为指针，必须能够使用*操作符类获取数据。你还可以使用其他数学操作符如+。典型的，+操作符用来递增迭代器，以访问容器中的下一个对象。如果迭代器到达了容器中的最后一个元素的后面，则迭代器变成past-the-end 值。使用一个 past-the-end 值得指针来访问对象是非法的，就好像使用 NULL 或为初始化的指针一样。 提示 STL 不保证可以从另一个迭代器来抵达一个迭代器。例如，当对一个集合中的对象排序时，如果你在不同的结构中指定了两个迭代器，第
8、二个迭代器无法从第一个迭代器抵达，此时程序注定要失败。这是 STL 灵活性的一个代价。STL不保证检测毫无道理的错误。 迭代器的类型 对于 STL 数据结构和算法，你可以使用五种迭代器。下面简要说明了这五种类型： Input iterators 提供对数据的只读访问。 Output iterators 提供对数据的只写访问 Forward iterators 提供读写操作，并能向前推进迭代器。 Bidirectional iterators 提供读写操作，并能向前和向后操作。 Random access iterators 提供读写操作，并能在数据中随机移动。 尽管各种不同的 STL 实现细节
9、方面有所不同，还是可以将上面的迭代器想象为一种类继承关系。从这个意义上说，下面的迭代器继承自上面的迭代器。由于这种继承关系，你可以将一个 Forward 迭代器作为一个 output 或 input 迭代器使用。同样，如果一个算法要求是一个 bidirectional 迭代器，那么只能使用该种类型和随机访问迭代器。 指针迭代器 正如下面的小程序显示的，一个指针也是一种迭代器。该程序同样显示了 STL 的一个主要特性它不只是能够用于它自己的类类型， 而且也能用于任何C或C+类型。 Listing 1, iterdemo.cpp, 显示了如何把指针作为迭代器用于STL的find()算法来搜索普通的
10、数组。 表 1. iterdemo.cpp #include #include using namespace std; #define SIZE 100 int iarraySIZE; int main() iarray20 = 50; int* ip = find(iarray, iarray + SIZE, 50); if (ip = iarray + SIZE) cout #include #include using namespace std; vector intVector(100); void main() intVector20 = 50; vector:iterator
11、intIter = find(intVector.begin(), intVector.end(), 50); if (intIter != intVector.end() cout :iterator first; 该语句创建了一个 vector类的迭代器。 下面的语句将该迭代器设置到 intVector 的第一个对象， 并将它指向的对象值设置为 123：: first = intVector.begin(); *first = 123; 这种赋值对于大多数容器类都是允许的，除了只读变量。为了防止错误赋值，可以申明迭代器为： const vector:iterator result; res
12、ult = find(intVector.begin(), intVector.end(), value); if (result != intVector.end() *result = 123; / ? 警告 另一种防止数据被改变得方法是将容器申明为 const 类型。 呀！在 VC 中测试出错,正确的含义是 result 成为常量而不是它指向的对象不允许改变，如同 int *const p;看来这作者自己也不懂 使用迭代器编程 你已经见到了迭代器的一些例子，现在我们将关注每种特定的迭代器如何使用。由于使用迭代器需要关于 STL 容器类和算法的知识，在阅读了后面的两章后你可能需要重新复习一
13、下本章内容。 输入迭代器 输入迭代器是最普通的类型。输入迭代器至少能够使用=和!=测试是否相等；使用*来访问数据；使用+操作来递推迭代器到下一个元素或到达 past-the-end 值。 为了理解迭代器和 STL 函数是如何使用它们的，现在来看一下 find()模板函数的定义： template InputIterator find( InputIterator first, InputIterator last, const T return first; 注意 在 find()算法中，注意如果 first 和 last 指向不同的容器，该算法可能陷入死循环。 输出迭代器 输出迭代器缺省只
14、写，通常用于将数据从一个位置拷贝到另一个位置。由于输出迭代器无法读取对象，因此你不会在任何搜索和其他算法中使用它。要想读取一个拷贝的值，必须使用另一个输入迭代器（或它的继承迭代器）。 Listing 3. outiter.cpp #include #include / Need copy() #include / Need vector using namespace std; double darray10 = 1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9; vector vdouble(10); int main() vector:ite
15、rator outputIterator = vdouble.begin(); copy(darray, darray + 10, outputIterator); while (outputIterator != vdouble.end() cout void replace (ForwardIterator first, ForwardIterator last, const T 使用 replace()将first,last范围内的所有值为 old_value 的对象替换为 new_value。: replace(vdouble.begin(), vdouble.end(), 1.5, 3.14159); 双向迭代器 双向迭代器要求能够增减。如 reverse()算法要求两个双向迭代器作为参数: template void reverse (BidirectionalIterator first, BidirectionalIterator last); 使用 reverse()函数来对容器进行逆向排序: reverse(vdouble.begin(), vdouble.end(); 随机访问迭代器 随机访问迭代器能够以任意顺序访问数据，并能用于读写数据（不是 const 的 C+指针也是随机访问迭代器）
