15.10　容器概览

STL提供了一些容器：

标准容器

vector 连续存储的元素序列；应用作默认容器

list 双向链表；当你希望在不移动现有元素的情况下完成对元素的插入和删除时使用

deque list和vector的交叉；除非你对算法和计算机体系结构知识非常精通，否则不要使用它

map 平衡有序树；当你需要按值访问元素时使用它（参见16.6.1～16.6.3节）

multimap 平衡有序树，可以包含同一个key的多个拷贝；当你需要按值访问元素时使用它（参见16.6.1～16.6.3节）

unordered_map 哈希表；一种优化的map；当映射规模很大、对性能要求很高且可以设计出好的哈希函数时使用它（参见16.6.4节）

unordered_multimap 可以包含同一个key的多个拷贝的哈希表；一种优化的multimap；当映射规模很大、对性能要求很高且可以设计出好的哈希函数时使用它（参见16.6.4节）

set 平衡有序树；当你需要追踪单个值时使用它（参见16.6.5节）

multiset 可以包含同一个key的多个拷贝的平衡有序树；当你需要追踪单个值时使用它（参见16.6.5节）

unordered_set 类似unordered_map，但只保持值而非（键，值）对

unordered_multiset 类似unordered_multimap，但只保持值而非（键，值）对

array 大小固定的数组，不存在内置数组所存在的大部分问题（参见15.9节）

 

你能在书籍或在线文档中找到关于这些容器及其使用的大量信息。下面是一些高质量的参考资料：

Josuttis, Nicholai M. The C++ Standard Library: A Tutorial and Reference. Addison-Wesley, 2012. ISBN 978-0321623218. Use only the 2nd edition.

Lippman, Stanley B., Jose Lajoie, and Barbara E. Moo. The C++ Primer. Addison-Wesley, 2005. ISBN 0201721481. Use only the 5th edition.

Stroustrup, Bjarne. The C++ Programming Language. Addison-Wesley, 2012. ISBN 978-0321714114. Use only the 4th edition.

The documentation for the SGI implementation of the STL and the iostream library: www.sgi.com/tech/stl. Note that they also provide complete code.

你觉得被骗了吗？你觉得我们应该向你介绍所有容器及其应用吗？这是不可能的。相关的标准特性、技术以及库实在是太多了，你不可能一下就把它们全部掌握。程序设计领域是如此丰富，任何人都难以掌握所有特性和技术，它同时也是一门高雅的艺术。作为一名程序员，你必须养成查找语言特性、库和相关技术新信息的习惯。程序设计是一个时刻快速变化的领域，所以安于现状是走向落后的“秘诀”。“查一查”对很多问题都是一个很好的答案，而随着你的技能逐渐增长、成熟，这一答案会变得越来越重要。

另一方面，你会发现当你了解了vector、list、map以及第16章中介绍的标准算法后，其他STL容器或类STL容器的使用会变得非常容易，你还会发现非STL容器及其应用也变得容易理解了。

那么什么是容器呢？在上述所有资源中你都可以找到STL容器的定义。这里我们只给出一个非正式的定义。一个STL容器

是一个元素序列[begin():end())。

提供拷贝元素的拷贝操作。拷贝可以通过赋值操作或拷贝构造函数来实现。

其元素类型命名为value_type。

具有名为iterator和const_iterator的迭代器类型。迭代器提供具有恰当语义的*、++（前缀和后缀）、==以及!=运算符。list的迭代器还提供可以在序列中向后移动的--操作，它也被称为双向迭代器（bidirectional iterator）。vector的迭代器还提供--、[]、+以及-运算符，它也被称为随机访问迭代器（random-access iterator）（参见15.10.1节）。

提供insert()、erase()、front()、back()、push_back()、pop_back()以及size()等操作，vector和map还提供下标操作（例如运算符[]）。

提供比较运算符（==、!=、<、<=、>以及>=）进行元素比较。容器对<、<=、>、>=采用字典顺序，也就是说，它们按字典中开始单词排在首位的顺序比较元素。

上面这个列表只是给你一个关于容器的大概印象。更详细的内容请参见附录C。更准确的说明和更完整的特性列表可以参考《The C++ Programming Language》或C++标准。

一些数据类型提供了标准容器所要求的大部分特性，但又不是全部。我们称之为“拟容器”。最常见的如下表所示。

“拟容器”

T[n]内置数组 没有size()或其他成员函数；当可以使用vector、string或array等容器时，尽量不要选择内置数组

string 只存储字符，但对文本处理提供了许多有用的操作，例如连接（+和+=）；相对于其他字符串，应优先选用标准字符串

valarray 具有向量操作的数值向量，但有许多限制制约了高性能实现；只有当你需要进行大量向量计算时使用

 

另外，许多个人与组织都致力于开发符合（或接近符合）标准容器要求的容器。

如存疑，选用vector。除非有充分的理由，否则选用vector。

15.10.1　迭代器类别

在我们之前的讨论中，似乎所有迭代器都是可以通用的。其实，只有在进行简单的操作时它们才是通用的，比如对某个序列进行一次遍历并读取每个值一次。如果你希望完成更为复杂的操作，例如向后遍历或下标操作，就会需要一些更为高级的迭代器了。

迭代器类别

输入迭代器 我们可以用++向前移动，用*读取元素值。istream提供的就是这类迭代器，参见16.7.2节。如果(*p).m有效，则可使用简写形式p->m

输出迭代器 我们可以用++向前移动，用*写入元素值。ostream提供的就是这类迭代器，参见16.7.2节

前向迭代器 我们可以反复用++向前移动，用*读写元素（当然，元素不能是const的）。如果(*p).m有效，则可使用简写形式p->m

双向迭代器 我们可以用++向前移动，用--向后移动，用*读写元素（除非元素是const的）。list、map和set所提供的就是这类迭代器。如果(*p).m有效，则可使用简写形式p->m

随机访问迭代器 我们可以用++向前移动，用--向后移动，用*或[]读写元素（除非元素是const的）。我们可以对随机访问迭代器进行下标操作，用+向迭代器加上一个整数，用-向迭代器减去一个整数。我们可以通过对指向同一序列的两个迭代器进行减法操作来得到它们的距离。vector提供的就是这类迭代器。如果(*p).m有效，则可使用简写形式p->m

 

从这些提供的操作我们可以看出，当可以使用输出或输入迭代器时，也可以使用前向迭代器完成相同的功能。双向迭代器也是一种前向迭代器，而随机访问迭代器也是一种双向迭代器。我们可以把迭代器类别图示如下：

 

注意，由于迭代器种类并不是类，因此这个层次结构并非是用派生实现的类层次。

简单练习

1. 定义一个含有10个元素{0，1，2，3，4，5，6，7，8，9}的int型数组。

2. 定义一个含有10个同样元素的vector<int>。

3. 定义一个含有10个同样元素的list<int>。

4. 另外再定义一个数组、一个向量、一个链表，并分别把它们初始化为上面所定义的数组、向量和链表的拷贝。

5. 把数组中的每个元素值加2，把向量中的每个元素值加3，把链表中的每个元素值加5。

6. 编写一个简单的copy()操作。

该操作像标准库copy函数一样把[f1,e1)复制到[f2, f2+(e1-f1))并返回f2+(e1-f1)。注意如果f1==e1，那么该序列为空，此时不需要复制任何内容。

7. 使用你的copy把数组中的内容拷贝到向量中，再把链表中的内容拷贝到数组中。

8. 用标准库f?ind()来判断向量中是否含有值3，如果有则输出它的位置；用f?ind()来判断链表中是否含有值27，如果有则输出它的位置。第一个元素的位置为0，第二个元素的位置为1，以此类推。注意，如果f?ind()返回的是序列尾，则说明没有找到所查的元素。记住，每一步后都要进行测试。

思考题

1. 为什么不同人编写的代码看起来会不一样？请举例说明。

2. 会有哪些关于数据的简单问题？

3. 存储数据有哪些不同的方式？

4. 可以对一组数据做哪些基本操作？

5. 理想的数据存储方式应该是怎样的？

6. 什么是STL序列？

7. 什么是STL迭代器？它支持哪些操作？

8. 如何把迭代器移到下一个元素？

9. 如何把迭代器移到上一个元素？

10. 当你试图把迭代器移动到序列尾之后时会出现什么情况？

11. 哪些迭代器可以移动到上一个元素？

12. 为什么要把数据与算法分离开？

13. 什么是STL？

14. 什么是链表？它和向量本质上的区别是什么？

15. 链表中的链接是什么？

16. insert()的功能是什么？erase()呢？

17. 如何判断一个序列是否为空？

18. list中的迭代器提供了哪些操作？

19. 如何使用STL遍历一个容器？

20. 什么时候应该使用string而不是vector？

21. 什么时候应该使用list而不是vector？

22. 什么是容器？

23. 容器的begin()和end()应该实现什么功能？

24. STL提供了哪些容器？

25. 什么是迭代器类别？STL提供了哪几类迭代器？

26. 哪些操作是随机访问迭代器提供了而双向迭代器没有提供的？

术语

algorithm（算法） begin() doubly-linked list（双向链表）

array container（array容器） container（容器） element（元素）

auto contiguous（连续的） empty sequence（空序列）

end() linked list（链表） traversal（遍历）

erase() sequence（序列） using

insert() singly-linked list（单向链表） type alias（类型别名）

iteration（迭代） size_type value_type

iterator（迭代器） STL（标准模板库）

习题

1. 如果还未完成本章所有“试一试”，请完成。

2. 编译运行15.1.2节中的例子Jack-and-Jill。利用几个小文件作为输入测试它。

3. 回顾回文的例子（见13.7节），用不同技术重写15.1.2节中的Jack-and-Jill程序。

4. 用STL技术找到并修改15.3.1节Jack-and-Jill例子中的错误。

5. 为vector定义输入和输出运算符（>>和<<）。

6. 基于15.6.2节中的内容，为Document编写一个“查找并替换”操作。

7. 在一个未排序的vector<string>中查找按字典顺序排在最后的字符串。

8. 编写一个可以统计Document中字符总数的函数。

9. 编写一个可以统计Document中单词数的程序。该程序有两个版本：一种将单词定义为“以空白符分隔的字符序列”，另一种将单词定义为“一个连续的字母序列”。例如，在第一种定义下，alpha.numeric和as12b都是一个单词，而在第二种定义下它们则都为两个单词。

10. 编写另一个统计单词的程序。在该程序中，用户可以指定空白符集合。

11. 以list<int>为（引用）参数，创建一个vector<double>，并将链表中的元素拷贝到向量中。验证拷贝操作的完整性与正确性。然后将元素按照值升序排序并打印。

12. 完成15.4.1～15.4.2节中list的定义，并让high()能正确运行。分配一个Link表示链表尾之后一个位置。

13. 实际上，在list中我们并不需要一个“真的”尾后位置Link。改写上面的程序，用0表示指向（不存在的）尾后位置Link（list<Elem>::end()）的指针，这样可以使空列表的大小和一个指针的大小相同。

14. 定义一个单向链表slist，风格类似std::list。由于slist没有后向指针，list中的哪些操作可以合理地去掉？

15. 定义一个与指针vector很相似的pvector，不同之处在于pvector中的指针指向对象，而且其析构函数会对每个对象进行delete操作。

16. 定义一个与pvector很相似的ovector，不同之处在于[]和*运算符返回元素所指向的对象的引用，而不是返回指针。

17. 定义一个ownership_vector，像pvector一样保存对象指针，但为用户提供了一种机制，可以决定哪些对象为向量所有（即哪些对象由析构函数进行delete操作）。

18. 为vector定义一个范围检查迭代器（随机访问迭代器）。

19. 为list定义一个范围检查迭代器（双向迭代器）。

20. 运行一个小的计时实验来比较vector和list的使用代价。有关如何对程序进行计时的内容可以在26.6.1节中找到。生成N个属于区间[0，N)的int型随机数。每生成一个随机数就把它加入vector<int>中（该vector大小每次增加1）。保持该vector为有序的，也就是说，新元素插入位置之前的所有元素都小于等于新元素的值，而新元素之后的所有元素都大于新元素的值。用list<int>保存int完成相同的实验。在N取什么样的值时list会比vector快？请解释实验结果。该实验由John Bentley最先提出。

附言

如果我们有N种数据容器和M种想要对其执行的操作，那么结果很容易变成我们要编写N×M段代码。如果数据有K种不同的类型，那么代码的总数甚至会达到N×M×K。STL通过将元素类型作为参数（解决了因子K）以及将算法与数据访问分离解决了这一问题。通过利用迭代器实现任意算法对任意容器中数据的访问，我们只需编写N+M种算法。这大大简化了我们的工作。例如，如果我们有12种容器和60种算法，暴力方法需要编写720个函数；而STL的策略只需要编写60个函数和定义12种迭代器，这可以省去我们90%的工作。实际上，这还低估了节省的工作量，因为很多算法接受一对迭代器参数，而两个迭代器可以是不同类型（例如，参见习题6）。而且，STL还给出了算法定义规范，可以简化编写正确的、可组合的代码的工作，因此工作量的节省实际上会更大。