C++程序设计:原理与实践(进阶篇)15.8 调整vector类达到STL版本的功能-阿里云开发者社区

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

C++程序设计:原理与实践(进阶篇)15.8 调整vector类达到STL版本的功能

简介:

15.8 调整vector类达到STL版本的功能


在15.5节中为vector增加了begin()、end()和类型别名后,现在只差insert()和erase()就接近我们设计一个std::vector的近似版本的目标了:

 

我们还是使用指向元素类型的指针T*作为迭代器的类型,这是最简单的方法。我们将边界检查迭代器的实现留作练习(习题18)。

人们通常不会为元素连续存储的数据类型(如vector)提供列表操作,如insert()或erase()。但insert()和erase()这样的列表操作对短vector或少量元素极为有用也极为高效。我们已经反复看到了push_back()的作用,它是另一个常见的列表操作。

基本上,我们可以通过拷贝所有位于所删除元素之后的元素来实现vector<T,A>::erase()。利用14.3.6节中定义的vector再加上上述内容,我们得到:

 

借助下面的图示,你可以更容易理解上面代码:

 

erase()的代码非常简单,但在纸上试着画几个例子可能是个好主意。有没有正确地处理空vector?为什么要判断p==end()?如果删除vector的最后一个元素会怎么样?如果使用下标语法的话代码的可读性会不会更好?

相对而言,vector<T, A>::insert()就有一点复杂了:

 

 

请注意:

由于迭代器不能指向序列之外,所以我们使用指针来完成,比如elem+sz。这就是为什么分配器用指针而不是迭代器来定义。

当我们使用reserve()时,元素会被移动到一块新的内存中。因此,我们必须要记住插入元素位置的索引,而不是指向它的迭代器。当vector为其元素重新分配内存时,指向vector内部的迭代器会失效——可以理解为它们指向的是旧的内存。

我们使用分配器参数A的方式很直观,但不准确。当你需要实现一个容器时,最好还是仔细读一下相关的标准。

由于这些微妙的细节,我们尽量避免处理底层内存问题。自然地,标准库vector(以及所有其他标准库容器)能正确实现这些重要的语义细节。这也是优先使用标准库而不是“家庭制作”的原因之一。

出于性能原因,你不应在一个含有100?000个元素的vector内部使用insert()或erase();对这种操作,使用list(或map,参见16.6节)更为适合。但是,vector确实提供了insert()和erase()操作,而且如果我们只是移动几个或几十个字的数据的话,其性能是没有问题的——毕竟现代计算机已非常擅长这种拷贝操作(见习题20)。注意不要用list(链表)表示少量元素的列表。

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

分享:

华章出版社

官方博客
官网链接