STL基础教程.doc

1. STL 概论

长久以来，软件界一直希望建立一种可重复利用的东西，以及一种得以制造出”可重复

运用的东西”的方法让程序员的心血不止于随时间的迁移，人事异动而烟消云散，从函数

，类别函数库类别库、各种

组件，从模块化设计，到面向对象，为的就是复用性的提升。

复用性必须建立在某种标准之上。但是在许多环境下，就连软件开发最基本的数据结

构和算法都未能有一套标准。大量程序员被迫从事大量重

统

称。现在主要出现在 中，但是在引入 之前该技术已经存在很长时间了。

从广义上分为容器算法迭代器容器和算法

之间通过迭代器进行无缝连接。几乎所有的代码都采用了模板类或者模板函数，这相

比 传 统 的 由 函 数 和 类 组 成 的 库 来 说 提 供 了 更 好 的 代 码 重 用 机 会 。 

标准模板库在我们 标准程序库中隶属于 的占到了  以

上。

1.2 STL 六大组件简介

 提供了六大组件，彼此之间可以组合套用，这六大组件分别是容器、算法、迭代

器、仿函数、适配器（配接器）、空间配置器。

的 %所有  容器都附带有自己专属的迭代器，只有容器的设计者才知道

如何遍历自己的元素。原生指针!也是一种迭代器。

仿函数：行为类似函数，可作为算法的某种策略。从实现角度来看，仿函数是一种重

载了 的 或者 

适配器：一种用来修饰容器或者仿函数或迭代器接口的东西。

空间配置器：负责空间的配置与管理。从实现角度看，配置器是一个实现了动态空间

配置、空间管理、空间释放的 %

 六大组件的交互关系，容器通过空间配置器取得数据存储空间，算法通过迭代器

存储容器中的内容，仿函数可以协助算法完成不同的策略的变化，适配器可以修饰仿函数

1.3 STL 优点

 具有高可重用性，高性能，高移植性，跨平台的优点。

,高可重用性：中几乎所有的代码都采用了模板类和模版函数的方式实现，这

相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。关于模板的知

识，已经给大家介绍了。

,高性能：如 可以高效地从十万条记录里面查找出指定的记录，因为 

是采用红黑树的变体实现的。

,高移植性：如在项目 -上用 编写的模块，可以直接移植到项目 .上。

,

 之父 -/!亚历山大0斯特潘诺夫 创建者

2. STL 三大组件

常用的数据结构：数组链表树，栈1队列"集合

映射表根据数据在容器中的排列特性，这些数据分为序列式容器和关联式容

器两种。

 序列式容器强调值的排序，序列式容器中的每个元素均有固定的位置，除非用删

除或插入的操作改变这个位置。2 容器、3" 容器、 容器等。

 关联式容器是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格

的物理上的顺序关系，也就是说元素在容器中并没有保存元素置入容器时的逻辑

顺序。关联式容器另一个显著特点是：在值中选择一个值作为关键字 1，这个

关键字对值起到索引的作用，方便查找。4 容器 54 容

器

特定的数据结构，算法与数据结构相辅相成。

算法分为质变算法和非质变算法。

质变算法：是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等

非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、

寻找极值等等

再好的编程技巧，也无法让一个笨拙的算法起死回生。

2.3 迭代器

迭代器是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念

的实物。在6637((一书中提供了 89 中设计模式的完整描述，其中

 模式定义如下：提供一种方法，使之能够依序寻访某个容器所含的各个元素，而

迭代器的种类

输出迭代器 提供对数据的只写访问 只写，支持

前向迭代器 提供读写操作，并能向前推进迭代器 读写，支持、::、！

双向迭代器 提供读写操作，并能向前和向后操作 读写，支持、''，

随机访问迭代器 提供读写操作，并能以跳跃的方式访问

容器的任意数据，是功能最强的迭代器

读写，支持、''、;<、'

、6、6:、(、(:

2.3 案例