首页 > 编程笔记 > C++笔记 阅读数:149

如何避免vector容器进行不必要的扩容?

前面提到,我们可以将 vector 容器看做是一个动态数组。换句话说,在不超出 vector 最大容量限制(max_size() 成员方法的返回值)的前提下,该类型容器可以自行扩充容量来满足用户存储更多元素的需求。

值得一提的是,vector 容器扩容的整个过程,和 realloc() 函数的实现方法类似,大致分为以下 4 个步骤:
  1. 分配一块大小是当前 vector 容量几倍的新存储空间。注意,多数 STL 版本中的 vector 容器,其容器都会以 2 的倍数增长,也就是说,每次 vector 容器扩容,它们的容量都会提高到之前的 2 倍;
  2. 将 vector 容器存储的所有元素,依照原有次序从旧的存储空间复制到新的存储空间中;
  3. 析构掉旧存储空间中存储的所有元素;
  4. 释放旧的存储空间。

通过以上分析不难看出,vector 容器的扩容过程是非常耗时的,并且当容器进行扩容后,之前和该容器相关的所有指针、迭代器以及引用都会失效。因此在使用 vector 容器过程中,我们应尽量避免执行不必要的扩容操作。

要实现这个目标,可以借助 vector 模板类中提供的 reserve() 成员方法。不过在讲解如何用 reserve() 方法避免 vector 容器进行不必要的扩容操作之前,vector 模板类中还提供有几个和 reserve() 功能类似的成员方法,很容易混淆,这里有必要为读者梳理一下,如表 1 所示。

表 1 vector模板类中功能类似的成员方法
成员方法 功能
size() 告诉我们当前 vector 容器中已经存有多少个元素,但仅通过此方法,无法得知 vector 容器有多少存储空间。
capacity() 告诉我们当前 vector 容器总共可以容纳多少个元素。如果想知道当前 vector 容器有多少未被使用的存储空间,可以通过 capacity()-size() 得知。注意,如果 size() 和 capacity() 返回的值相同,则表明当前 vector 容器中没有可用存储空间了,这意味着,下一次向 vector 容器中添加新元素,将导致 vector 容器扩容。
resize(n) 强制 vector 容器必须存储 n 个元素,注意,如果 n 比 size() 的返回值小,则容器尾部多出的元素将会被析构(删除);如果 n 比 size() 大,则 vector 会借助默认构造函数创建出更多的默认值元素,并将它们存储到容器末尾;如果 n 比 capacity() 的返回值还要大,则 vector 会先扩增,在添加一些默认值元素。
reserve(n) 强制 vector 容器的容量至少为 n。注意,如果 n 比当前 vector 容器的容量小,则该方法什么也不会做;反之如果 n 比当前 vector 容器的容量大,则 vector 容器就会扩容。

通过对以上几个成员方法功能的分析,我们可以总结出一点,即只要有新元素要添加到 vector 容器中而恰好此时 vector 容器的容量不足时,该容器就会自动扩容。

因此,避免 vector 容器执行不必要的扩容操作的关键在于,在使用 vector 容器初期,就要将其容量设为足够大的值。换句话说,在 vector 容器刚刚构造出来的那一刻,就应该借助 reserve() 成员方法为其扩充足够大的容量。

举个例子,假设我们想创建一个包含 1~1000 的 vector<int>,通常会这样实现:
vector<int>myvector;
for (int i = 1; i <= 1000; i++) {
    myvector.push_back(i);
}
值得一提的是,上面代码的整个循环过程中,vector 容器会进行 2~10 次自动扩容(多数的 STL 标准库版本中,vector 容器通常会扩容至当前容量的 2 倍,而这里 1000≈2 10),程序的执行效率可想而知。

在上面程序的基础上,下面代码演示了如何使用 reserve() 成员方法尽量避免 vector 容器执行不必要的扩容操作:
vector<int>myvector;
myvector.reserve(1000);
cout << myvector.capacity();
for (int i = 1; i <= 1000; i++) {
    myvector.push_back(i);
}
相比前面的代码实现,整段程序在运行过程中,vector 容器的容量仅扩充了 1 次,执行效率大大提高。

当然在实际场景中,我们可能并不知道 vector 容器到底要存储多少个元素。这种情况下,可以先预留出足够大的空间,当所有元素都存储到 vector 容器中之后,再去除多余的容量。

关于怎样去除 vector 容器多余的容量,可以借助该容器模板类提供的 shrink_to_fit() 成员方法,另外后续还会讲解如何使用 swap() 成员方法去除 vector 容器多余的容量,两种方法都可以。

爱面试的程序媛,一个分享面试经验的公众号。跟着站长一起学习,每天都有进步。

通俗易懂,深入浅出,定时分享程序员面试的那点事。

面试如何造火箭?工作如何拧螺丝?都在这个公号哦。

扫描二维码关注公众号,免费领取价值 1000 元的求职面试资料(限时免费)!

当你决定关注「爱面试的程序媛」,你已然超越了90%的程序员!

爱面试的程序媛二维码
微信扫描二维码关注