C++ P48 – STD::VECTOR 的优化
C++ P48 – STD::VECTOR 的优化

C++ P48 – STD::VECTOR 的优化

优化Vector之前我们要干些什么?

  1. 知道我们要优化什么(环境);
  2. 知道用什么方式来优化问题。

优化前环境:

一个测试用结构

这个结构,由两个构造器组成, 第一个在被构造后显示“Constructed!”, 而第二个则是接受一个在别处声明过的Vectex结构再被传入Vectex中(Copy), 被Copy后会显示“Copied!".

从运行结果可以看出,在main函数中添加元素调用了3次创建结构和6次复制, 这样的效率是十分不理想的. 这就为我们接下来的优化提供了条件——减少复制次数.

优化

为了减少复制次数, 我们要先了解为什么会出现复制.

push_back

vectexes.push_back(Vectex(1, 2, 3));

push_back的参数是左值引用。首先定义一个Vectex对象的时候,调用一次构造函数, 然后push_back的时候调用一次拷贝构造函数. 两次构造很花时间,因为内存里面需要重新分配空间.

而接下来的两个Copy和三个Copy则是由于每个Vectex对象在内存重新分配空间时需要移动,不难计算,在n次添加Vectex对象时复制操作的时间复杂度是O(n^2).

为了避免在构造时调用拷贝函数(从main中拷贝到Vectex),我们使用emplace_back.相比于push_back,emplace_back可以避免额外类的复制和移动操作.

可以看到,添加每一个对象时都减少了一次复制操作。

避免容量不够导致多次复制

vector会在每次容量满时,寻找新的更大的内存空间,再把其中每个元素拷贝到新的内存空间,最后销毁原来的空间,这样,在每次容量满时,都会对每一个Vectex对象进行一次拷贝操作,在数据大的情况下这种操作大大拖慢了运行时间。

通过reserve空间,我们可以做到在没有元素加入时就预先占用定量的内存空间来做到添加时不用寻找新的内存空间,当然,reserve的大小取决于你的数据的数量。

结果

Constructed!
Constructed!
Constructed!

我们成功消灭了无用的Copy操作。

思考

关于&和&&

在寻找emplace_back的资料时,看到了有趣的东西

&表示被copy, &&表示被move,为什么呢?

发表回复

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据