【精品】30分钟学会STL

下面是小编为大家整理的【精品】30分钟学会STL,供大家参考。

　30 分钟学会 STL STL 概述 STL 的一个重要特点是数据结构和算法的分离。

　尽管这是个简单的概念， 但这种分离确实使得 STL 变得非常通用。例如， 由于 STL 的 sort()函数是完全通用的， 你可以用它来操作几乎任何数据集合， 包括链表， 容器和数组。

　要点 STL 算法作为模板函数提供。为了和其他组件相区别， 在本书中 STL 算法以后接一对圆括弧的方式表示， 例如 sort()。

　STL 另一个重要特性是它不是面向对象的。

　为了具有足够通用性， STL 主要依赖于模板而不是封装， 继承和虚函数（多态性）

　——OOP 的三个要素。

　你在 STL 中找不到任何明显的类继承关系。

　这好像是一种倒退， 但这正好是使得 STL 的组件具有广泛通用性的底层特征。

　另外， 由于 STL 是基于模板， 内联函数的使用使得生成的代码短小高效。

　提示 确保在编译使用了 STL 的程序中至少要使用-O 优化来保证内联扩展。STL 提供了大量的模板类和函数， 可以在 OOP和常规编程中使用。

　所有的 STL 的大约 50 个算法都是完全通用的， 而且不依赖于任何特定的数据类型。

　下面的小节说明了三个基本的 STL 组件：

　1）

　迭代器提供了访问容器中对象的方法。

　例如， 可以使用一对迭代器指定 list 或 vector 中的一定范围的对象。

　迭代器就如同一个指针。

　事实上， C++的指针也是一种迭代器。

　但是， 迭代器也可以是那些定义了 operator*()以及其他类似于指针的操作符地方法的类对象。

　2）

　容器是一种数据结构， 如 list， vector， 和 deques ， 以模板类的方法提供。

　为了访问容器中的数据， 可以使用由容器类输出的迭代器。

　3）

　 算法是用来操作容器中的数据的模板函数。例如， STL 用 sort()来对一个 vector 中的数据进行排序， 用 find()来搜索一个 list 中的对象。

　函数本身与他们操作的数据的结构和类型无关， 因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。

　头文件 为了避免和其他头文件冲突，

　STL 的头文件不再使用常规的.h 扩展。

　为了包含标准的 string 类， 迭代器和算法，用下面的指示符：

　#include <string> #include <iterator> #include <algorithm>

　如果你查看 STL 的头文件， 你可以看到象 iterator.h 和 stl_iterator.h 这样的头文件。

　由于这些名字在各种 STL 实现之间都可能不同， 你应该避免使用这些名字来引用这些头文件。

　为了确保可移植性， 使用相应的没有.h 后缀的文件名。表 1 列出了最常使用的各种容器类的头文件。

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

　 表 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 数据结构和算法， 你可以使用五种迭代器。

　下面简要说明了这五种类型：

　·

　Input iterators 提供对数据的只读访问。

　·

　Output iterators 提供对数据的只写访问 ·

　Forward iterators 提供读写操作， 并能向前推进迭代器。

　·

　Bidirectional iterators 提供读写操作， 并能向前和向后操作。

　·

　Random access iterators 提供读写操作， 并能在数据中随机移动。

　尽管各种不同的 STL 实现细节方面有所不同， 还是可以将上面的迭代器想象为一种类继承关系。

　从这个意义上说，下面的迭代器继承自上面的迭代器。

　由于这种继承关系， 你可以将一个 Forward 迭代器作为一个 output 或 input 迭代器使用。

　同样， 如果一个算法要求是一个 bidirectional 迭代器， 那么只能使用该种类型和随机访问迭代器。

　 指针迭代器 正如下面的小程序显示的， 一个指针也是一种迭代器。

　该程序同样显示了 STL 的一个主要特性——它不只是能够用于它自己的类类型， 而且也能用于任何 C 或 C++类型。

　Listing 1, iterdemo.cpp, 显示了如何把指针作为迭代器用于 STL 的 find()算法来搜索普通的数组。

　表 1. iterdemo.cpp

　#include <iostream.h> #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;

　 else

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

　 return 0; } 在引用了 I/O 流库和 STL 算法头文件（注意没有.h 后缀）， 该程序告诉编译器使用 std 名字空间。

　使用 std 名字空间的这行是可选的， 因为可以删除该行对于这么一个小程序来说不会导致名字冲突。

　程序中定义了尺寸为 SIZE 的全局数组。

　由于是全局变量， 所以运行时数组自动初始化为零。

　下面的语句将在索引20 位置处地元素设置为 50,并使用 find()算法来搜索值 50:

　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); if (ip != NULL) ...

　// ??? incorrect 当使用 STL 函数时， 只能测试 ip 是否和 past-the-end 值是否相等。

　尽管在本例中 ip 是一个 C++指针,其用法也必须符合 STL 迭代器的规则。

　容器迭代器 尽管 C++指针也是迭代器， 但用的更多的是容器迭代器。

　容器迭代器用法和 iterdemo.cpp 一样， 但和将迭代器申明为指针变量不同的是， 你可以使用容器类方法来获取迭代器对象。

　两个典型的容器类方法是 begin()和 end()。

　它们在大多数容器中表示整个容器范围。

　其他一些容器还使用 rbegin()和 rend()方法提供反向迭代器， 以按反向顺序指定对象范围。

　下面的程序创建了一个矢量容器（STL 的和数组等价的对象）， 并使用迭代器在其中搜索。

　该程序和前一章中的程序相同。

　Listing 2. vectdemo.cpp

　#include <iostream.h> #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())

　 cout << "Vector contains value " << *intIter << endl;

　 else

　 cout << "Vector does not contain 50" << endl; }

　 注意用下面的方法显示搜索到的数据：

　cout << "Vector contains value " << *intIter << endl; 常量迭代器 和指针一样， 你可以给一个迭代器赋值。

　例如， 首先申明一个迭代器：

　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;

　// ??? 警告 另一种防止数据被改变得方法是将容器申明为 const 类型。

　『呀！

　在 VC 中测试出错,正确的含义是 result 成为常量而不是它指向的对象不允许改变， 如同 int *const p;看来这作者自己也不懂』

　 使用迭代器编程 你已经见到了迭代器的一些例子， 现在我们将关注每种特定的迭代器如何使用。

　由于使用迭代器需要关于 STL 容器类和算法的知识， 在阅读了后面的两章后你可能需要重新复习一下本章内容。

　输入迭代器 输入迭代器是最普通的类型。

　输入迭代器至少能够使用==和!=测试是否相等； 使用*来访问数据； 使用++操作来递推迭代器到下一个元素或到达 past-the-end 值。

　为了理解迭代器和 STL 函数是如何使用它们的， 现在来看一下 find()模板函数的定义：

　template <class InputIterator, class T> InputIterator find(

　 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;

　 double darray[10] =

　 {1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9};

　 vector<double> vdouble(10);

　 int main() {

　 vector<double>::iterator outputIterator = vdouble.begin();

　 copy(darray, darray + 10, outputIterator);

　 while (outputIterator != vdouble.end()) {

　 cout << *outputIterator << endl;

　 outputIterator++;

　 }

　 return 0; } 注意

　当使用 copy()算法的时候， 你必须确保目标容器有足够大的空间， 或者容器本身是自动扩展的。

　前推迭代器 前推迭代器能够读写数据值， 并能够向前推进到下一个值。

　但是没法递减。

　replace()算法显示了前推迭代器的使用方法。

　 template <class ForwardIterator, class T> void replace (ForwardIterator first,

　 ForwardIterator last,

　 const T& old_value,

　 const T& new_value); 使用 replace()将[first,last]范围内的所有值为 old_value 的对象替换为 new_value。

　: replace(vdouble.begin(), vdouble.end(), 1.5, 3.14159); 双向迭代器 双向迭代器要求能够增减。

　如 reverse()算法要求两个双向迭代器作为参数: template <class BidirectionalIterator> void reverse (BidirectionalIterator first,

　 BidirectionalIterator last); 使用 reverse()函数来对容器进行逆向排序: reverse(vdouble.begin(), vdouble.end()); 随机访问迭代器 随机访问迭代器能够以任意顺序访问数据， 并能用于读写数据（不是 const 的 C++指针也是随机访问迭代器）。

　STL的排序和搜索函数使用随机访问迭代器。

　随机访问迭代器可以使用关系操作符作比较。

　random...

推荐访问:【精品】30分钟学会STL 学会 精品 STL