第15章 标准模板库简介

简单地说，标准模板库（STL）是一组模板类和函数，向程序员提供了：

• 用于存储信息的容器；

• 用于访问容器存储的信息的迭代器；

• 用于操作容器内容的算法。

本章概述STL的这3个重要方面。

15.1 STL容器

容器是用于存储数据的STL类，STL提供了两种类型的容器类：

• 顺序容器；

• 关联容器。

另外，STL还提供了被称为容器适配器（Container Adapter）的类，它们是顺序容器和关联容器的变种，包含的功能有限，用于满足特殊的需求。

15.1.1 顺序容器

顾名思义，顺序容器按顺序存储数据，如数组和列表。顺序容器具有插入速度快但查找操作相对较慢的特征。

STL顺序容器包括：

• std::vector——操作与动态数组一样，在最后插入数据；可将vector视为书架，您可在一端添加和拿走图书；

• std::deque——与std::vector类似，但允许在开头插入或删除元素；

• std::list——操作与双向链表一样。可将它视为链条，对象被连接在一起，您可在任何位置添加或删除对象；

• std::forward_list——类似于std::list，但是单向链表，只能沿一个方向遍历。

STL vector类与数组类似，允许随机访问元素，即可使用下标运算符（[ ]）指定元素在 vector中的位置（索引），从而直接访问或操作元素。另外，STL vector是动态数组，因此能够根据应用程序在运行阶段的需求自动调整长度。为保留数组能够根据位置随机访问元素的特征，大多数STL vector实现都将所有元素存储在连续的存储单元中，因此需要调整长度的 vector 通常会降低应用程序的性能，这取决于它包含的对象类型。第4章简要地介绍了vector（参见程序清单4.4），而第17章将更详细地讨论该容器。

可将STL list类视为普通链表的STL实现。虽然 list中的元素不能像STL vector中的元素那样随机访问，但list可使用不连续的内存块组织元素，因此它不像std::vector那样需要给内部数组重新分配内存，进而导致性能问题。STL list类将在第 18章更详细地讨论。

15.1.2 关联容器

关联容器按指定的顺序存储数据，就像词典一样。这将降低插入数据的速度，但在查询方面有很大的优势。

STL提供的关联容器包括：

• std::set——存储各不相同的值，在插入时进行排序；容器的复杂度为对数；

• std::unordered_set——存储各不相同的值，在插入时进行排序；容器的复杂度为常数。这种容器是C++11新增的；

• std::map——存储键-值对，并根据唯一的键排序；容器的复杂度为对数；

• std::unordered_map——存储键-值对，并根据唯一的键排序；容器的复杂度为对数。这种容器是C++11新增的；

• std::multiset——与set类似，但允许存储多个值相同的项，即值不需要是唯一的；

• std::unordered_multiset——与 unordered_set 类似，但允许存储多个值相同的项，即值不需要是唯一的。这种容器是C++11新增的；

• std::multimap——与map类似，但不要求键是唯一的；

• std::unordered_multimap——与unordered_map类似，但不要求键是唯一的。这种容器是C++11新增的。

可通过谓词函数编程定制STL容器的排序标准。

有些STL实现也支持关联容器hashset、hash_multiset、hash_map和hash_multimap，它们与标准支持的unordered容器类似。在有些情况下，hash_和unordered_*容器有更好的元素搜索性能，因为其元素访问时间为常量（不依赖于容器包含的元素数）。通常，这些容器提供了与相应的标准容器相同的公有方法，因此使用起来很容易。

使用遵循标准的容器时，代码将更容易在不同平台和编译器之间移植，因此是更好的选择。另外，虽然遵循标准的容器的性能呈对数降低，但这可能并不会严重影响应用程序。

15.1.3 选择正确的容器

显然，可能有多种STL容器能够满足应用程序的需求，这时必须做出选择，这种选择很重要，因为错误的选择将导致应用程序性能低下。

因此，在选择容器前，评估各种容器的优缺点很重要，如表15.1所示。

表15.1 STL容器类的特点

续表

15.1.4 容器适配器

容器适配器（Container Adapter）是顺序容器和关联容器的变种，其功能有限，用于满足特定的需求。主要的适配器类如下。

• std::stack：以 LIFO（后进先出）的方式存储元素，让您能够在栈顶插入（压入）和删除（弹出）元素。

• std::queue：以FIFO（先进先出）的方式存储元素，让您能够删除最先插入的元素。

• std::priority_queue：以特定顺序存储元素，因为优先级最高的元素总是位于队列开头。

这些容器将在第24章详细讨论。

15.2 STL迭代器

最简单的迭代器是指针。给定一个指向数组中的第一个元素的指针，可递增该指针使其指向下一个元素，还可直接对当前位置的元素进行操作。

STL中的迭代器是模板类，从某种程度上说，它们是泛型指针。这些模板类让程序员能够对STL容器进行操作。注意，操作也可以是以模板函数的方式提供的STL算法，迭代器是一座桥梁，让这些模板函数能够以一致而无缝的方式处理容器，而容器是模板类。

STL提供的迭代器分两大类。

• 输入迭代器：通过对输入迭代器解除引用，它将引用对象，而对象可能位于集合中。最严格的输入迭代器确保只能以只读的方式访问对象。

• 输出迭代器：输出迭代器让程序员对集合执行写入操作。最严格的输出迭代器确保只能执行写入操作。

上述两种基本迭代器可进一步分为三类。

• 前向迭代器：这是输入迭代器和输出迭代器的一种细化，它允许输入与输出。前向迭代器可以是const的，只能读取它指向的对象；也可以改变对象，即可读写对象。前向迭代器通常用于单向链表。

• 双向迭代器：这是前向迭代器的一种细化，可对其执行递减操作，从而向后移动。双向迭代器通常用于双向链表。

• 随机访问迭代器：这是对双向迭代器的一种细化，可将其加减一个偏移量，还可将两个迭代器相减以得到集合中两个元素的相对距离。随机访问迭代器通常用于数组。

从实现层面说，可将“细化”视为继承或具体化。

15.3 STL算法

查找、排序和反转等都是标准的编程需求，不应让程序员重复实现这样的功能。因此STL以STL算法的方式提供这些函数，通过结合使用这些函数和迭代器，程序员可对容器执行一些最常见的操作。

最常用的STL算法如下所示。

• std::find：在集合中查找值。

• std::find_if：根据用户指定的谓词在集合中查找值。

• std::reverse：反转集合中元素的排列顺序。

• std::remove_if：根据用户定义的谓词将元素从集合中删除。

• std::transform：使用用户定义的变换函数对容器中的元素进行变换。

这些算法都是std命名空间中的模板函数，要使用它们，必须包含标准头文件<algorithm>。

15.4 使用迭代器在容器和算法之间交互

下面通过一个示例阐述迭代器如何无缝地将容器和STL算法连接起来。程序清单15.1所示的程序使用了STL顺序容器std::vector（它类似于动态数组）来存储一些整数，再使用std::find算法在集合中查找一个整数。请注意迭代器是如何在这两者之间搭建桥梁的。请不要担心语法和功能， std::vector等容器以及std::find等算法将分别在第17章和第23章详细讨论。如果您觉得这部分很复杂，可暂时跳过。

程序清单15.1 在vector中查找元素及其位置

输出：

分析：

程序清单 15.1 演示了如何使用迭代器遍历向量。迭代器是一个接口，将算法（find）连接到其要操作的数据所属的容器（如vector）。第20行声明了迭代器对象iArrayWalker，并将其初始化为指向容器开头，即vector的成员函数begin()返回的值。第22～29行演示了如何在循环中使用该迭代器遍历并显示vector包含的元素，这与显示静态数组的内容极其相似。迭代器的用法在所有STL容器中都相同。所有容器都提供了begin()函数和end()函数，其中前者指向第一个元素，后者指向容器中最后一个元素的后面。这就是第22行的while循环在end()前面而不是end()处结束的原因。第32行演示了如何使用find在vector中查找值。find操作的结果也是一个迭代器，通过将该迭代器与容器末尾进行比较，可判断find是否成功，如第36行所示。如果找到了元素，便可对该迭代器解除引用（就像对指针解除引用一样）以显示该元素。算法distance计算找到的元素的所处位置的偏移量。

如果将程序清单15.1中所有的vector都替换为deque，代码仍能通过编译并完美地运行。这表明迭代器让您能够轻松地使用算法和容器。

C++11

使用关键字auto让编译器确定类型

在程序清单15.1中，有多个迭代器声明，这些声明类似于下面这样：

上述迭代器类型定义看起来令人恐怖。如果您使用的是遵循C++11的编译器，可将这行代码简化成下面这样：

注意到将变量类型声明为auto时，必须对其进行初始化，这样编译器才能根据初始值推断变量的类型。

15.5 STL字符串类

STL提供了一个专门为操纵字符串而设计的模板类：std::basic_string<T>，该模板类的两个常用具体化如下。

• std::string：基于char的std::basic_string具体化，用于操纵简单字符串。

• std::wstring：基于wchar_t的std::basic_string具体化，用于操纵宽字符串。

第16章将详细讨论这个实用类，届时您将发现，它使得使用和操纵字符串非常简单。

15.6 总结

本章介绍了STL容器、迭代器和算法后面的基本概念，还简要地介绍了basic_string<T>，这个类将在本书后面详细讨论。容器、迭代器和算法是最重要的STL概念，深入理解它们有助于在应用程序中高效地使用STL。第17～25章将更详细地解释这些概念的实现及其应用。

15.7 问与答

问：我需要一个数组，但不知道它应包含多少个元素。请问我应使用哪种STL容器？

答：std::vector或std::deque能够很好地满足这种需求。这两种容器都负责管理内存，并可根据应用程序需求动态地调整大小。

问：我的应用程序经常需要执行搜索操作，我应选择哪种容器？

答：诸如std::map和std::set及其unordered变种等关联容器最适合于需要经常进行搜索的应用程序。

问：我要存储键-值对，并希望能够快速完成查找，但键可能不是唯一的。我应选择哪种容器？

答：关联容器std::multimap适合这种需求。multimap可存储非唯一的键-值对，查找速度也快，这是关联容器的一个特点。

问：我要开发一个能够在不同平台和编译器之间移植的应用程序，该程序还需要使用能够根据键快速查询的容器。我应使用std::map还是std::hash_map？

答：移植性是一个重要约束条件，必须使用遵循标准的容器。如果您使用的是遵循C++11的编译器，也可使用std::unordered_map。

15.8 作业

作业包括测验和练习，前者帮助读者加深对所学知识的理解，后者提供了使用新学知识的机会。请尽量先完成测验和练习题，然后再对照附录D的答案。在继续学习下一章前，请务必弄懂这些答案。

测验

1．要包含一个对象数组，并允许在开头和末尾插入对象，应使用哪种容器？

2．要存储元素以进行快速查找，应选择哪种容器？

3．要使用std:set存储元素，并根据除元素值外的其他条件进行存储和查找，可能吗？

4．STL的哪部分将算法和容器连接起来，让算法能够操作容器中的元素？

5．如果应用程序要移植到不同的平台，并使用不同的C++编译器进行编译，是否可选择使用容器hash_set？