我的书签
添加书签
移除书签7.10 关联式容器
set、map、multiset和multimap被称为关联式容器（associative container），因为它们将关键字与值关联起来。至少map和multimap将关键字与值关联在一起，读者可以将一个set看成是没有值的map，它只有关键字（事实上，它们可以以这样的方式实现），multiset和multimap之间也有同样的关系。因此，由于结构的相似性，set和multiset都被归类为关联式容器。
关联式容器最重要的基本操作就是将对象放进容器。并且在set的情况下，要查看该对象是否已经在集合中；在map的情况下，需要先查看关键字是否已经在map中，如果存在，就需要为那个关键字设置关联的值。在这个主题上有很多变化，但是那是基本的概念。下面的例子显示了这些基本操作：
这里使用两个迭代器来创建set＜Noisy＞对象ns，使其进入一个Noisy对象的数组之内。但是也有一个默认的构造函数和一个拷贝构造函数，可以传入一个对象以便提供另一种做比较的方案。set和map两者都有一个成员函数insert（）用于向其中放入对象，可以用两种方式检查来看看对象是否已经存在于相应的关联式容器中。当给定一个关键字时，成员函数count（）会告之那个关键字在容器中存在多少次。（在set或者map中只能是0或者1，但是在multiset和multimap中则可能多于一个）。成员函数find（）将会产生一个指向首次出现（在set和map中则是惟一出现）给定关键字的元素的迭代器，或者如果找不到该关键字，将产生指向超越末尾的迭代器。所有的关联式容器都有count（）和find（）成员函数，这是很有意义的。这些关联式容器也都有成员函数lower_bound（）、upper_bound（）和equal_range（），它们仅仅对multiset和multimap有意义，正如读者所见。（但是不要试图去搞清楚它们对set和map到底有什么用，因为它们被设计用来处理某个范围的重复关键字，这在set和map容器中是不允许的。）
设计一个operator[]总是多少有点进退两难。因为它被有意地作为一个数组索引操作来对待，人们在使用前一般不会想到对其进行测试。但是，假如决定将索引设置为超出数组范围以外的位置时会发生什么事情？一种选择是抛出一个异常，但是对于一个map，“在数组范围以外的位置进行索引”意味着希望在那个位置创建一个新条目，这就是STL map的处理方式。在创建map＜int, Noisy＞nm之后的第1个for循环使用operator[]来“查找”对象，但实际上这是在创建新的Noisy对象！如果使用operator[]查寻一个值而它又不存在的话，这个map就会创建一个新的关键字-值对（为这个值使用默认的构造函数）。这意味着，如果实际上仅想要查寻某个对象并不想创建一个新条目，就必须使用成员函数count（）（看这个对象是否在那里）或者find（）（得到指向它的迭代器）。
与for循环一起使用运算符operator[]来打印容器中的值会有许多问题。首先，它需要整数关键字（在这里恰好是这样）。其次且更糟的是，如果所有的关键字都不是连续的，那么将会完成从0到整个容器的大小全部都进行计算，如果某些点没有关键字-值对存在，系统将会自动创建它们并会错过一些较高值的关键字。最后，如果观察for循环的输出，将会看到其工作非常繁忙。起先读者会相当迷惑，一个简单的查寻怎么会出现如此多的构造与析构呢？只有当看到map模板中关于operator[]的代码时答案才清楚为什么，这段代码如下所示：
函数map：insert（）接受一个关键字-值对，如果在映像中已有与给定的关键字在一起的条目，就什么也不做—否则它为该关键字插入一个条目。在两者之中任一情况下，它返回一个新的关键字-值对，该关键字-值对的第1个元素持有指向被插入对的迭代器，如果发生了插入操作，该对的第2个元素持有值为真。成员first和second分别给出了关键字和值，因为map：value_type实际上只是一个为std：pair进行类型定义的typedef：
读者已经在前面看到了std：pair模板。它是两个独立类型值的简单持有者，就像在其定义中所看到的那样：
pair模板类非常有用，特别是想要一个函数返回两个对象的时候（因为一个return语句只能返回一个对象）。为了创建一个关键字-值对pair，甚至还有一个快捷的称为make_pair（）的函数，它用在AssociativeBasics.cpp中。
追溯上面执行的各个步骤，map：value_type是map的一个关键字-值对pair—实际上，它是map的一个条目。但是要注意，pair由值封装它的对象，这意味着将对象装入pair之内，拷贝构造是必须的。因此，在map：operator[]的tmp创建过程中，对于每个pair中的对象将包括至少一个拷贝构造函数调用和一个析构函数调用。在这里，可以很容易地完成这些操作，因为关键字是int型的。但是，如果想要看看根据map：operator[]的活动方式到底能产生什么样的结果，请运行下面这个程序：
读者将会看到，插入和查寻两者都会产生很多额外的对象，这是因为tmp对象的创建。如果回过来看map：operator[]，就会看到第2行调用了insert（），并向其传递tmp—即operator[]每次都进行了插入操作。函数insert（）的返回值是一种不同的pair类型，其first是一个指向刚刚插入的关键字-值对的迭代器，而second则是一个表示在该处是否发生了插入操作的bool值。可以看到，operator[]抓取了first（迭代器），对其进行解析以产生pair，然后返回second，即该位置上的值。
因此，从上面的描述看来，map具有“如果在那里没有条目的话就创建一个”的奇妙行为，但是从下面（具体操作）来看，就是在使用map：operator[]时总是得到很多额外的对象创建和析构操作。幸运的是，AssociativeBasics.cpp也演示了如何减少插入和删除操作的开销。如果不需要它，尽量避免使用operator[]。成员函数insert（）比operator[]稍微更有效些。对于一个set，仅仅持有一个对象，而对于map来说，持有的是关键字-值对；所以insert（）需要一个pair作为其参数。这里就是make_pair（）派得上用场的地方，就像在程序中所能看到的那样。
为了在一个map中查寻对象，可以使用count（）来查看这个关键字是否在map中，或者可以用find（）产生一个直接指向关键字-值对的迭代器。再次强调，因为map包含pair，这就是在解析它的时候为什么会产生迭代器的原因，所以选择first和second作为其参数。在运行AssociativeBasics.cpp的时候，读者将会注意到，使用迭代器的方法不会产生额外的对象的构造和析构操作。然而，就易编写或者易阅读的面向对象编码要求而言，这是不可取的。
7.10.1 用于关联式容器的发生器和填充器
在使用＜algorithm＞中的fill（）、fill_n（）、generate（）和generate_n（）函数模板向序列容器（vector、list和deque）中填充数据时，已经看到了它们是多么的有用。然而，它们的实现都使用operator=赋值的方式将值放进序列容器，而向关联式容器中添加对象的方式是使用它们各自的成员函数insert（）。因此，在尝试与关联式容器一起使用“填充（fill）”和“产生（generate）”函数的时候，默认的“赋值”行为将会产生问题。
一个解决方案就是复制“填充”和“产生”函数，创建新的一种能用于关联式容器的函数。结果是，只有fill_n（）和generate_n（）函数能被复制（fill（）和generate（）复制序列，这对于关联式容器来说没有什么意义），但是这个工作是相当简单的，因为可以利用头文件＜algorithm＞作为工作的根据：
读者可以看到，没有使用迭代器，容器类自身被传递了（当然，通过使用引用）。
这段代码演示了两条有价值的经验教训。第1条就是，如果有什么需要的工作某个算法不能做，可以复制与其最接近的算法，并且修改它以满足需要。在STL头文件中有很多手到擒来例子，从这一点来说，大多数工作实际上已经完成了。
第2条经验教训进一步指出：如果观察的时间足够长，就会发现在STL中有一种方法来做这个工作，而不必再发明任何新的东西。当前的问题可以用insert_iterator（调用inserter（）而产生）来解决，它调用insert（）而非operator=以便在容器中放入对象。这不是仅仅对front_insert_iterator或者back_insert_iterator的变更，因为那些迭代器使用各自的push_front（）和push_back（）。每个插入迭代器都因为其用于插入操作的成员函数各具各的优点而不尽相同，insert（）正是我们所需要的一个函数。这里有一个演示显示进行填充和产生map和set两个容器的例子。（它也可以用于multiset和multimap。）首先，创建一些模板化的发生器。（这似乎像是有点过分，但在需要它们的时候，用户绝不会知道。为此，它们被放置在一个头文件中。）
两个发生器都希望T可以进行增1操作，无论用什么来进行初始化，它们都仅使用operator++来产生新的值。PairGen创建一个STL pair对象作为其返回值，这也就是为什么可以使用insert（）向一个map或者multimap中放入对象的原因。
最后的函数是个一般用于输出流ostream的操作符operator＜＜，假定pair的每一个元素都支持流操作符operator＜＜，因此任何pair都能被打印。（这是在第5章中讨论过的名字空间std中奇怪的名字查寻的推论，在本章Thesaurus.cpp之后将再一次解释。）如下所示，这允许用copy（）来输出map：
传递给inserter的第2个参数是一个迭代器，它是最佳化的，暗示可以帮助较快地进行插入（而不总是从底层树形结构的根开始进行搜索）。因为insert_iterator可以用于很多不同类型的容器，对于非-关联式容器来说，它还有更多的意义—它是必需的。
注意ostream_iterator是如何被创建来输出一个pair的。如果未创建operator＜＜，它不会起什么作用。因为它是一个模板，它将自动地为pair＜int, int＞进行实例化。
7.10.2 不可思议的映像
一个普通的数组使用一个整数值来对连续排列的某种类型的元素集进行索引。map是一个关联式数组（associative array），这意味着，按照类数组的方式将一个对象与另一个对象关联到一起。而不是像处理普通数组的方式一样使用一个数字来选择某个数组元素，在这里利用一个对象来进行查寻！下面的例子对一个文本文件中的单词进行计数，因此索引是一个代表单词的string对象，被查寻的值就是保存字串（单词）总数的对象。
在一个类似于vector或list的单项容器中，仅保存着一样东西。但是在一个map中，将会得到两样东西：关键字（key）（用它来进行查寻，就像在mapname[key]中）以及作为对关键字进行查寻得到的结果值。如果只希望遍历整个map并列出每一个关键字-值对的话，可以使用一个迭代器，它在解析时产生一个包含了关键字及其值的pair对象。可以通过选择first和second访问pair对象中的成员。
这种将两项一起进行打包的相同思想也用于将元素插入map的操作，但是包含了关键字及值的pair是作为map实例化的一部分来进行创建的，该pair称为value_type。所以插入新元素操作的一个选择就是创建一个value_type对象，以适当的对象装载它，然后为map调用insert（）成员函数进行插入操作。下面的例子使用了上述的map的特性：如果尝试向operator[]传递一个关键字来查找某个对象，当那个对象不存在时，operator[]将会自动使用值对象的默认构造函数插入一个新的关键字-值对。以这种思想为基础，现在考虑一个单词计数程序的实现：
这个例子显示了零初始化（zero-initialization）的能力。考虑程序代码中的这行：
这个将int与word关联在一起的表达式进行增1操作。如果map映像中没有这样的一个单词，则作为该单词的关键字-值对就会自动地插入到map映像中，并调用返回值为0的伪构造函数int（）并将其值初始化为0。
打印整个列表需要一个能够遍历该列表的迭代器。（这里不存在用于map的快捷方式的copy（），除非需要再为map中的pair编写一个operator＜＜。）如前所述，解析该迭代器会产生一个pair对象，其中first成员为关键字，second成员为其值。
如果希望找到为某个特定单词的计数，可以使用数组的索引操作符，如下所示：
可以看到，map的主要优点之一就是其清楚的语法；一个关联式数组对于读者来说是直观的。（然而要注意的是，如果单词“the”已不在wordmap中，一个新的条目就会被创建！）
7.10.3 多重映像和重复的关键字
多重映像multimap是一个能包含重复的关键字的map。起初这可能似乎是一个奇怪的想法，但令人惊讶的这种情况却经常发生。比如电话号码簿，同一个名字可以有很多个条目。
假定读者正在监视野生动植物，需要跟踪每一种有斑点的动物出现的时间和地点。因此，你就可能看到很多同一种类的动物，它们都在不同的时间和不同的地点出现。因此，如果将动物的类型作为关键字，就需要一个multimap。如下所示：
将观察到的所有数据都封装到一个DataPoint类中，该类非常简单足以使用综合赋值和拷贝构造函数来对其进行操作。它用标准C库的时间函数来记录观察的时间。
在string数组animal中，要注意的是在初始化期间，char*构造函数将会自动地调用，这就使得对string数组进行初始化变得相当方便。因为在一个vector中较易使用动物的名字，所以在计算好数组的长度后，使用构造函数vector（iterator, iterator）来初始化一个vector＜string＞。
用于构建Sighting的关键字-值对是表示动物类型名称的string。DataPoint表示观察到该动物的时间和地点。标准的pair模板将这两个类型关联起来，并且使用类型定义产生Sighting类型。然后为Sighting创建一个ostream operator＜＜；这将允许对一个存储了Sighting的map或multimap进行迭代并显示它。
SightingGen产生在随机数据点随机观察到的数据用于测试。它有一个普通的operator（），这对于函数对象来说是必需的，但是它还有一个构造函数，用于获得和存储一个引用到vector＜string＞，这就是前面提到的存储动物名称的地方。
DataMap是一个包含了string-DataPoint对的multimap，这意味着它存储Sighting对象。用generate_n（）产生的50个Sighting对象来填充该DataMap，并且显示它们。（注意，因为存在一个接受Sighting的operator＜＜，所以可以创建一个输出流迭代器ostream_iterator。）此时就可以请用户选择他们想要查看所有观察记录中的哪一种动物的情况。如果键入q程序就会退出，但是如果选择一个动物的编号，就会调用equal_range（）成员函数。这将会返回一个指向匹配对pair集的起始元素的迭代器（DMIter）和一个指向该匹配对pair集的超越末尾的迭代器。因为从一个函数中只能返回一个对象，因此equal_range（）使用了pair。因为range对拥有匹配集的起始和终止迭代器，所以这些迭代器可以在copy（）函数中用来打印对某种特定类型动物的所有观察记录。
7.10.4 多重集合
读者已经知道set仅允许插入每个值的惟一一个对象。而multiset看起来则比较古怪，因为它允许插入每个值的多个对象。这似乎违反了“集合”的完整的思想，读者可能会问，“‘它’在这个集合中吗？”如果集合中存在着多个“它”，将意味着什么呢？
想一想就会明白，如果这些重复的对象确实完全相同，在一个集合中有多个相同值的对象意义并不大（对那些出现的对象进行计数的情况可能是一个例外，但是，就像在本章较早时看到的，这个问题可以使用另一种更优雅的方法来处理）。因此，每个重复的对象都应该有什么地方“不同于”其他的重复对象—最有可能是在比较期间那些未被用作关键字计算的不同的状态信息。也就是说，通过比较操作这些对象看起来相同，但是它们却包括一些不同的内部状态。
像任何STL容器都必须对其元素进行排序一样，multiset模板在默认情况下使用less函数对象来决定元素的顺序。它使用了被包含类的比较运算符operator＜，但可以允许用户用自己的比较函数来代替它。
考虑一个简单的包含一个用于进行比较的元素与另一个不用于进行比较的元素的类：
在X中，所有的比较都产生char c。因为在这个例子中使用了默认的less比较对象，比较由operator＜进行，这就是multiset所必需的全部工作。类Xgen随机产生X对象，但是用于比较的值被限制在'A'到'E'之间的范围内。在main（）函数中，创建一个multiset＜X＞并用Xgen向其中填入25个X对象，这就保证了那里存在重复的关键字。所以为了了解存在哪些惟一的关键字值，根据multiset创建了一个常规的set＜X＞（使用iterator、iterator构造函数）。这些值被显示出来，然后对在multiset中的每个关键字值都产生equal_range（）（equal_range（）在这里和在multimap中有着相同的意义：所有的元素都与进行匹配的关键字相匹配）。然后打印每个匹配的关键字集。
作为第2个例子，用multiset创建的一个（可能）版本更优雅的WordCount.cpp：
main（）函数中的设置与WordCount.cpp中完全相同，然后每个单词都只是被插入到multiset＜string＞中。一个迭代器被创建出来并且初始化为指向multiset的起始处；解析该迭代器就可以产生它所指向的当前单词。成员函数equal_range（）（并非通用算法）产生当前选中的单词的起始和终止迭代器，算法distance（）（在＜iterator＞中定义的）对该范围内的元素进行计数。然后，迭代器it向前移动到范围终止之处，并令其指向下一个单词。如果读者现在还不熟悉multiset的话，那么这里的代码就可能显得太复杂。但它的紧凑性和没有所需的诸如Count这样的支持类却具有很强的吸引力。
最后，这个容器到底是个真实地“集合”，或者还是应当使用别的名字来命名它呢？另一种选择是，可以将其命名为在某些容器库中定义的一般称为“袋子（bag）”的容器，因为一个袋子可以不加区别地保存任何东西—包括重复的对象。这样的命名比较接近实际情况，可是由于袋子没有对元素按怎样的顺序排列给出规范，所以它也不是完全适合。multiset（它要求所有重复的元素必须相互毗邻地存放）比起set的概念来其限制甚至更加严格。一个set实现可能使用散列函数（hashing function）来排列其元素，这样它将不会按排序的顺序存放这些元素。另外，如果想要不受限制地（即没有任何指定标准）存放一个对象串，可以使用vector, deque或者list。
