vector如何保证元素的连续存储？
参考回答
std::vector 通过在底层使用动态分配的 连续内存块 来保证其元素的连续存储。每当需要扩展容量时，vector 会分配一块更大的连续内存，并将旧内存中的元素逐一复制到新的内存块中。因此，无论在任何时候，vector 的所有元素都存储在一块连续的内存空间中。
详细讲解与拓展
1. 底层机制：动态数组
std::vector 使用堆内存存储元素。它的核心是维护一个指针，指向分配的动态内存块。初始时，vector 会分配一小块连续内存来存储元素。当现有容量不足以容纳新增元素时，它会：
1. 分配一个更大的连续内存块（通常是当前容量的 2 倍，称为 倍增策略）。
2. 将现有的元素从旧内存块逐一复制到新内存块。
3. 释放旧的内存块。
这一策略确保了所有元素始终存储在同一块连续的内存中。
2. 示例：动态扩展的实现
以下代码展示了 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
size是当前元素个数。capacity是当前分配的内存块大小。当容量不足时，vector重新分配一块更大的内存，并将所有元素复制到新的内存中。
3. 为什么连续存储是必要的？
连续存储使得 vector 的设计具备以下特性：
1. 随机访问：由于存储是连续的，vector[i] 的访问是常数时间 (O(1))，本质上是通过指针偏移实现的：*(data + i)。
2. 兼容性：vector 可以与 C 风格的数组无缝对接。例如：
“`cpp
vector<int> v = {1, 2, 3, 4};
int* arr = v.data(); // 获取底层数组指针
cout << arr[2] << endl; // 输出 3
“`
4. 内存连续的代价：扩展时的性能开销
由于 vector 需要保证内存连续，扩展容量时必须重新分配内存并复制数据，这会带来性能开销：
– 扩展容量时的时间复杂度为 (O(n))（线性），因为需要逐一复制现有元素。
– 如果容量很大，拷贝操作可能对性能造成显著影响。
为减少扩展的频率，可以提前调用 reserve 函数分配足够的容量。例如：
vector<int> v;
v.reserve(100); // 提前分配 100 个元素的空间
5. 扩展：迭代器失效问题
由于扩展时会分配新的内存块，旧内存中的指针和迭代器都会失效。例如：
vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4); // 容量不足，分配新内存
cout << *it << endl; // 未定义行为，迭代器失效
解决方法：
– 避免在扩展前使用迭代器。
– 如果可能的扩展不可避免，可以通过 reserve 提前分配足够的容量。
总结
std::vector 使用动态分配的连续内存块来保证元素的连续存储。虽然这一设计带来了高效的随机访问性能和与数组的兼容性，但它在扩展容量时需要分配新内存并复制数据，可能导致一定的性能开销。提前了解其内存管理机制，有助于更高效地使用 vector。