第7章　通用容器

容器类是一种特定代码重用问题的解决方案。它们是用于创建面向对象程序的构件，使程序内部模块的构建变得非常容易。

一个容器类描述了一个持有其他对象的对象。容器类如此重要以至于它们被认为是早期面向对象语言的基础。比如在Smalltalk中，程序员将编程语言看做一种与类库结合起来的翻译程序，而类库的关键就是容器类的集合。因此，C++编译器的供应商们很自然地也把容器类库包含在编译器中。读者将会注意到，本教材第1卷中以最简单的形式介绍过的vector是多么的有用。

就像很多其他早期的C++库一样，早期的容器类库遵循了Smalltalk的基于对象的层次结构（object-based hierarchy），这种结构在Smalltalk中工作得很好，但是它在C++中却变得如此笨拙而难以使用。这就需要另外的解决方法。

C++中处理容器是采用基于模板的方式。标准C++库中的容器提供了多种数据结构。这些数据结构可以与标准算法一起很好地工作，来满足常见的软件开发需求。

7.1　容器和迭代器

在解决一个特定的问题时，如果不知道到底需要多少个对象，或这些对象将要维持多长时间，也就不能预先知道怎样存储这些对象。而在程序实际运行前你并不知道要创建多大的存储空间。

在面向对象程序设计中大多数这样的问题解决起来似乎很简单；只须创建对象的另一种类型就可以了。对于存储问题，这种新的对象类型持有其他对象或者是指向这些对象的指针。这种新的对象类型，通常在C++中称为容器（在一些语言中也称为收集器（collection），每当必须适应放置在它内部的所有对象的需要的时候，容器都会自行扩展。所以不必预先知道容器中将要放入多少个对象；仅需要创建一个容器对象，然后由容器来处理全部细节。

幸运的是，一个好的面向对象编程语言都伴随着一个容器集。在C++中，它就是标准模板库（STL）。在某些库中，人们认为一个好的通用容器应该能够满足所有的需要，而在其他库中（特别是C++中）则针对不同的需要有不同类型的容器：一个vector用于高效地访问其中的所有元素，而一个链表list则用于高效地在其中的所有位置上进行插入操作，还有更多其他类型的容器，所以人们可以根据自己的需要来选择特定类型的容器。

所有的容器都有某种存入对象和取出对象的方法。将某一对象放进一个容器的方法是十分明显的；可用一个名为“压入”或“增加”或者类似名字的函数。而从容器中检索对象的方法却并不总是明确的。如果这是一个类似数组的实体，比如一个vector，可以使用一个索引检索操作符或函数来完成。但是，在很多情况下这样做并没有意义。而且，单一选择函数也有其局限性。如果需要在容器中操纵或者比较一组元素时该怎么办呢？

对于灵活的元素访问的解决方案就是使用迭代器，迭代器是一个对象，它的工作就是在容器中挑选元素并将其呈献给迭代器的使用者。作为一个类，迭代器同时也提供了一个抽象层，因此可以将容器的内部实现细节与用来访问容器的代码分隔开来。通过迭代器，容器可以被看做一个序列。迭代器允许遍历一个序列而无需考虑基本结构—即不管它是一个vector、一个list、一个set还是其他结构。如此一来，就提供了这样的灵活性：即使在轻易地改变了底层的数据结构以后，也不会扰乱遍历容器的程序代码。将迭代操作从容器的控制下分隔开来，也允许同时存在的多重迭代器。

从设计的观点来说，人们实际上想要做的事情不过就是需要一个序列，并能够操纵该序列以解决自己的问题。如果序列的一个类型可以满足所有要求的话，就没有必要使用不同的类型。基于两种原因需要在容器中进行选择。首先，各种容器提供了不同的接口类型和外部行为。stack具有与queue不同的接口和行为，对于一个set或一个list而言这也是不同的。其中的某一个容器可能比其他容器能够为问题提供更加灵活的解决方案，或者它能提供传达人们设计意图的更清晰的抽象。其次，不同的容器对于某些操作可能具有不同的效率。比如，在vector和list之间进行比较，效率就会有所不同。它们都是具有几乎相同的接口和外部行为的简单序列。但是某些操作却可能具有完全不同的代价。在vector中对元素的随机访问只是一个时间恒定的操作；无论选择哪一个元素它的时间代价都是一样的。然而，通过遍历的方式对一个list中的元素进行随机访问却是一个代价巨大的操作，元素在list中的位置越靠后，所需要的时间就越长。另一方面，如果要想向一个序列的中间插入一个元素，使用list的代价却比vector低。这些操作以及其他操作的效率依赖序列的底层结构。在设计阶段，可能开始时使用一个list，后来又在调整性能时转而使用vector，或者反过来。使用了迭代器，就使那些只遍历序列的代码与底层序列实现的改变隔离开来。

要记住的是，容器仅仅是一个存储对象的储存柜。如果那个储存柜满足了人们所有的要求，或许确实没有必要了解它是如何实现的。如果读者是在那种内在开销来自于其他因素的编程环境中工作的话，一个vector和一个list之间代价的差别也许就没那么重要了。可能的需要只是序列的一种类型。你甚至可以想象一种“完美”的容器抽象，它可以根据其使用方法自动地调整底层的实现。[1]

STL参考文档

如前一章所述，读者也将注意到在本章中并没有包含用于描述每个STL容器的成员函数详尽的文档。虽然本章将描述我们使用到的成员函数，是我们没有给出其他成员函数的完整描述。我们推荐一些关于Dinkumware、Silicon Graphics以及STLPort STL实现的可利用的在线资源。[2]

[1]这是一个State模式的例子，将在第10章介绍。

[2]请访问http：//www.dinkumware.com、http：//www.sgi.com/tech/stl或http：//www.stlport.org。