7.2　概述

这里是一个使用set类模板的例子，一个模拟传统数学集合的容器，该容器不接受重复值。下面创建的set与int整型数据一起工作：

成员函数insert（）完成所有的工作：它试图插入一个元素并且如果容器中已经存在相同的元素则不予插入。在使用一个集合中涉及的操作通常只限于插入元素和检测集合是否包含要插入的元素。也可以形成一个并集、一个交集或者一个差集，并测试一个集合是否是另一个集合的子集。在这个例子中，值0～9被插入集合25次，但是只有10个惟一的实例被接受。

现在考虑使用Intset.cpp的形式并修改它，用以显示包含在一个文档中的单词清单。该解决方案变得非常简单。

这里惟一的实质区别在于，集合保存字符串而不是整数。这些单词被从一个文件中取出来，但其他操作与Intset.cpp中的类似。该输出不仅显示出所有重复的单词都已经被忽略掉，而且由于set的实现方式，这些单词都被自动地排过序。

set是关联式容器（associative container）的一个例子，它是标准C++库提供的3种容器之一。下表列出了容器及其分类总结：

这些分类表示，针对不同的需要使用不同的模型。序列容器仅将它们的元素线性地组织起来，是最基本的容器类型。对于某些问题，这些序列需要附上某些特殊的属性，这正好是容器适配器要做的事情—它们对诸如队列或者栈的抽象建立模型。关联式容器则基于关键字来组织它们的数据，并允许快速地检索那些数据。

标准库中所有的容器都持有存入的对象的拷贝，并且根据需要扩展它们的资源，所以这些对象都必须是可构造拷贝（copy-constructible）（具有一个可访问的拷贝构造函数）和可赋值（assignable）拷贝（具有一个可访问的赋值操作符）的。一个容器与其他容器之间的关键不同之处在于它们在内存中存储对象的方式和向用户提供什么样的操作。

如读者已经知道的那样，vector是一种允许快速随机访问其中元素的线性序列。然而，向类似于vector这样排在一起的序列的中间插入一个元素的操作的开销却是很大的，就像对一个数组进行这种操作一样。一个deque（双端队列（double-ended-queue），读作“deck”）也允许几乎与vector一样快的随机访问，但是当需要分配新的存储空间时速度明显更快，而且很容易在序列的前端和后端加进新的元素。list是一个双向链表，所以在其上随机地移动某个元素的代价很高，但却可以用很低的代价向其中任何地方插入元素。因此，list、deque和vector在基本功能上很相似（它们都是线性序列），只是在各种操作的代价上有所不同。在一个程序的开始阶段可以选择它们中的任何一种使用，只在为了调整效率的时候尝试更换为其他容器。

很多问题的解决其实只需要一个像list、deque或vector这样简单的线性序列。所有这3个容器都含有用于向序列尾部插入一个元素的成员函数push_back（）（list和deque还有一个push_front（）成员，用于将一个元素插入序列前端）。

但是，如何在一个序列容器中检索存储的元素呢？对于vector和deque可以使用索引检索操作符operator[]，但对于list这是行不通的。这3种容器都可以使用迭代器来访问元素。每种容器都提供了相应类型的迭代器来访问它的元素。

虽然容器由值来保存对象（也就是说，它们持有对象的全部拷贝），而在某些时候希望容器存储一些指针，这些指针可以指向某一层次结构的对象，这样一来就可以利用类表现出的多态行为。考虑经典的“图形（shape）”例子，在这里所有的图形都有一个共同的操作集，而且拥有不同类型的图形。这里有一个程序例子，它看起来像使用STL vector来持有指向在堆中创建的不同类型Shape对象的指针：

类Shape、Circle、Square和Triangle的创建非常相似。Shape是一个抽象基类（因为有纯虚函数指明标记=0），它定义了所有Shape类型的接口。派生类覆盖虚函数virtual draw（）以实现相应的操作。现在要创建一串不同类型的Shape对象，并将它们原封不动存储在一个STL容器内。为方便起见，用类型定义：

为Shape*的vector创建一个别名，而用类型定义：

使用前面定义的别名为vector＜Shape＞：iterator创建另一个别名。注意，容器类型名必须用于产生合适的迭代器，它被定义为一个嵌套类。虽然存在不同类型的迭代器（前向、双向、随机等等），但它们都拥有同一个基本接口：可以使用++对它们进行增1操作，可以对迭代器解析以便产生它们当前选中的对象，而且可以测试它们以查看是否已经到了序列的末尾。这就是在90%的时间里要做的事情。这也正是前面例子中所做的事情：一个容器被创建以后，它被填入不同类型的Shape指针。注意，向上类型转换发生在当Circle、Square或者Rectangle指针被加入Shapes容器中去的时候，容器并不知道加入的指针的具体类型，作为替代它只持有Shape。一旦指针被装入容器，它就失去了明确的特性而成为了一个匿名的Shape*。这正是我们想要的：将它们全都投掷进容器，然后再利用多态性把它们挑选出来。

第1个for循环创建一个迭代器，并且通过调用容器的begin（）成员函数将其设置为指向序列的开始端。所有的容器都有begin（）和end（）成员函数，分别用来产生选择序列开始端和超越末尾的迭代器。可以通过确认迭代器不等于通过调用end（）函数产生的迭代器的办法来测试操作是否已经完成；不要使用＜或者＜=。只有！=和==测试方式起作用，所以通常将循环写成如下形式：

这条语句的意思是“遍历序列中的每一个元素。”

对迭代器做什么才可以产生它所选择的元素呢？可以通过‘’（这实际上是一个重载了的操作符）解析其引用（请读者思考其他方法）来实现。返回的是容器持有的任何东西。这个容器持有Shape，所以这就是*i所产生的结果。如果希望调用Shape的成员函数，必须使用操作符-＞，因此写出下面的一行：

这将会调用迭代器当前选择的Shape*的draw（）成员函数。这里的括号虽然难看，但却是产生运算符优先级所必需的。

当这些对象已经被销毁或者在其他情况下这些指针被删除时，STL容器并不会自动地为它们包含的指针调用delete。如果用new在堆中创建了一个对象，并将其指针存放到某个容器中，这个容器不会提示该指针是否同时也存入到了另一个容器，也不会提示它是否指向堆内存中的开始位置。用户必须始终负责管理自己的堆内存的分配。程序中的最后一行遍历并且删除容器中所有的对象，以便彻底地实施清理工作。处理容器中指针最容易和最安全的办法就是使用智能（smart）指针。要注意的是auto_ptr并不能用于这种目的，所以必须在C++标准库以外寻找适当的智能指针。^[1]

可以修改这个程序中的两行以便改变本例中使用的容器类型。用包含＜list＞来替代包含＜vector＞，并且将第1个typedef改写如下：

以替代正在使用vector。对其他任何地方不做修改。可以这样做不是因为由继承强加了一个接口（在STL只有很少一点继承），而是因为按STL的设计者采用的惯例已经强加了接口，所以可以非常准确地进行这类交换。现在就可以很容易地在vector与list或是任何其他支持相同接口（语法和语义上均相同）的容器之间进行变换，并且看看对于需求来说哪种容器工作起来最快。

7.2.1　字符串容器

在前面的例子中，在main（）的最后需要遍历整个的链表，并且用delete删除所有的Shape指针：

STL容器确保在其自身被销毁时将调用其包含的每个对象的析构函数。然而，指针并没有析构函数，因此用户必须自己用delete删除它们。

这里明显看到STL中的一个疏漏：在任何STL容器中都没有自动用delete删除它们包含的指针的设施，所以必须人工地自行解决。这表明STL的设计者们似乎认为指针的容器并不是一个有趣的问题，但事实并不是这样的。

由于存在多重成员资格（multiple membership）问题，使得自动删除一个指针成为问题。如果一个容器持有一个指向某个对象的指针，并不表明那个指针就不会在另一个容器中出现。Trash指针链表中的一个指向Aluminum对象的指针，也可能存在于一个Aluminum指针链表中。如果发生了这种情况，哪个链表负责清理这个对象—即哪个链表“拥有”这个对象呢？

这个问题事实上可以通过在链表中存储对象而不是指针来解决。当链表被销毁的时候似乎它包含的对象也必须被销毁。在这里，当看到创建一个包含string型对象的容器时，STL表现出了它的闪光点。下面的例子将每一输入行作为一个string型字符串对象存入一个vector＜string＞中：

一旦名为strings的vector＜string＞被创建，文件中的每一行都作为一个string对象被读入并且放入vector中：

对该文件的操作是向其中添加行号。一个stringstream对象提供了简便的方法将一个int型数字转换为一个用字符表示那个整数的string。

因为操作符operator+已被重载，所以组合string对象是相当容易的。非常合乎情理，迭代器w可以解析以便产生一个既可作为右值又可作为左值的字符串。

通过迭代器可以反向给容器中的元素进行赋值，这可能会让人感到惊讶，但这就是对STL的精心设计做出的贡献。

因为vector＜string＞包含对象，这里有两件事值得注意。第一，就像前面解释过的那样，不必明确地清理string对象。即便将指向这些string对象的地址作为指针放入其他容器也一样，显而易见strings就是“主链表”，它拥有对那些对象的所有权。

第二，有效地使用对象的动态创建方法，并且还绝不使用new或者delete！因为已经保存了给予它的对象拷贝，所有这些问题交由vector进行处理。因此能够有效地清理编码。

7.2.2　从STL容器继承

那种即刻就能创建出一个元素序列的能力是令人惊异的，这使人们回想起以前为解决这个特殊的问题时花费了多少时间。比如，很多实用的程序都包括这样的功能，将一个文件读进内存，修改该文件，然后再写回到磁盘上。读者也可以用StringVector.cpp中的那些功能并将其打包成一个类，以便以后使用。

现在的问题是：在程序设计中，是创建一个vector类型的成员对象，还是采用继承的方式派生出一个类似的对象？一般情况下，面向对象设计准则更倾向于使用组合（成员对象）而不是继承，但是有些标准算法盼望有这样一些序列，它们实现某个特殊的接口，因此继承的使用常常是必需的。

构造函数打开文件，将其读入到FileEditor，再用成员函数write（）将包含string的vector写入任何一个输出流ostream。注意，在write（）中可以使用一个默认的参数作为引用。

其实现相当简单：

来自StringVector.cpp的函数在这里仅被重新打包。这是类进化的常用方法—程序员在开始时创建一个程序来解决某一特殊的应用，然后发现其中有些通用的功能，就可以把它们变成一个类。

现在，那个行号产生程序可以用FileEditor重新编写如下：

现在，用于读取文件的操作都在构造函数中了：

（或者在成员函数open（）中），而写操作发生在单独的一行中（默认将数据发送输出到cout）：

该程序块被包含进来用以对内存中的文件进行修改。

[1]随着更多的smart指针类型将加入下一个版本的标准，情况将会发生变化。如果想要先了解它们，可以在www.boost.org看到这些智能指针。