C++ 中 vector 的扩容机制是什么？

推荐答案

在C++中，std::vector的扩容机制是通过动态分配内存来实现的。当vector的当前容量不足以容纳新元素时，它会自动分配一块更大的内存空间，通常是将当前容量翻倍（具体实现可能有所不同），然后将现有元素从旧内存空间复制到新内存空间，最后释放旧内存空间。

本题详细解读

1. 扩容触发条件

std::vector的扩容通常发生在以下情况下：

• 当调用push_back()、emplace_back()等成员函数向vector中添加新元素时，如果当前容量不足以容纳新元素，vector会自动扩容。
• 当调用reserve()函数显式请求更大的容量时，如果请求的容量大于当前容量，vector也会进行扩容。

2. 扩容策略

std::vector的扩容策略通常是按指数增长的方式进行。具体来说，当vector需要扩容时，它会分配一块比当前容量更大的内存空间。常见的实现策略是将当前容量翻倍，例如从容量为4扩容到8，再从8扩容到16，依此类推。

这种指数增长的策略可以保证在大多数情况下，vector的扩容操作是高效的，因为扩容操作的次数会随着元素数量的增加而减少。

3. 扩容过程

当vector需要扩容时，通常会经历以下步骤：

1. 分配一块更大的内存空间。
2. 将现有元素从旧内存空间复制到新内存空间。
3. 释放旧内存空间。
4. 更新vector的内部指针和容量信息。

4. 扩容的时间复杂度

由于vector的扩容涉及到内存分配和元素复制，因此扩容操作的时间复杂度是O(n)，其中n是vector中元素的数量。然而，由于扩容操作的频率随着元素数量的增加而减少，因此vector的均摊时间复杂度仍然是O(1)。

5. 避免频繁扩容

为了避免频繁扩容带来的性能开销，可以使用reserve()函数预先分配足够的内存空间。例如：

std::vector<int> vec;
vec.reserve(100);  // 预先分配100个元素的内存空间

这样可以减少扩容操作的次数，从而提高性能。

6. 注意事项

• vector的扩容操作可能会导致迭代器失效，因此在扩容后，原有的迭代器、指针和引用可能会变得无效。
• 如果需要频繁插入大量元素，建议使用reserve()函数预先分配足够的内存空间，以避免频繁扩容带来的性能开销。