1、1标准模板库 STL(Standard Template Library)指南目录1 介绍 .21.1 动机 .21.2 STL 历史 .21.3 STL 和 ANSI/ISO C+草案标准 .21.4 内容安排 .22 C+基础 .22.1 类 .22.2 函数对象(Function Objects).32.3 模板(Template) .32.3.1 函数模板 .32.3.2 类模板 .42.3.3 模板特化 .53 STL 概貌 .53.1 STL 网上信息 .63.2 STL 文档 .63.3 编译 STL 程序 .64 学习 STL .64.1 容器(Container) .64.1
2、.1 向量 (Vector) .74.2 迭代器(Iterator) .94.2.1 输入和输出迭代器 .94.2.2 向前迭代器 .104.2.3 双向迭代器 .104.2.4 任意存取迭代器 .114.3 算法和函数对象 .114.3.1 如何创建基本算法 .114.3.2 STL 算法 .134.4 适应器(Adaptor) .154.4.1 容器适应器 .154.4.2 迭代适应器 .154.4.3 函数适应器 .164.5 分配算符和内存处理 .165 其余的 STL 部件 .165.2 向量(Vector) .165.3 线性表(List) .165.4 双向队列(Deque) .
3、175.5 迭代标签(Iterator Tag).175.6 关联容器(Container) .1721 介绍1.1 动机在七十年代末，Alexander Stepanov 第一个发现一些算法不依赖于数据结构的特定实现，而仅仅和结构的一些基本语义属性相关。这些属性表达了一种能力，比如可以从数据结构的一个成员取得下一个成员，从头到尾“走过” 结构中的元素就象排序算法不关心元素是存放在数组中或是线性表中） 。Stepanov 研究过一些算法可以用一种抽象的方式实现，而且不会影响效率。1.2 STL 历史1985 年，Stepanov 开发了基本 Ada 库，有人要求他在 C+中也这样做。但直到 1
4、987 年，模板(Template)在C+中还未实现，所以他的工作推迟了。1988 年，Stepanov 到 HP 实验室工作，并在 1992 年被任命为一个算法项目的经理。在此项目中，Alexander Stepanov 和 Meng Lee 写了一个巨大的库-标准模板库(STL：Standard Template Library)，意图定义一些通用算法而不影响效率。现在 STL 在国外已经成了新的编程手段。1.3 STL 和 ANSI/ISO C+草案标准1994 年 7 月 14 日，ANSI/ISO C+标准化委员会将 STL 采纳为草案标准。现在 Microsoft Visual C
5、+ 5.0 以上及 Borland C+ 4.0 以上都支持 STL。STL 已经并将继续影响软件开发的方法，有了 STL，程序员可以写更少且更快的代码，把精力集中在问题解决上，而不必关心低层的算法和数据结构了。1.4 内容安排第 2 部分介绍 STL 需要的 C+基础，主要是类、函数对象和模板。第 3 部分是概貌，介绍了关键的思想。第 4 部分 step-by-step 的教 STL。第 5 部分介绍剩余的 STL 部分。第 6 部分是版权信息。第 7 部分是参考文献。2 C+基础2.1 类请读下面一段代码:class shapeprivate:int x_pos;int y_pos;int
6、 color;public:shape() : x_pos(0), y_pos(0), color(1) shape(int x, int y, int c = 1) : x_pos(x), y_pos(y), color(c) shape(const shapey_pos = s.y_pos;color = s.color;return *this;int get_x_pos() return x_pos; int get_y_pos() return y_pos; int get_color() return color; 3void set_x_pos(int x) x_pos = x;
7、 void set_y_pos(int y) y_pos = y; void set_color(int c) color = c; virtual void DrawShape() friend ostreama = b;b = tmp注意这里 T 是任意的类型名字。看例子：int a = 3, b =5;shape MyShape, YourShape;float fa = 3.01, fb = 5.02;swap(a , b); /交换整数swap(MyShape, YourShape); /交换自定义类的两个对象的值swap(fa, fb); /交换浮点数还可以看看两个函数模板例子：t
8、emplate Tint sz;public:5vector(int s) v = new Tsz = s; vector() delete v; T int get_size() return sz; ;现在你可以实例化不同类型的 vector 容器了：vector int_vector(10);vectorchar_vector(10);vector shape_vector(10);2.3.3 模板特化也许在某些情况下，编译器对某种类型产生的模板代码不另你满意，你也可以为这种类型给出一个特定的实现，此之谓“ 模板特化(template specialization)”。比如，你想让 sh
9、ape 类型的 vector 只包含一个对象，则可以特化 vector 模板如下：class vectorshape v;public:vector(shape int get_size() return 1; ;使用时：shape MyShape;vector single_shape_vector(MyShape);STL 中有时会需要定义特定类型的算法或容器实现。3 STL 概貌STL 是个部件库(component library)，其中的部件包括有容器(container，储存任意类型对象的对象)和算法。只要用户对自己定义的部件做点小小的要求，STL 中的算法就可以工作在用户自定义的
10、容器上，或者 STL 中的容器可以使用用户自定义的算法。隐藏在 STL 后面的想法可以用下图表示：我们可以把软件部件想象成一个三位空间。第一维表示数据类型(int, double, char, )，第二维表示容器(array, linked-list, )，第三维表示算法(sort, merge, search, )。根据这个图示，需要设计 i*j*k 个不同的代码版本，比如整数数组的排序算法、double 数组的排序算法，double linked-list 的搜索算法。通过使用数据类型作为参数的模板函数，第一维(i 轴)就可取消，而仅需要设计 j*k 个不同的代码。下一步是让算法可以工作在
11、不同的容器上，这就意味着排序算法既可以用在 array 上，也可用在 linked-list 上。最后，只需要设计 j+k 个不同的代码版本了。STL 具体化了上述思想，期望通过减少开发时间以简化软件开发，简化调试、维护并增加代码的可移植性。STL 包含 5 个主要的部分，以后会有较详细的陈述：算法(Algorithm)：能运行在不同容器(container)上的计算过程容器(Container)：能够保留并管理对象的对象int, double, char, array, linked-list kijsort, merge, serarch, 6迭代器(Iterator)：算法存取容器(al
12、gorithm-access to containers)的抽象，以便算法可以应用在不同的容器上函数对象(Function Object)：定义了函数调用操作符 (operator()的类适应器(Adaptor)：封装一个部件以提供另外的接口( 例如用 list 实现 stack)3.1 STL 网上信息STL 的 FTP 站点HP 实验室(Alexander Stepanov 和 Meng Lee) - ftp:/ 的 WWW 站点David Mussers 的 STL 主页 - http:/www.cs.rpi.edu/musser/stl.htmlLink2go 上有关 C+编程的主页：
13、http:/ 3 个网址，其内容及其丰富，不仅仅有关 STL。3.2 STL 文档参考文献之6 附件二The Standard Template Libray 以及源代码, Alexander Stepanov /一定要写上这句话，因为 STL 都是在 std 名字空间中定义的void F1()vector v(10); /现在你就可以放心大胆的使用 STL 了4 学习 STL4.1 容器(Container)容器(Container)是能够保存其他类型的对象的类。容器形成了 STL 的关键部件。当书写任何类型软件的时候，把特定类型的元素集聚起来都是很至关重要的任务。STL 中有顺序容器(Se
14、quence Container)和关联容器(Associative Container)。顺序容器组织成对象的有限线性集合，所有对象都是同一类型。STL 中三种基本顺序容器是：向量(Vector) 、线性表(List)、双向队列(Deque) 。关联容器提供了基于 KEY 的数据的快速检索能力。元素被排好序，检索数据时可以二分搜索。STL 有四种关联容器。当一个 KEY 对应一个 Value 时，可以使用集合(Set)和映射(Map) ；若对应同一 KEY 有多个元素被存储时，可以使用多集合(MultiSet)和多映射(MultiMap)。7STL 中支持的容器总结如下：顺序容器(Seque
15、nce Container) 向量(Vector)双向队列(Deque)线性表(List)关联容器(Associative Container) 集合(Set)多集合(MultiSet)映射(Map)多映射(MultiSet)4.1.1 向量 (Vector)如果你要将所有 shape 对象保存在一个容器中，用 C+代码可以这样写：shape my_shapesmax_size;这里 max_size 是可以保存在 my_shapes 数组中的最大数量。当你使用 STL 时，则可以这样写：#include using namespace std;int main()vector my_shap
16、es;/ 使用 my_shapesreturn 0;【 此后的代码不再写 #inlucde 行、 using namespace std，以及 main()函数，直接写示例代码 】现在想得到容器中能保存的最大元素数量就可以用 vector 类的成员函数 max_size()：vector:size_type max_size = my_shapes.max_size();当前容器的实际尺寸 - 已有的元素个数用 size()：vector:size_type size = my_shapes.size();就像 size_type 描述了 vector 尺寸的类型，value_type 说明了
17、其中保存的对象的类型：cout :value_type).name();输出：value type: float可以用 capacity()来取得 vector 中已分配内存的元素个数：vector v;vector:size_type capacity = v.capacity();vector 类似于数组，可以使用下标访问：vector v(10);v0 = 101;注意到这里预先给 10 个元素分配了空间。你也可以使用 vector 提供的插入函数来动态的扩展容器。成员函数push_back()就在 vector 的尾部添加了一个元素：v.push_back(3);也可以用 insert
18、()函数完成同样的工作：v.insert(v.end(), 3);这里 insert()成员函数需要两个参数：一个指向容器中指定位置的迭代器(iterator)，一个待插入的元素。insert()将元素插入到迭代器指定元素之前。现在对迭代器(Iterator)做点解释。Iterator 是指针(pointer)的泛化，iterator 要求定义 operator*，它返回指定类型的值。Iterator 常常和容器联系在一起。例子：vector v(3);v0 = 5;v1 = 2;8v2 = 7;vector:iterator first = v.begin();vector:iterator
19、 last = v.end();while (first != last)cout v(5, 3.25); /初始化有 5 个元素，其值都是 3.25vector v_new1(v);John Tom Peter Andybegin()返回的 iterator end()返回的 iterator类型 value_type 的对象Iterator Iterator Iterator对象 对象 对象容器(Container)算法(Algorithm)9vector v_new2 = v;vector v_new3(v.begin(), v.end();这四个 vector 对象是相等的，可以用 o
20、perator=来判断。其余常用的 vector 成员函数有：empty()：判断 vector 是否为空front()：取得 vector 的第一个元素back()：取得 vector 的最后一个元素pop_back()：去掉最后一个元素erase()：去掉某个 iterator 或者 iterator 区间指定的元素到现在我们已经可以把一些对象存储在容器(container)中，并有几种手段来进行管理和维护。为了将算法应用到容器中的元素上，下面要对迭代器(Iterator)做进一步的解释。4.2 迭代器(Iterator)迭代器(Iterator)是指针(pointer)的泛化，它允许程序
21、员以相同的方式处理不同的数据结构(容器) 。STL 中有 5 中类型的迭代器，它们分别满足一定的要求。不同的迭代器要求定义的操作不一样。箭头表示左边的迭代器一定满足右边迭代器需要的条件。比如某个算法需要一个双向迭代器(Bidirctional Iterator)，你可以把一个任意存取迭代器(Random Access Iterator)作为参数；但反之不行。4.2.1 输入和输出迭代器输入迭代器(Input Iterator)需要满足的条件：constructorassignment operatorequality/inequality operatordereferenc operator
22、pre/post increment operator输入迭代器表示要从其中取出一个值，即从输入迭代器 X 中取值只可有以下三种形式：V = *X+V = *X, +XV = *X, X+输出迭代器(Output Iterator)需要满足的条件：constructorassignment operatordereferenc operatorpre/post increment operator一个输出迭代器 X 只能有一个值 V 存储其中，在下一个存储之前，必须将 X 加一。即只可有以下三种形式之一：*X+ = V*X = V, +X*X = V, X+注意，对输入和输出迭代器，一旦取出或
23、放入值后，就只能前进(increment)，不可多次取出或放入。任意存取 双向迭代器 向前迭代器输出迭代器输入迭代器104.2.2 向前迭代器向前迭代器(Forward Iterator)需要满足的条件：constructorassignment operatorequality/inequality operatordereferenc operatorpre/post increment operator和输入和输出迭代器比较而言，两个向前迭代器 r 和 s，若 r = s 则+r = +s。而且既可取值，也可赋值：*X = V, V = *X。看一个例子：template Forward
24、Iterator find_linear(ForwardIterator first, ForwardIterator last, Treturn last;函数 find_linear()在一个容器中循环，如果找到指定的值，则返回该值的迭代器位置；否则返回 past-the-end 迭代器。下面用这个函数：vector v(3, 1);v.push_back(7); / vector v: 1 1 1 7vector:iterator i = find_linear(v.begin(), v.end(), 7);if (i != v.end()cout void bubble_sort(BidirectionalIterator first, BidirectionalIterator last, Compare comp)BidirectionalIterator left_el = first, right_el = first;right_el+;while (first != last)while (right_el != last)if (comp(*right_el, *left_el)iter_swap(left_el, right_el);right_el+;left_el+;
