1. 什么是STL?

STL 是“Standard Template Library”的缩写，中文译为“标准模板库”或者“泛型库”。

其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合，用于完成诸如输入/输出、数学计算等功能。

STL 是 C++ 标准库的一部分，不用单独安装。STL 最初由惠普实验室开发，于 1998 年被定为国际标准，正式成为 C++ 程序库的重要组成部分。值得一提的是，如今 STL 已完全被内置到支持 C++ 的编译器中，无需额外安装，这可能也是 STL 被广泛使用的原因之一。

STL 就位于各个 C++ 的头文件中，即它并非以二进制代码的形式提供，而是以源代码的形式提供。

C++ 对模板（Template）支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。例如，vector 的底层为顺序表（数组），list 的底层为双向链表，deque 的底层为循环队列，set 的底层为红黑树，hash_set 的底层为哈希表。

从根本上说，STL 是一些容器、算法和其他一些组件的集合，所有容器和算法都是总结了几十年来算法和数据结构的研究成果，汇集了许多计算机专家学者经验的基础上实现的，因此可以说，STL 基本上达到了各种存储方法和相关算法的高度优化。

2. 学STL能干什么？

为了让读者清楚地了解 STL 是什么，使用 STL 编程有哪些优势，这里举一个使用 STL 的例子。

以 C++ 定义数组的操作为例，在 C++ 中如果定义一个数组，可以采用如下方式：

int a[n];

这种定义数组的方法需要事先确定好数组的长度，即 n 必须为常量，这意味着，如果在实际应用中无法确定数组长度，则一般会将数组长度设为可能的最大值，但这极有可能导致存储空间的浪费。

所以除此之外，还可以采用在堆空间中动态申请内存的方法，此时长度可以是变量：

1	int *p = new int[n];

这种定义方式可根据变量 n 动态申请内存，不会出现存储空间浪费的问题。但是，如果程序执行过程中出现空间不足的情况时，则需要加大存储空间，此时需要进行如下操作：

新申请一个较大的内存空间，即执行int * temp = new int[m];
将原内存空间的数据全部复制到新申请的内存空间中，即执行memecpy(temp, p, sizeof(int)*n);
将原来的堆空间释放，即执行delete [] p; p = temp;

而完成相同的操作，如果采用 STL 标准库，则会简单很多，因为大多数操作细节将不需要程序员关心。下面是使用向量模板类 vector 实现以上功能的示例：

vector <int> a; //定义 a 数组，当前数组长度为 0，但和普通数组不同的是，此数组 a 可以根据存储数据的数量自动变长。
//向数组 a 中添加 10 个元素
for (int i = 0; i < 10 ; i++)
    a.push_back(i)
//还可以手动调整数组 a 的大小
a.resize(100);
a[90] = 100;
//还可以直接删除数组 a 中所有的元素，此时 a 的长度变为 0
a.clear();
//重新调整 a 的大小为 20，并存储 20 个 -1 元素。
a.resize(20, -1)

注意，初学者只需结合注释，大概了解代码功能即可，有关代码中涉及到具体知识，后续会做详细介绍。

对比以上两种使用数组的方式不难看出，使用 STL 可以更加方便灵活地处理数据。所以，大家只需要系统地学习 STL，便可以集中精力去实现程序的功能，而无需再纠结某些细节如何用代码实现。

3. STL的发展历程

Alexander Stepanov（后被誉为 STL 标准模板库之父，后简称 Stepanov），1950 年出生与前苏联的莫斯科，他曾在莫斯科大学研究数学，此后一直致力于计算机语言和泛型库研究。

在 20 世纪 70 年代，Stepanov 开始考虑，在保证效率的前提下，是否能将算法从诸多具体应用之中抽象出来？为了验证自己的思想，他和纽约州立大学教授 Deepak Kapur 以及伦塞里尔技术学院教授 David Musser 共同开发了一种叫做 Tecton 的语言，尽管这次尝试没有取得实用性的成果，但却给了 Stepanov 很大的启示。

在随后的几年中，他又和 David Musser 等人先后用 Schema 语言（一种 Lisp 语言的变种）和 Ada 语言建立了一些大型程序库。Stepanov 逐渐意识到，在当时的面向对象程序设计思想中存在一些问题，比如抽象数据类型概念所存在的缺陷，他希望通过对软件领域中各组成部分的分类，逐渐形成一种软件设计的概念性框架。

1987 年，在贝尔实验室工作的 Stepanov 开始首次采用 C++ 语言进行泛型软件库的研究。由于当时的 C++ 语言还没有引入模板的编程技术，泛型库只能是通过 C++ 的继承机制来开发，代码表达起来非常笨拙。

但尽管如此，Stepanov 还是开发出了一个庞大的算法库。与此同时，在与 Andrew Koenig（前 ISO C++ 标准化委员会主席）和 Bjarne Stroustrup（C++ 语言的创始人）等顶级大师们的共事过程中，Stepanov 开始注意到 C/C++ 语言在实现其泛型思想方面所具有的潜在优势。

就拿 C/C++ 中的指针而言，它的灵活与高效运用使后来的 STL 在实现泛型化的同时更是保持了高效率。另外，在 STL 中占据极其重要地位的迭代器概念便是源自于 C/C++ 中原生指针的一般化推广。

1988 年，Stepanov 开始进入惠普的 Palo Alto 实验室工作，在随后的 4 年中，他从事的是有关磁盘驱动器方面的工作。直到 1992 年，由于参加并主持了实验室主任 Bill Worley 所建立的一个有关算法的研究项目，才使他重新回到了泛型化算法的研究工作上来。

项目自建立之后，参与者从最初的 8 人逐渐减少，最后只剩下 Stepanov 和 Meng Lee 两个人。经过长时间的努力，最终完成了一个包含有大量数据结构和算法部件的庞大运行库（HP 版本的 C++ STL），这便是现在 STL 的雏形。

1993 年，当时在贝尔实验室的 Andrew Koenig 看到了 Stepanov 的研究成果，在他的鼓励与帮助下，Stepanov 于 1993 年 9 月在圣何塞为 ANSI/ISO C++ 标准委员会做了一个题为“The Science of C++ Programming” 的演讲，向委员们讲述了其观念。然后又于 1994 年 3 月，在圣迭戈会议上向委员会提交了一份建议书，以期将 STL 通用库纳入 C++ 标准。

尽管这一建议十分庞大，以至于降低了被通过的可能性，但其所包含的新思想吸引了许多人的注意力。随后在众人的帮助之下，包括 Bjame Stroustrup 在内，Stepanov 又对 STL 进行了改进，同时加入了一个封装内存模式信息的抽象模块，也就是现在 STL 中的 allocator（内存分配器），它使 STL 的大部分实现都可以独立于具体的内存模式，从而独立于具体平台。

最终在 1994 年的滑铁卢会议上，委员们通过了提案，决定将 STL 正式纳入 C++ 标准化进程之中，随后 STL 便被放进了会议的工作文件中。自此，STL 终于成为 C++ 家族中的重要一员。

此后，随者 C++ 标准的不断改进，STL 也在不断地做着相应的演化。直至 1998 年，ANSI/ISO C++ 标准正式定案，STL 始终是 C++ 标准库不可或缺的重要组成部分。

4. C++ STL版本有哪些？

自 1998 年 ANSI/ISO C++ 标准正式定案，C++ STL 规范版本正式通过以后，由于其实开源的，各个 C++ 编译器厂商在此标准的基础上，实现了满足自己需求的 C++ STL 泛型库，主要包括 HP STL、SGI STL、STLport、PJ STL、Rouge Wave STL 等。

4.1. HP STL

HP STL 是 Alexandar Stepanov（STL 标准模板库之父，文章后续简称 Stepanov）在惠普 Palo Alto 实验室工作时，与 Meng Lee 合作完成的。HP STL 是开放源码的，即任何人都可以免费使用、复制、修改、发布和销售该软件以及相关文档，但前提是必须在相关文档中，加入 HP STL 版本信息和授权信息。

HP STL 是 C++ STL 的第一个实现版本，其它版本的 C++ STL 一般是以 HP STL 为蓝本实现出来的。不过，现在已经很少直接使用此版本的 STL 了。

4.2. SGI STL

Stepanov 在离开 HP 之后，就加入到了 SGI 公司，并和 Matt Austern 等人开发了 SGI STL。严格意义上来说，它是 HP STL 的一个继承版本。和 HP STL 一样，SGI STL 也是开源的，其源代码的可读性可非常好，并且任何人都可以修改和销售它。

注意，和 STL 官方版本来说，SGI STL 只能算是一个“民间”版本，因此并不是所有支持 C++ 的编译器都支持使用 SGI STL 模板库，唯一能确定的是，GCC（Linux 下的 C++ 编译器）是支持的，所以 SGI STL 在 Linux 平台上的性能非常出色。

4.3. STLport

为了使 SGI STL 的基本代码都适用于 VC++ 和 C++ Builder 等多种编译器，俄国人 Boris Fomitchev 建立了一个 free 项目来开发 STLport，此版本 STL 是开放源码的。

4.4. PJ STL

PJ STL（全称为 P.J. Plauger STL）是由 P.J.Plauger（美国人，1965 年毕业于普林斯顿大学，物理专业学士）参照 HP STL 实现出来的，也是 HP STL 的一个继承版本，因此该头文件中不仅含有 HP STL 的相关授权信息，同时还有 P.J.Plauger 本人的版权信息。
其实 PJ STL 是 P.J.Plauger 公司的产品，尽管该公司当时只有 3 个人。

PJ STL 被 Visual C++ 编译器所采用，但和 PH STL、SGI STL 不同的是，PJ STL 并不是开源。

4.5. Rouge Wave STL

该版本的 STL 是由 Rouge Wave 公司开发的，也是继承 HP STL 的一个版本，它也不是开源的。

Rouge Wave STL 用于 Borland C++ Builder 编译器中，我们可以在 C++ Builder 的 Inculde 子目录中找到该 STL 的所有头文件。

值得一提的是，尽管 Rouge Wave STL 的性能不是很好，但 C++ Builder 对 C++ 语言标准的支持还算不错，所以在一定程度上使 Rouge Wave STL 的表现得以改善。

遗憾的是，由于 Rouge Wave STL 长期没有更新且不完全符合标准，因此 Rouge Wave STL 在 6.0 版本时改用了 STLport 版本（之后的版本也都采用了 STLport），不过考虑到和之前版本的兼容，6.0 版本中依旧保留了 Rouge Wave STL。

Rouge Wave 公司在 C++ 程序库领域应该说是鼎鼎大名，对 C++ 标准化的过程出力甚多。不过 Rouge Wave STL 版本不仅更新频率慢，费用还高，基于这两个原因，Borland 在 6.0 版本决定弃用 Rouge Wave STL 而改用 STLport。

5. C++ STL基本组成（6大组件+13个头文件）

STL并没有使用面向对象的思想，而是使用了GP（泛型编程）思想

通常认为，STL 是由容器、算法、迭代器、函数对象、适配器、内存分配器这 6 部分构成，其中后面 4 部分是为前 2 部分服务的，它们各自的如下含义所示。
STL 组成结构：

容器：一些封装数据结构的模板类，例如 vector 向量容器、list 列表容器等。
算法：STL 提供了非常多（大约 100 个）的数据结构算法，它们都被设计成一个个的模板函数，这些算法在 std 命名空间中定义，其中大部分算法都包含在头文件中，少部分位于头文件中。
迭代器：在 C++ STL 中，对容器中数据的读和写，是通过迭代器完成的，扮演着容器和算法之间的胶合剂。
函数对象/仿函数：如果一个类将 () 运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象（又称仿函数）。
适配器：可以使一个类的接口（模板的参数）适配成用户指定的形式，从而让原本不能在一起工作的两个类工作在一起。值得一提的是，容器、迭代器和函数都有适配器。
内存分配器：为容器类模板提供自定义的内存申请和释放功能，由于往往只有高级用户才有改变内存分配策略的需求，因此内存分配器对于一般用户来说，并不常用。

关于 STL 的构成，初学者简单了解即可，后续章节将专门对它们做系统的深入讲解。

另外，在惠普实验室最初发行的版本中，STL 被组织成 48 个头文件；但在 C++ 标准中，它们被重新组织为 13 个头文件。

按照 C++ 标准库的规定，所有标准头文件都不再有扩展名。以为例，此为无扩展名的形式，而 <vector.h> 为有扩展名的形式。

但是，或许是为了向下兼容，或许是为了内部组织规划，某些 STL 版本同时存储具备扩展名和无扩展名的两份文件（例如 Visual C++ 支持的 Dinkumware 版本同时具备 <vector.h> 和）；甚至有些 STL 版本同时拥有 3 种形式的头文件（例如 SGI 版本同时拥有、<vector.h> 和 <stl_vector.h>）；但也有个别的 STL 版本只存在包含扩展名的头文件（例如 C++ Builder 的 RaugeWare 版本只有 <vector.h>）。

建议读者养成良好的习惯，遵照 C++ 规范，使用无扩展名的头文件。

6. 算法的执行效率？

学习 C++ 标准库，特别是 STL，经常需要考量算法和成员函数的效能（也就是运行效率，又称复杂度），因此每个学习 STL 的读者都需要掌握一种衡量算法（或成员函数）复杂度的方法，目前最常用的方法称为大 O 表示法（注意，不是数字 0，而是字母 O）。

学习 C++ 标准库，特别是 STL，经常需要考量算法和成员函数的效能（也就是运行效率，又称复杂度），因此每个学习 STL 的读者都需要掌握一种衡量算法（或成员函数）复杂度的方法，目前最常用的方法称为大 O 表示法（注意，不是数字 0，而是字母 O）。

使用大 O 表示法衡量某个算法的复杂度，其实就是将该算法的运行时间用输入量为 n 的函数表示出来。这里的输入量 n 在 STL 中通常指的是算法操作的元素个数。

举个例子，当算法运行时间随元素个数成线性增长时（即如果元素个数呈倍数增长，运行时间也呈倍数增长），该算法的复杂度用 O(n) 来表示；反之，如果算法的运行时间和输入量 n 无关，则该算法的复杂度就用 O(1) 来表示。

表 1 列出了常见的算法复杂度种类，以及使用大 O 表示法表示的复杂度。

算法复杂度种类	含义	大O表示法
常数阶	算法运行时间和所操作的元素个数无关	O(1)
对数阶	算法运行时间随所操作的元素个数呈对数增长	O(log(n))
线性阶	算法运行时间随所操作的元素个数呈线性增长	O(n)
指数阶（m次方，m为数字）	算法运行时间随所操作的元素个数呈m次方增长 O(nm)	常见的有O(n2)、O(n3)等

值得注意的是，大 O 表示法并不关心算法运行所消耗的具体时间，换句话说，对于那些影响算法运行效率较小的因素，使用大 O 表示法表示时会直接将其忽略。例如，某个算法运行的复杂度为 O(n)，呈线性增长，但至于线性增长的具体程度（是 100n 还是 2n），在大 O 表示法看来，它们是一样的。也就是说，采用这种测量法则，任何两个线性算法都将被视为具有相同的复杂度。

采用大 O 表示法甚至会出现这种一种情况，即带有巨大常量的线性算法，很有可能会比小常量的指数算法更受欢迎，因为该方法无法显示出真实的运行时间。

所以请读者记住，大 O 表示法只是某种度量方法，它所显示的算法的最佳复杂度，并不一定就是真正的最佳（最快）算法。

复杂度		元素个数
种类	大O表示	1	2	5	10	50	100	1 000	10 000
常量阶	O(1)	1	1	1	1	1	1	1	1
对数阶	O(log(n))	1	2	3	4	6	7	10	13
线性阶	O(n)	1	2	5	10	50	100	1 000	10 000
2次方	O(n2)	1	4	25	100	2500	10 000	1 000 000	100 000 000

表 2 列出了常用的复杂度随元素个数增长的变化程序。可以看到，当算法处理的元素较少时，各复杂度的差别很小，此时算法效率的优劣往往受被大 O 表示法忽略部分的影响更大。而当处理元素个数越多，各复杂度的差别越大，此时复杂度被忽略的部分就变得无关紧要了。

因此，在考量算法的复杂度时，输入量 n （操作元素的个数）的值必须足够大才有意义。