【C++】顺序容器(三):vector对象是如何增长的

发布于:2024-11-28 ⋅ 阅读:(27) ⋅ 点赞:(0)

9.4 vector对象是如何增长的

为了支持快速随机访问,vector 将元素连续存储——每一个元素紧挨着前一个元素存储。

假定容器中元素是连续存储的,且容器的大小是可变的,考虑向 vector 或 string 中添加元素会发生什么:如果没有空间容纳新元素,容器不可能简单地将它添加到内存中其它位置——因为元素必须连续存储。容器必须分配新的内存空间来保存已有元素和新元素,将已有元素从旧位置移动到新空间中,然后添加新元素,释放旧存储空间。如果我们每添加一个新元素,vector 就执行一次这样的内存分配和释放操作,性能会慢到不可接受。

为了避免这种代价,标准库实现者采用了可以减少容器空间重新分配次数的策略。当不得不获取新的内存空间时,vector 和 string 的实现通常会分配比新的空间需求更大的内存空间。容器预留这些空间作为备用,用来保存更多的元素。这样就不需要每次添加新元素都重新分配容器的内存空间了。

这种分配策略比每次添加新元素时重新分配容器内存空间的策略要高效得多。其实际性能也足够好——虽然 vector 每次重新分配内存空间时都需要移动所有元素,但是使用该策略之后,其扩张操作比 list 和 deque 还要快。

(所以实际上 vector 存储空间的增长仍然是开辟新的存储空间之后,将原存储复制到新存储,再删掉原存储,只不过每次开辟新的内存空间时,将开辟额外的空间作为冗余)

管理容量的成员函数

vector 和 string 类型提供了一些成员函数,允许我们与它的实现中内存分配部分互动。capacity 操作告诉我们容器在不扩张内存空间的情况下可以容纳多少个元素。reserve 操作允许我们通知容器它应该准备保存多少个元素。

以下列出了一些容器大小管理操作:
shrink_to_fit 只适用于 vector、string和deque。
capacity和reverse只适用于vector和string。

  • c.shrink_to_fit():将 capacity() 减少为与 size() 相同大小;
  • c.capacity():不重新分配内存空间的话,c 可以保存多少元素;
  • c.reserve(n):分配至少能容纳 n 个元素的内存空间;

reserve 并不改变容器中元素的数量,它仅影响 vector 预先分配多大的内存空间。

只有当需要的内存空间超过当前容量时,reserve 调用才会改变 vector 的容量。如果需求大小大于当前容量,reserve 至少分配与需求一样大的内存空间(可能更大)。

需要注意的是,reserve 永远不会减少容器占用的内存空间。

capacity 和 size

capacity 和 size 有着本质的区别。容器的 size 指的是它已经保存的元素的数目;而 capacity 则是在不分配新的内存空间的前提下它最多可以保存多少元素。

通常来说,在分配更多内存空间时,vector 会将当前的存储空间翻倍。