《抽象容器类型.doc》由会员分享，可在线阅读，更多相关《抽象容器类型.doc（52页珍藏版）》请在金锄头文库上搜索。
1、抽象容器类型顺序容器(sequence container)拥有由单一类型元素组成的一个有序集合。两个主要的顺序容器是list和vector。第三个顺序容器为双端队列deque，发音为“deck”，它提供了与vector相同的行为，但是对于首元素的有效插入和删除提供了特殊的支持。例如，在实现队列时（队列是一种抽象，用户每次总是获取第一个元素），deque比vector更为合适。关联容器(associative container)支持查询一个元素是否存在，并且可以有效也获取元素。两个基本的关联容器是map(映射)和set(集合)。Map是一个键/值（key/value）对；键(key)用于查询
2、，而值(value)包含我们希望使用的数据。例如，map可以很好地支持电话目录，键是人名，值是相关联的电话号码。Set包含一个单一键值，有效支持关于元素是否存在的查询。例如，当我们要创建一个单词数据库，且它包含在某个文本中出现的单词时，文本查询系统对能会生成一个单词集合以排除the, and 以及but等等。程序将顺次读取文本中的每个单词，检查它是否属于被排除单词的集合，并根据查询的结果将其丢弃或者放入数据库中。Map和set都只包含每个键的唯一出现，即每个键只允许出现一次.multimap（多映射）和multiset(多集合)支持同一个键的多次出现。例如，我们的电话目录可能需要为单个用户支持
3、多个列表 ，一种实现方法是使用multimap.我们的文本查询系统文本查询系统应该由什么构成呢？1 用户指定的任意文本文件。 2 一个逻辑查询机制，用户可以通过它查询文本中单词或相邻的单词序列。如果一个单词或相邻的单词序列被找到，则程序显示出该单词或单词序列的出现次数。如果用户希望的话，则包含单词或单词序列的句子也会被显示出来。例如，如果用户希望找到所有对Civil War或Civil Rights的引用，则查询可能如下：Civil & ( War | Rights )查询结果如下：Civil: 12 occurrencesWar: 48 occurrencesRights: 1 occurr
4、enceCivil & War: 1 occurrenceCivil & Rights: 1 occurrence(8) Civility, of course, is not to be confused withCivil Rights, nor should it lead to Civil War.这里（8）表示文本中句子的序号。我们的系统应该不会将同一个词显示多次，而且多个句子应该以升序显示。我们的程序需要支持哪些任务呢？1. 它必须允许用户指明要打开的文本文件的名字2. 它必须在内部组织文本文件，以便能够识别出每个单词在句子中出现的次数，以及在该句子中的位置3. 它必须支持某种形式
5、的布尔查询语言。在我们的例子中，它将支持：&：在一行中，两个单词不仅存在，而且相邻|：在一行中，两个单词至少有一个存在；！：在一行中该单词不存在；()：把子查询组合起来的方式因此，我们可以写：Lincoln来找到所有出现单词Lincoln的句子，或者写：! Lincoln来找到所有没有出现出现单词Lincoln的句子，或者写：( Abe | Abraham ) & Lincoln将挑选出那些显式地引用Abe Lincoln和Abraham Lincoln的句子。我们将给出系统的两种实现。在本章中，我们给出一个实现，它把单词项及其相关联的行列位置当作一个map,来解决文本文件的检索和存储问题。为
6、了运用这个方案，我们提供了一个单个词的查询系统。我们使用下列六行作为文本示例，经过我们的处理之后（这包括读入文本的每一行，把它们分成独立的单词，去掉标识符号，把大写字母变成小写，提供关于后缀的最小支持，以及去掉无语义的词比如and, a 和the），支持单词查询的文本的内部存储形式看起来如下所示：alice (0,0)alive (1,10)almost (1,9)ask (5,2)beautiful (2,7)bird (2,3),(2,9)blow (1,3)daddy (0,8),(3,3),(5,5)emma (0,1)fiery (2,2),(2,8)flight (2,5)flow
7、ing (0,4)hair (0,6),(1,6)has (0,2)like (2,0)long (0,3)look (1,8)magical (3,0)mean (5,4)more (4,12)red (0,5)same (4,5)say (0,9)she (4,0),(5,1)shush (3,4)shyly (5,0)such (3,8)tell (2,11),(4,1),(4,10)there (3,5),(5,7)thing (3,9)through (1,4)time (4,6)untamed (3,2)wanting (4,7)wind (1,2)下面的简单查询示例使用了本章实现
8、的程序（斜体为用户输入）：please enter file name: alice_emmaenter a word against which to search the text.to quit, enter a single character = alicealice occurs 1 time:( line 1 ) Alice Emma has long flowing red hair. Her Daddy saysenter a word against which to search the text.to quit, enter a single character = d
9、addydaddy occurs 3 times:( line 1 ) Alice Emma has long flowing red hair. Her Daddy says( line 4 ) magical but untamed. Daddy, shush, there is no such thing,( line 6 ) Shyly, she asks, I mean, Daddy, is there?enter a word against which to search the text.to quit, enter a single character = phoenixSo
10、rry. There are no entries for phoenix.enter a word against which to search the text.to quit, enter a single character = .Ok, bye!Vector还是list?我们的程序必须要做的第一件事情是存储来自文本文件的未知数目的单词。这些单词将被依次存储为string对象。我们的第一个问题是，应该把单词存储在顺序容器不是在关联容器中？从某种意义上讲，我们需要支持查询单词是否存在，如果存在的话，还要获取到它在文本中相关的出现位置。因为我们需要查找并获取一个值，所以关联容器map是最
11、合适的容器类型。但是，在此之前，我们只需要简单地把输入文本存储起来以供后续处理（即去掉标识符号，处理后缀等等）。对于这个前处理过程，我们只需要顺序容器，而不是关联容器。问题是，它应该是vector还是list?如果曾经在C语言中或在C+标准化之前编写过程序，那么你的第一个选择可能是：如果在编译时元素的个数已知，则使用数组。如果元素的个数未知或者可能变化范围很大，则使用list，为每个对象动态分配存储区，然后再把它们顺序链接在list中。但是，这样的选择规则对于顺序容器类型并不适用：vector,deque以及list都是动态增长的。在这三者之中选择的准则主要是关注插入特性以及对元素的后续访问要
12、求。Vector表示一段连续的内存区域，每个元素被顺序存储在这段内存中。对vector的随机访问（比如先访问元素5，然后访问15，然后再访问7等等）效率很高，因为每次访问离vector起始处的位移都是固定的。但是，在任意位置，而不是在vector末尾插入元素，则效率很低，因为它需要待插入元素右边的每个元素都拷贝一遍。类似地，删除任意一个，而不是vector的最后一个元素，效率同样很低，因为待删除元素右边的每个元素都必须被复制一遍。这种代价对于大型的、复杂的类对象来说尤其大。（一个deque也表示一段连续的内存区域，但是，与vector不同的是，它支持高效地在其首部插入和删除元素。它通过两级数组
13、结构来实现，一级表示实际的容器，第二级指向容器的首和尾。）List表示非连续的内存区域，并通过一对指向首尾元素的指针双向链接起来，从而允许向前或向后两个方向进行遍历。在list的任意位置插入和删除元素的效率都很高；指针必须被重新赋值，但是，不需要用拷贝元素来实现移动。另一方面，它对随机访问的支持并不好；访问一个元素需要遍历中间的元素。另外，每个元素还有两个指针的额外空间开销。下面是选择顺序容器类型的一些准则：- 如果我们需要随机访问一个容器，则vector要比list好得多。- 如果我们已知要存储元素的个数，则vector又是一个比list好的选择。- 如果需要的不只是在容器两端插入和删除元素
14、，则list显然要比vector好。- 除非我们需要在容器首部插入和删除元素，否则vector要比deque好。如果我们既需要随机访问元素，又需要随机插入和删除元素，那么又该怎么办呢？我们需要在“随机访问的代价”和“拷贝右边或左边相邻元素的代价”之间进行折衷。一般来说，应该是由应用程序的主要操作（查找或插入）来决定容器类型的选择。（为了做这个决定，我们可能需要知晓两种容器类型的性能。）如果两种容器类型的性能都不能够使我们满意，则需要自己设计更复杂的数据结构。当我们不知道需要存储的元素的个数（即容器需要动态增长），并且不需要随机访问元素，以及在首部或者中间插入元素时，我们该如何决定选择哪一个容器
15、类型呢？在这种情况下，list和vector哪一个更有效？List以简单方式增长：每当一个新对象被插入到list中时，插入处的两个元素的前指针和后指针被重新赋值为指向新对象。新对象的前后指针被初始化为指向这两个元素。List只占有其包含的元素所必需的存储区。额外的开销有两个方面；与每个值相关联的两个附加指针，以及通过指针进行的间接访问。动态vector的表示和额外开销更加复杂。Vector怎样自己增长一个需要动态增长的vector必须分配一定的内存以便保存新的序列、按顺序拷贝旧序列的元素以及释放旧的内存。而且，如果它的元素是类对象，那么拷贝和释放内存可能需要对每个元素依次调用拷贝构造函数和析构函数。因为list的每次增长，只是简单地链接新元素，所以看起来好像没有问题。在动态增长的支持方面，这两个容器类型之中list更为有效。但实际上并不是这样。让我们来看看为什么。为了提高效率，实际上vector并不是随每一个元素的插入而增长自己，而是当vector需要增长自身时，它实际分配的空间比当前所需的空间要多一些，也就是说，它分配了一些额外的内存容量，或者说它预留了
