C++程序设计:原理与实践(进阶篇)15.7 vector、list和string-阿里云开发者社区

开发者社区> 华章出版社> 正文

C++程序设计:原理与实践(进阶篇)15.7 vector、list和string

简介:

15.7 vector、list和string


为什么我们对行用list而对字符用vector呢?更准确地说,我们为什么要用list保存行的序列而用vector保存字符序列呢?再有,为什么不用string来存储一行呢?

我们可以把这些问题再一般化一些。到现在为止,我们知道了四种存储字符序列的方法:

char[](字符数组);

vector<char>;

string;

list<char>。

那么对于一个给定问题应该采取哪种存储方式呢?当问题非常简单时,选择哪种方式都无所谓,因为它们都有非常相似的接口。例如,给定一个iterator,我们可以使用++遍历所有字符,用*访问字符。在与Document相关的代码示例中,我们的确可以将vector<char>换成list<char>或string,而不会引起任何逻辑上的问题。这是非常好的特性,因为这令我们只需从性能角度选择存储方式。但是,在考虑性能之前,我们先来看看这些存储方式的逻辑特性:有什么是它能做而其他方式所不能的?

Elem[]:不知道它自己的大小。没有begin()、end()或任何其他有用的容器成员函数。不能系统地实现边界检查。可以作为参数传递给用C或C++编写的函数。其中的元素在内存中连续存储。数组的大小在编译时就确定了。比较(==和!=)和输出(<<)操作使用的是指向数组第一个元素的指针,而不是元素。

vector[Elem]:基本上可以做所有事,包括insert()和erase()。支持下标操作。在其上的列表操作,例如insert()和erase(),通常需要移动字符(当元素很大或元素数目很多时效率会比较低)。可实现边界检查。元素在内存中连续存储。vector可以扩展(例如使用push_back())。向量的元素(连续)存储在数组中。比较运算符(==、!=、<、<=、>、>=)对元素进行比较。

string:提供了所有常见的有用操作,还提供了特殊的文本处理操作,例如字符串的连接(+和+=)。其元素保证在内存中连续存储。string可以扩展。比较运算符(==、!=、<、<=、>、>=)对元素进行比较。

list[Elem]:提供了除下标外所有常见的有用操作。我们在进行insert()或erase()操作时不必移动其他元素。每个元素需要两个额外的字(用来存储链接指针)。list可以扩展。比较运算符(==、!=、<、<=、>、>=)对元素进行比较。

正如我们之前提到的(见12.2节和13.6节),当我们需要在底层和内存打交道或需要和C程序交互时数组是非常有用且必需的(见27.1.2节和27.5节)。在其他情况下,vector由于更方便、灵活且安全,应是首选。

试一试

上述的区别在实际的代码中意味着什么?分别定义一个保存值"Hello"的char数组、vector<char>、list<char>和string,并把它们作为参数传递给一个函数。该函数首先输出传来的字符串中的字符数目,并将其与函数内定义的"Hello"相比较(以判断你是否真的传递了"Hello"),然后再与"Howdy"比较,看看它们在字典中谁更靠前。把参数复制到另一个相同类型的变量中。

试一试

重复上面的“试一试”,这次测试int数组、vector<int>和list<int>,都保存数值{1,2,3,4,5}。

15.7.1 insert和erase

标准库vector是我们使用容器时的首选。它几乎具有所有所需特性,所以我们只在没有办法时才会使用其他的替代品。vector主要的问题在于每当我们执行列表操作(insert()和erase())时,都需要对元素进行移动。当vector中的元素很多或元素很大时,移动元素会产生很高的代价。但也不必太担心这一点。我们可以放心地用push_back()读取50万个浮点数存入一个vector中,实验证明相对于预分配所有内存的方法,push_back()并无明显的性能劣势。在为了性能而做出重大改变前一定要进行性能测试,即使是专家也很难猜测性能。

正如在15.6节中所提到的,移动元素的特性还意味着一个逻辑限制:当你对一个vector执行列表操作(如insert()、erase()和push_back())时一定不要保留指向其元素的迭代器或指针:若元素移动,你的迭代器或指针将会指向错误的元素,甚至根本不指向任何元素。这也正是list相对于vector(以及map,参见16.6节)的根本优势。如果你在程序中需要使用很多大对象,而且会在很多地方(用迭代器或指针)指向它们,则应考虑使用list。

我们来比较一下list和vector的insert()和erase()操作。首先看一个仅用来展示关键点的例子:

 

现在q是无效的。随着向量的大小增长,可能会为其元素分配新的内存。如果v有空闲空间,则它会原地增长,q很可能指向的是值为3的元素而不是值为4的元素,但千万不要认为一定会是这样。

 

 

也就是说,如果在insert()操作后执行一次erase()操作删除刚刚插入的元素,那么我们就回到了起始状态,只是q变成无效了。但是,在这两次操作之间,我们移动了插入点之后的所有元素,随着v增长所有元素可能都被重新分配空间了。

作为对比,我们使用list来完成相同的操作:

 

注意,q仍然指向值为4的元素。

 

 我们又一次发现回到了起始状态。但是,与vector的不同之处在于,我们没有移动任何元素,q始终是有效的。

list<char>与其他三种容器相比需要至少3倍的存储空间——在PC上,一个list<char>需要12个字节来保存每个元素,而vector<char>只需要1个字节。当字符数很多时,这种差距可能很重要。

那vector哪方面优于string呢?从它们的特性中可以发现,string似乎能完成比vector更多的功能。但这也正是部分问题的所在:由于string必须完成更多功能,对它进行优化也就更困难了。实际上,vector设计思想之一就是对push_back()这样的“内存操作”进行优化,而string并没有。取而代之,string对拷贝操作、短字符串处理以及与C风格字符串的交互进行了优化。在文本编辑器的例子中,我们选择vector是因为需要使用insert()和delete(),另一方面也是出于性能的考虑。vector和string逻辑的主要差异在于vector几乎可以用于任何元素类型,而只有在处理字符时我们才需要考虑string。总之,只有当需要进行字符串操作(例如字符串连接或读取空白符间隔的单词)时才考虑使用string,其他情况下,就用vector好了。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:

华章出版社

官方博客
官网链接