当vector空间不足时，如何扩容？

八股文_C++STL面试题 0 1

参考回答

当 std::vector 空间不足时，它会自动扩容。具体过程如下：

分配更大的连续内存块：通常，新容量是当前容量的两倍（倍增策略）。
复制现有元素：将旧内存中的元素逐一复制到新分配的内存中。
释放旧内存：释放之前的内存块。

这种机制确保了 vector 的元素始终存储在连续内存中，但扩容过程中会有一定的性能开销。

详细讲解与拓展

1. 扩容触发条件

扩容的触发条件是当前 vector 容量不足以存储新增的元素。例如：

vector<int> v = {1, 2, 3};
v.push_back(4);  // 如果容量不足，这里会触发扩容

使用 vector 的 capacity() 成员函数可以查看当前容量。比如：

vector<int> v;
cout << v.capacity() << endl;  // 初始容量为 0
v.push_back(1);
cout << v.capacity() << endl;  // 容量可能变为 1
v.push_back(2);
cout << v.capacity() << endl;  // 容量可能变为 2 或更大

2. 扩容机制

扩容的核心步骤包括：
1. 分配新内存：
– 分配一个更大的连续内存块，新容量通常为当前容量的 2 倍。
– 倍增策略减少了频繁扩容的开销，使得扩容的均摊时间复杂度为 (O(1))。

数据迁移：
- 将旧内存块中的所有元素逐一拷贝到新内存中。
- 如果 vector 中的元素有复杂的析构函数或拷贝构造函数，这一步可能会导致较高的性能开销。
释放旧内存：
- 释放之前的内存块，避免内存泄漏。

3. 示例代码

下面的代码演示了 vector 的扩容机制：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;
    for (int i = 0; i < 10; ++i) {
        v.push_back(i);
        cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << endl;
    }
    return 0;
}

输出示例（具体值可能因实现不同而异）：

Size: 1, Capacity: 1
Size: 2, Capacity: 2
Size: 3, Capacity: 4
Size: 4, Capacity: 4
Size: 5, Capacity: 8

4. 手动优化扩容

由于扩容可能带来较大的性能开销（尤其在大规模数据操作时），我们可以通过以下方法优化：
1. 提前预分配容量：
使用 reserve 方法提前分配足够的空间，避免频繁扩容。例如：

“`cpp
vector<int> v;
v.reserve(100); // 分配 100 个元素的空间
for (int i = 0; i < 100; ++i) {
v.push_back(i);
}
“`
这避免了多次扩容操作，提高了效率。

使用 resize：
如果已知最终大小，可以直接使用 resize：
```
vector<int> v;
v.resize(100);  // 分配并初始化 100 个元素
```

5. 倍增策略的均摊效率

虽然每次扩容会导致 (O(n)) 的拷贝开销，但由于倍增策略，扩容的次数是对数级别的。例如，当从 1 扩展到 100 个元素时，扩容的次数约为 (\log_2(100) \approx 7)。因此，扩容的 均摊时间复杂度 为 (O(1))。

6. 注意迭代器失效

扩容后，vector 的迭代器、指针或引用都会失效，因为数据已经迁移到新的内存地址。例如：

vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4);  // 容量不足导致扩容
cout << *it << endl;  // 未定义行为，迭代器已失效

解决方法：
– 在扩容可能发生时，避免使用旧的迭代器。
– 如果需要频繁扩容，可以通过 reserve 预分配空间。

总结

std::vector 在空间不足时通过倍增容量的策略进行扩容，确保了元素的连续存储。虽然扩容带来了数据迁移的性能开销，但通过提前 reserve 空间，可以显著提升效率。同时，扩容后要注意迭代器失效问题，合理设计程序以避免潜在问题。