抽象容器类型.doc

抽象容器类型顺序容器(sequence container)拥有由单一类型元素组成的一个有序集合。两个主要的顺序容器是list和vector。第三个顺序容器为双端队列deque，发音为“deck”，它提供了与vector相同的行为，但是对于首元素的有效插入和删除提供了特殊的支持。例如，在实现队列时（队列是一种抽象，用户每次总是获取第一个元素），deque比vector更为合适。关联容器(associative container)支持查询一个元素是否存在，并且可以有效也获取元素。两个基本的关联容器是map(映射)和set(集合)。Map是一个键/值（key/value）对；键(key)用于查询，而值(value)包含我们希望使用的数据。例如，map可以很好地支持电话目录，键是人名，值是相关联的电话号码。Set包含一个单一键值，有效支持关于元素是否存在的查询。例如，当我们要创建一个单词数据库，且它包含在某个文本中出现的单词时，文本查询系统对能会生成一个单词集合以排除the, and 以及but等等。程序将顺次读取文本中的每个单词，检查它是否属于被排除单词的集合，并根据查询的结果将其丢弃或者放入数据库中。Map和set都只包含每个键的唯一出现，即每个键只允许出现一次.multimap（多映射）和multiset(多集合)支持同一个键的多次出现。例如，我们的电话目录可能需要为单个用户支持多个列表 ，一种实现方法是使用multimap.我们的文本查询系统文本查询系统应该由什么构成呢？1 用户指定的任意文本文件。 2 一个逻辑查询机制，用户可以通过它查询文本中单词或相邻的单词序列。如果一个单词或相邻的单词序列被找到，则程序显示出该单词或单词序列的出现次数。如果用户希望的话，则包含单词或单词序列的句子也会被显示出来。例如，如果用户希望找到所有对Civil War或Civil Rights的引用，则查询可能如下：Civil & ( War | Rights )查询结果如下：Civil: 12 occurrencesWar: 48 occurrencesRights: 1 occurrenceCivil & 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. 它必须支持某种形式的布尔查询语言。在我们的例子中，它将支持：&：在一行中，两个单词不仅存在，而且相邻|：在一行中，两个单词至少有一个存在；！：在一行中该单词不存在；()：把子查询组合起来的方式因此，我们可以写：Lincoln来找到所有出现单词Lincoln的句子，或者写：! Lincoln来找到所有没有出现出现单词Lincoln的句子，或者写：( Abe | Abraham ) & Lincoln将挑选出那些显式地引用Abe Lincoln和Abraham Lincoln的句子。我们将给出系统的两种实现。在本章中，我们给出一个实现，它把单词项及其相关联的行列位置当作一个map,来解决文本文件的检索和存储问题。为了运用这个方案，我们提供了一个单个词的查询系统。我们使用下列六行作为文本示例，经过我们的处理之后（这包括读入文本的每一行，把它们分成独立的单词，去掉标识符号，把大写字母变成小写，提供关于后缀的最小支持，以及去掉无语义的词比如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)flowing (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)下面的简单查询示例使用了本章实现的程序（斜体为用户输入）：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 = daddydaddy 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 = phoenixSorry. 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是最合适的容器类型。但是，在此之前，我们只需要简单地把输入文本存储起来以供后续处理（即去掉标识符号，处理后缀等等）。对于这个前处理过程，我们只需要顺序容器，而不是关联容器。问题是，它应该是vector还是list?如果曾经在C语言中或在C+标准化之前编写过程序，那么你的第一个选择可能是：如果在编译时元素的个数已知，则使用数组。如果元素的个数未知或者可能变化范围很大，则使用list，为每个对象动态分配存储区，然后再把它们顺序链接在list中。但是，这样的选择规则对于顺序容器类型并不适用：vector,deque以及list都是动态增长的。在这三者之中选择的准则主要是关注插入特性以及对元素的后续访问要求。Vector表示一段连续的内存区域，每个元素被顺序存储在这段内存中。对vector的随机访问（比如先访问元素5，然后访问15，然后再访问7等等）效率很高，因为每次访问离vector起始处的位移都是固定的。但是，在任意位置，而不是在vector末尾插入元素，则效率很低，因为它需要待插入元素右边的每个元素都拷贝一遍。类似地，删除任意一个，而不是vector的最后一个元素，效率同样很低，因为待删除元素右边的每个元素都必须被复制一遍。这种代价对于大型的、复杂的类对象来说尤其大。（一个deque也表示一段连续的内存区域，但是，与vector不同的是，它支持高效地在其首部插入和删除元素。它通过两级数组结构来实现，一级表示实际的容器，第二级指向容器的首和尾。）List表示非连续的内存区域，并通过一对指向首尾元素的指针双向链接起来，从而允许向前或向后两个方向进行遍历。在list的任意位置插入和删除元素的效率都很高；指针必须被重新赋值，但是，不需要用拷贝元素来实现移动。另一方面，它对随机访问的支持并不好；访问一个元素需要遍历中间的元素。另外，每个元素还有两个指针的额外空间开销。下面是选择顺序容器类型的一些准则：- 如果我们需要随机访问一个容器，则vector要比list好得多。- 如果我们已知要存储元素的个数，则vector又是一个比list好的选择。- 如果需要的不只是在容器两端插入和删除元素，则list显然要比vector好。- 除非我们需要在容器首部插入和删除元素，否则vector要比deque好。如果我们既需要随机访问元素，又需要随机插入和删除元素，那么又该怎么办呢？我们需要在“随机访问的代价”和“拷贝右边或左边相邻元素的代价”之间进行折衷。一般来说，应该是由应用程序的主要操作（查找或插入）来决定容器类型的选择。（为了做这个决定，我们可能需要知晓两种容器类型的性能。）如果两种容器类型的性能都不能够使我们满意，则需要自己设计更复杂的数据结构。当我们不知道需要存储的元素的个数（即容器需要动态增长），并且不需要随机访问元素，以及在首部或者中间插入元素时，我们该如何决定选择哪一个容器类型呢？在这种情况下，list和vector哪一个更有效？List以简单方式增长：每当一个新对象被插入到list中时，插入处的两个元素的前指针和后指针被重新赋值为指向新对象。新对象的前后指针被初始化为指向这两个元素。List只占有其包含的元素所必需的存储区。额外的开销有两个方面；与每个值相关联的两个附加指针，以及通过指针进行的间接访问。动态vector的表示和额外开销更加复杂。Vector怎样自己增长一个需要动态增长的vector必须分配一定的内存以便保存新的序列、按顺序拷贝旧序列的元素以及释放旧的内存。而且，如果它的元素是类对象，那么拷贝和释放内存可能需要对每个元素依次调用拷贝构造函数和析构函数。因为list的每次增长，只是简单地链接新元素，所以看起来好像没有问题。在动态增长的支持方面，这两个容器类型之中list更为有效。但实际上并不是这样。让我们来看看为什么。为了提高效率，实际上vector并不是随每一个元素的插入而增长自己，而是当vector需要增长自身时，它实际分配的空间比当前所需的空间要多一些，也就是说，它分配了一些额外的内存容量，或者说它预留了这些存储区（分配的额外容量的确切数目由具体实现定义）。这个策略使容器的增长效率更高-因此，实际上，对于小的对象,vector在实践中比list效率更高。让我们来看一看在C+标准库的Rogue Wave实现版本下的一些例子。但是首先我们要弄清楚容器的容量和长度(size)之间的区别。容量是指在容器下一次需要增长自己之前能够被加入到容器中的元素的总数（容量只与连续存储的容器相关：例如vector, deque或string。List不要求容量）。为了知道一个容器的容量，我们调用它的capacity()操作。而长度(size)是指容器当前拥有元素的个数。为了获得容器的当前长度，我们调用它的size()操作。例如：#include #include int main()vector ivec;cout ivec: size: ivec.size() capacity: ivec.capacity() endl;for ( int ix = 0; ix 24; +ix ) ivec.push_back( ix );cout ivec: size: ivec.size() capacity: ivec.capacity() endl;在Rogue Wave实现版本下，在ivec的定义之后，它的长度和容量都是0。但是在插入第一元素之后，ivec的容量是256,长度为1，这意味着在ivec下一次需要增长之前。我们可以向它加入256个元素。当我们插入第256个元素时，vector以下列方式重新自我增长，它分配双倍于当前容量的存储区，把当前的值拷贝到新分配的内存中，并释放原来的内存。正好稍后我们将要看到的，同list相比，数据类型越大越复杂，则vector的效率也就越低。表显示了各种数据类型。它们的长度，及其相关vector的初始容量。数据类型长度（字节）初始插入后的容量int4256double8128简单类(simple class) #11285String1285大型简单类(large simple class)80001大型复杂类(large complex class)80001正如你所看到的，在标准库的Rogue Wave实现版本下，在第一次插入时分配的元素缺省容量接近或等于1024字节，然后它随每次重分配而加倍。对于大型的数据类型，容量较小，所以元素的重分配和拷贝操作成为使用vector的主要开销（我们这里说的复杂类型是指类提供了一个拷贝构造函数和一个拷贝赋值操作符），下表显示了在list和vector中插入1千万个上述类型所花的时间（以秒为单位）。及显示了插入1万个元素的时间（当元素长度较大时就太慢了。）插入1千万个元素所需的时间数据类型List(s)vectorint10383.76double10.723.95简单的类(simpleclass)12.315.89string14.4211.80插入1万个元素的时间数据类型List(s)vector大型简单类(large simple class)0.362.23大型复杂类(large complex class)2.376.70正如你所看到的，对于小的数据类型，vector的性能要比list好得多，而对于大型的数据类型则相反，list的性能要好得多。区别是由于vector需要重新增长以及拷贝元素。但是，数据类型的长度不是影响容器性能的唯一标准。数据类型的复杂性也会影响到元素的插入的性能，为什么？无论是list不是vector,对于已定义拷贝构造函数的类来说，插入这样的类的元素都需要调用拷贝构造函数。（拷贝构造函数用该类型的一个对象初始化该类型的另一个对象）这正是说明了在简单类和string的链表之间插入代价的区别。简单类对象和大型简单类对象通过按位拷贝插入（一个对象的所有位被拷贝到第二个对象的位中），而string类对象和大型复杂类对象通过调用拷贝构造函数来插入。另外，随着每次重新分配内存，vector必须为每个元素调用拷贝构造函数。而且，在释放原来的内存时，它要为每个元素调用其相关类型的析构函数。Vector的动态自我增长越频繁，元素插入的开销就越大。当然，一种解决方案是当vector的开销变得非常大时，把vector转换成list。另一种经常使用的方案是，通过指针间接存储复杂的类对象。例如，当我们用指针存储复杂类对象时，在vector中插入10000个元素的开销从6.70s明显地降到0.82s。为什么？首先，容量从1增加到256，因此重新分配的次数大大减少。其次，指向类对象的指针的拷贝和释放不需要调用该类的拷贝构造函数和析构函数。Reserve()操作允许程序员将容器的容量设置成一个显式指定的值，例如：int main() vector svec;svec.reserve( 32 ); / 把容量设置为32/ .使svec的长度为0（即0个元素），而容量为32。但是，根据经验发现，用一个非1的缺省值来调整vector的容量看起来会引起性能退化。例如，对于string和double型的vector，通过reserve()增加容量导致很差的性能。另一方面，增加大型复杂类的容量，会大大改善了性能，如表所示调整容量时插入10000元素的时间容量时间(s)缺省值16.7040965.5581924.44100002.22注：非简单类：8000字节大小，并且带有构造函数和析构函数对于我们的文本查询系统，将使用一个vector来包含string对象，并且使用与它相关联的缺省容量。虽然当我们插入未知数目的string时，vector会动态增长，但是正如前面显示的计时情况来看，它的性能仍然比list好一些。定义一个顺序容器为了定义一个容器对象，我们必须包含相关联的头文件，应该是下列头文件之一：#include #include #include #include #include 容器对象的定义以容器类型的名字开始，后面是所包含的元素的实际类型，例如：vector svec;list ilist;定义了svec是一个内含string对象的主vector，以及ilist是一个int型对象的空list。svec和ilist都是空的。为了确认这一点，我们可以调用empty()操作符。例如：if ( svec.empty() != true ); / 喔, 有错误了插入元素最简单的方法是push_back(),它将元素插入在容器的尾部。例如：string text_word;while ( cin text_word )svec.push_back( text_word );每次从标准输入读取一个字符串放到text_word中。然后push_back()再将text_word字符串的拷贝插入到svec中。list和deque容器也支持push_front()，它把新元素插入在链表的前端。例如，假设我们有一个int型的内置数组如下：int ia 4 = 0, 1, 2, 3 ;用push_back():for ( int ix = 0; ix 4; +ix )ilist.push_back( ia ix );创建序列0,1,2,3,然而，如果使用push_front():for ( int ix = 0; ix 4; +ix )ilist.push_front( ia ix );则在ilist中创建序列3,2,1,0另外，我们或许希望为容器指定一个显式的长度。长度可以是常量，也可以是非常量表达式：#include #include #include extern int get_word_count( string file_name );const int list_size = 64;list ilist( list_size );vector svec(get_word_count(string(Chimera);容器中的每个元素都被初始化为“与该类型相关联的缺省值”。对于整数，将用缺省值0初始化所有元素。对于string类，每个元素都将用string的缺省构造函数初始化。除了用相关联的初始值来初始化每个元素外，我们还可以指定一个值，并用它来初始化每个元素。例如：list ilist( list_size, - 1 );vector svec( 24, pooh );除了给出初始长度外，我们还可以通过resize()操作重新设置容器的长度。例如，当我们写下面的代码时：svec.resize( 2 * svec.size() );我们将svec的长度加了一倍。每个新元素都被初始化为“与元素底层类型相关联的缺省值”。如果我们希望把每个新元素初始化为某个其他值，则可以把该值指定为第二个参数：/ 将新元素初始化为pigletsvec.resize( 2 * svec.size(), piglet );那么，svec的原始定义的容量是多少？它的初始长度是24个元素。它的初始容量可能是多少？对-svec的容量也是24。一般地，vector的最小容量是它的当前长度，当vector的长度加倍时，容量一般也加倍。我们也可以用一个现有的容器对象初始化一个新的容器对象。例如：vector svec2( svec );list ilist2( ilist );每个容器支持一组关系操作符，我们可以用来比较两个容器，这些关系操作符分别是：等于、不等于、小于、大于、小于等于，以及大于等于。容器的比较是指两个容器的元素之间成对进行比较。如果所有元素相等而且两个容器含有相同数目的元素，则两个容器相等。否则，它们不相等。第一个不相等元素的比较决定了两个容器的小于或大于关系。例如，下面是一个程序的输出，它比较了五个vector:ivec1: 1 3 5 7 9 12ivec2: 0 1 1 2 3 5 8 13ivec3: 1 3 9ivec4: 1 3 5 7ivec5: 2 4/ 第一个不相等元素: 1, 0/ ivec1 大于 ivec2ivec1 ivec2 / flaseivec2 ivec1 / true/ 第一个不相等元素: 5, 9ivec1 ivec3 / true/ 所有元素相等, 但是, ivec4 的元素少/ 所以ivec4 小于ivec1ivec1 ivec4 / false/ 第一个不相等元素: 1, 2ivec1 ivec2 / trueivec3 ivec1 / trueivec5 ivec2 / true我们能够定义的容器的类型有三个限制（实际上，它们只适用于用户定义的类类型）：- 元素类型必须支持等于操作符- 元素类型必须支持小于操作符- 元素类型必须支持一个缺省值（对于类类型，即指缺省构造函数）所有预定义数据类型，包括指针，都满足这些限制，C+标准库给出的所有类型也一样。迭代器迭代器(iterator)提供了一种一般化的方法，对顺序或关联容器类型中的每个元素进行连续访问。例如，假设iter为任意容器类型的一个iterator，则：+iter;向前移动迭代器，使其指向容器的下一个元素，而：*iter;返回iterator指向元素的值。每种容器类型都提供一个begin()和一个end()成员函数。- begin()返回一个iterator，它指向容器的第一个元素。- end()返回一个iterator,它指向容器的末元素的下一个位置。为了迭代任意容器类型的元素，我们可以这样写：for ( iter = container.begin();iter != container.end(); +iter )do_something_with_element( *iter );由于模板和嵌套类语法的原因，iterator的定义看起来有点吓人。例如，下面是一对iterator的定义，它们指向一个内含string元素的vector:/ vector vec;vector:iterator iter = vec.begin();vector:iterator iter_end = vec.end();iterator是vector类中定义的typedef。以下语法：vector:iterator引用了vector类中内嵌的iterator typedef, 并且该vector类包含string类型的元素。为了把每个string元素打印到标准输出上，我们可以这样写：for( ; iter != iter_end; +iter )cout *iter n;当然，这里*iter的运算结果就是实际的string对象。除了iterator类型，每个容器还定义了一个const iterator类型，后者对于遍历const容器是必需的。Const iterator允许以只读方式访问容器的底层元素。例如：#include void even_odd( const vector *pvec,vector *pvec_even,vector *pvec_odd )/ 必须声明一个const_iterator, 才能够遍历pvecvector:const_iterator c_iter = pvec-begin();vector:const_iterator c_iter_end = pvec-end();for ( ; c_iter != c_iter_end; +c_iter )if ( *c_iter % 2 )pvec_odd-push_back( *c_iter );else pvec_even-push_back( *c_iter );最后，如果我们希望查看这些元素的某个子集，该怎么办呢？如每隔一个元素或每隔三个元素，或者从中间开始逐个访问元素。我们可以用标量算术运算使iterator从当前位置偏移到某个位置上。例如：vector:iterator iter = vec.begin()+vec.size()/2;将iter指向vec的中间元素，而：iter += 2;将iter向前移动两个元素。Iterator算术运算只适用于vector或deque，而不适用于list，因为list的元素在内存中不是连续存储的。例如：ilist.begin() + 2;是不正确的，因为在list中向前移动两个元素需要沿着内部next指针走两次。对于vector或deque，前进两个元素需要把当前的地址值加上两个元素的长度。容器对象也可以用“由一对iterator标记的起始元素和末元素后一位置之间的拷贝”来初始化。例如，假设我们有：#include #include #include int main()vector svec;string intext;while ( cin intext )svec.push_back( intext );/ process svec .我们可以定义一个新的vector来拷贝svec的全部或部分元素。int main()vector svec;/ ./ 用svec 的全部元素初始化svec2vector svec2( svec.begin(), svec.end() );/ 用svec 的前半部分初始化svec3vector:iterator it =svec.begin() + svec.size()/2;vector svec3( svec.begin(), it );/ 处理 vectors .用特定的istream_iterator类型，我们可以更直接地向svec插入文本元素：#include #include #include int main()/ 将输入流iterator 绑定到标准输入上istream_iterator infile( cin );/ 标记流结束位置的输入流iteratoristream_iterator eos;/ 利用通过cin 输入的值初始化svecvector svec( infile, eos );/ 处理 svec除了一对iterator之外，两个指向内置数组的指针也可以被用作元素范围标记器（range marker）。例如，假设我们有下列string对象的数组：#include string words4 = stately, plump, buck, mulligan;我们可以通过传递数组words的首元素指针和末元素后一位置的指针来初始化string vectorvector vwords( words, words+4 );第二个指针被用作终止条件，它指向的对象（通常指向容器或者数组中最后一个元素后面的位置上）不包含在要被拷贝或遍历的元素之中。类似地，我们可以按如下方式初始化一个内含int型元素的list:int ia6 = 0, 1, 2, 3, 4, 5 ;list ilist( ia, ia+6 );顺序容器操作Push_back()方法给出了“在顺序容器尾部插入单个元素”的简短表示。但是，如果我们希望在容器的其他位置插入元素，该怎么办呢？或者，如果我们希望在容器的尾部或某个其他位置插入一个元素序列，该怎么办呢？在这些情况下，我们将使用一组更通用的插入方法。例如，为了在容器的头部插入元素，我们将这样做：vector svec;list slist;string spouse( Beth );slist.insert( slist.begin(), spouse );svec.insert( svec.begin(), spouse );这里在，insert()的第一个参数是一个位置（指向容器中某个位置的iterator）,第二个参数是将要被插入的值，这个值被插入到由iterator指向的位置的前面。更为随机的插入操作可以如下实现。string son( Danny );list:iterator iter;iter = find( slist.begin(), slist.end(), son );slist.insert( iter, spouse );这里在，find()返回被查找元素在容器中的位置，或者返回容器的end() iterator, 表明这次查询失败。Push_back()是下列调用的简短表示：/ 等价于: slist.push_back( value );slist.insert( slist.end(), value );insert()方法的第二种形式支持“在某个位置插入指定数量的元素”。例如，如果希望在vector的开始处插入10个Anna，我们可以这样做：vector svec;.string anna( Anna );svec.insert( svec.begin(), 10, anna );insert()方法的最后一种形式支持“向容器插入一段范围内的元素”。例如，给出下列string数组：string sarray4 = quasi, simba, frollo, scar ;我们可以向字符串vector中插入数组中的全部或部分元素。svec.insert( svec.begin(), sarray, sarray+4 );svec.insert( svec.begin() + svec.size()/2,sarray+2, sarray+4);另外，我们还可以通过一对iterator来标记出待插入值的范围，可以是另一个string元素的vector:/ 插入svec 中含有的元素/ 从svec_two 的中间开始svec_two.insert( svec_two.begin() + svec_two.size()/2,svec.begin(), svec.end() );或者，更一般的情况下，也可以是任意一种string对象的容器。list slist;/ ./ 把svec 中含有的元素插入到/ slist 中stringVal 的前面list:iterator iter =find( slist.begin(), slist.end(), stringVal );slist.insert( iter, svec.begin(), svec.end() );删除操作删除容器内元素的一般形式是一对erase()方法：一个删除单个元素，另一个删除由一对iterator标记的一段范围内的元素。删除容器末元素的简短方法由pop_back()方法支持例如，为了删除容器中一个指定的元素，我们可以简单地调用erase()，用一个iterator表示它的位置。在下列代码段中，我们用find()泛型算法获得待删除元素的iterator,如果list中存在这样的元素，则把它的位置传递给erase():string searchValue( Quasimodo );list:iterator iter =find( slist.begin(), slist.end(), searchValue );if ( iter != slist.end() )slist.erase( iter );要删除容器中的所有元素，或者由iterator对标记的子集，我们可以这样做。/ 删除容器中的所有元素slist.erase( slist.begin(), slist.end() );/ 删除由iterator 标记的一段范围内的元素list:iterator first, last;first = find( slist.begin(), slist.end(), val1 );last = find( slist.begin(), slist.end(), val2 );/ . 检查first 和last 的有效性slist.erase( first, last );最后，如同在容器尾部插入一个元素的push_back()方法相仿，pop_back()方法删除容器的末元素-它不返回元素，只是简单地删除它。例如：vector:iterator iter = buffer.begin();for ( ; iter != buffer.end(); iter+ )slist.push_back( *iter );if ( ! do_something( slist )slist.pop_back();赋值和对换当我们把一个容器类型赋值给另一个时，会发生什么事情？赋值操作符使用针对容器元素类型的赋值操作符，把右边容器对象中的元素依次拷贝到左边的容器对象中。如果两个容器的长度不相等，又会怎么样呢？例如：/ slist1 含有10 个元素/ slist2 含有24 个元素/ 赋值之后都含有24 个元素slist1 = slist2;赋值的目标，在本例中为slist1, 它现在拥有与被拷贝容器相同的元素数目。Slist1中的前10个元素被删除。Swap()可以被看作是赋值操作符的互补操作。当我们写：slist1.swap( slist2 );时，slist1现在含有24个string元素，是用string赋值操作符拷贝的，就如同我们写：slist1 = slist2;一样。两者的区别在于，slist2现在含有slist1中原来含有的10个元素的拷贝。如果两个容器的长度不同，则容器长度就被重新设置，且等于被拷贝容器的长度。泛型算法从概念上度，我们的思想是把所有容器类型的公共操作抽取出来，形成一个通用算法集合，它能够被应用到全部容器类型以及内置数组类型上。这组通用算法被称作泛型算法。泛型算法通过一个iterator对，被绑定到一个特殊的容器上。例如，下面的代码显示了我们怎样在一个list,vector，以及不同类型的数组上调用find()泛型算法：#include #include int ia 6 = 0, 1, 2, 3, 4, 5 ;vector svec;list dlist;/ the associated header file#include vector:iterator viter;list:iterator liter;int *pia;/ 如果找到, find()返回指向该元素的iterator/ 对于数组, 返回指针pia = find( &ia0, &ia6, some_int_value );liter = find( dlist.begin(), dlist.end(), some_double_value );viter = find( svec.begin(), svec.end(), some_string_value );因为list容器类型不支持随机访问其元素，所以它提供了额外的操作，如merge()和sort()。存储文本行我们的第一个任务是读入用户需要查询的文本文件。需要获得下列信息：每个单词，当然，还有每个单词的位置，-即，它在哪一行，以及在该行的位置。而且，为了显示出与一个查询相匹配的文本行，我们必须按行号保留文本。怎样获得文本的每一行呢？标准库支持getline()函数，声明如下：istream&getline( istream &is, string str, char delimiter );getline()读取istream对象，向string对象插入字符，包括空格，直到遇到分割符、文件结束，或者被读入的字符序列等于string对象的max_size()值，在该点处读入操作失败。在每次调用getline()之后，我们都会将str插入到代表文本的字符串vector中。下面是一般化的实现。我们已经将它提取到一个函数中，命名为retrieve_text()。为了增加被收集到的信息，我们定义了一对值来存储最长行的行数和长度。/ 返回值是指向string vector 的指针vector*retrieve_text()string file_name;cout file_name;/ 打开文本文件以便输入 .ifstream infile( file_name.c_str(), ios:in );if ( ! infile ) cerr oops! unable to open file file_name - bailing out!n;exit( -1 );else cout n;vector *lines_of_text =new vector;string textline;typedef pair stats;stats maxline;int linenum = 0;while ( getline( infile, textline, n ) cout line read: textline n;if ( maxline.first push_back( textline );linenum+;return lines_of_text;程序的输出如下：please enter file name: alice_emmali