《分钟掌握STL(迭代器)》由会员分享，可在线阅读，更多相关《分钟掌握STL(迭代器)（23页珍藏版）》请在金锄头文库上搜索。
1、三十分钟掌握 STL 这是本小人书。原名是using stl，不知道是谁写的。不过我倒觉得很有趣， 所以化了两个晚上把它翻译出来。我没有对翻译出来的内容校验过。如果你没 法在三十分钟内觉得有所收获，那么赶紧扔了它。文中我省略了很多东西。心 疼那，浪费我两个晚上。 译者：karycontact:STLSTL 概述概述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.1. STLSTL 头文件和容器类头文件和容器类#include#includeContainerContainer ClassClassdequelistmap, multimapqueue, priority_queueset, multisetstackvector, vector名字空间名字空间你的编译器可能不能识别名字空间。名字空间就好像一个信封，将标志符 封装在另一个名字中。标志符只在名字空间中存在，因而避免了和其他标志符 冲突。例如，
6、可能有其他库和程序模块定义了 sort()函数，为了避免和 STL 地 sort()算法冲突，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
9、 iterators提供读写操作，并能在数据中随机移动。尽管各种不同的 STL 实现细节方面有所不同，还是可以将上面的迭代器想象为一种类继承关系。从这个意义上说，下面的迭代器继承自上面的迭代器。由于这种继承关系，你可以将一个Forward 迭代器作为一个 output 或 input 迭代器使用。同样，如果一个算法要求是一个bidirectional 迭代器，那么只能使用该种类型和随机访问迭代器。 指针迭代器指针迭代器正如下面的小程序显示的，一个指针也是一种迭代器。该程序同样显示了 STL 的一个主要特性它不只是能够用于它自己的类类型，而且也能用于任何 C 或 C+类型。Listing 1,
10、iterdemo.cpp, 显示了如何把指针作为迭代器用于 STL 的 find()算法来搜索普通的数组。表表 1.1. iterdemo.cppiterdemo.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 intV
11、ector(100);void main() intVector20 = 50;vector:iterator intIter =find(intVector.begin(), intVector.end(), 50);if (intIter != intVector.end()cout :iterator first;该语句创建了一个 vector类的迭代器。下面的语句将该迭代器设置到 intVector 的第一个对象，并将它指向的对象值设置为 123：:first = intVector.begin(); *first = 123;这种赋值对于大多数容器类都是允许的，除了只读变量。为了防止
12、错误赋值，可以申明迭代器为：const vector:iterator result; result = find(intVector.begin(), intVector.end(), value); if (result != intVector.end()*result = 123; / ?警告警告另一种防止数据被改变得方法是将容器申明为 const 类型。呀！在 VC 中测试出错,正确的含义是 result 成为常量而不是它指向的对象不允许改变，如同int *const p;看来这作者自己也不懂 使用迭代器编程使用迭代器编程你已经见到了迭代器的一些例子，现在我们将关注每种特定的迭代器如
13、何使用。由于使用迭代器需要关于 STL 容器类和算法的知识，在阅读了后面的两章后你可能需要重新复习一下本章内容。输入迭代器输入迭代器输入迭代器是最普通的类型。输入迭代器至少能够使用=和!=测试是否相等；使用*来访问数据；使用+操作来递推迭代器到下一个元素或到达past-the-end 值。为了理解迭代器和 STL 函数是如何使用它们的，现在来看一下 find()模板函数的定义：template InputIterator find(InputIterator first, InputIterator last, const Treturn first;注意注意在 find()算法中，注意如果
14、first 和 last 指向不同的容器，该算法可能陷入死循环。输出迭代器输出迭代器输出迭代器缺省只写，通常用于将数据从一个位置拷贝到另一个位置。由于输出迭代器无法读取对象，因此你不会在任何搜索和其他算法中使用它。要想读取一个拷贝的值，必须使用另一个输入迭代器（或它的继承迭代器）。ListingListing 3.3. outiter.cppoutiter.cpp #include #include / Need copy() #include / Need vectorusing namespace std;double darray10 =1.0, 1.1, 1.2, 1.3, 1.4,
15、1.5, 1.6, 1.7, 1.8, 1.9;vector vdouble(10);int main() vector:iterator 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 的对象替换
16、为 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+指针也是随机访问迭代器）。STL 的排序和搜索函数使用随
