好的，我们来从 底层实现角度详细分析 C++ STL 中 vector 容器的 扩容机制，包括内存分配、容量管理、复杂度分析和性能注意点。

一、vector 容器概览

vector 是 动态数组，其特点：

• 支持随机访问：O(1) 访问任意元素。
• 支持动态扩展：可以向末尾添加元素。
• 连续内存存储，底层用一块连续的数组存储元素。
• 内部维护三个指针（或迭代器）：
  1. start：指向数组起始位置。
  2. finish：指向已使用的最后一个元素后的位置。
  3. end_of_storage：指向分配内存的末尾位置。

[start, finish)      : 已使用的元素
[finish, end_of_storage) : 可用容量（未使用）

二、扩容触发条件

vector 在以下情况下会扩容：

v.push_back(x);  // 当 finish == end_of_storage 时触发扩容

也就是 当前容量用完，需要重新分配更大的内存来容纳新元素。

三、底层扩容机制（以 GCC 实现为例）

1. 计算新容量
   • STL 通常按 几何倍增策略，一般是当前容量的 1.5~2 倍：
   new_capacity = max(old_capacity * 2, 1)
   • 保证扩容次数为 O(log n)，避免频繁分配。
2. 分配新内存
   • 使用 allocator 分配一块新的连续内存：
   pointer new_start = allocator.allocate(new_capacity);
3. 元素搬移
   • 将旧数组 [start, finish) 的元素 逐个拷贝或移动到新内存。
   • 对于非 POD 类型，会调用 拷贝构造函数或移动构造函数。
   for (size_type i = 0; i < size(); ++i) allocator.construct(new_start + i, std::move_if_noexcept(old_start[i]));
4. 销毁旧数组
   • 调用旧元素析构函数：
   for (size_type i = 0; i < size(); ++i) allocator.destroy(old_start + i);
   • 释放旧内存：
   allocator.deallocate(old_start, old_capacity);
5. 更新指针
   • start → new_start
   • finish → new_start + size
   • end_of_storage → new_start + new_capacity

四、复杂度分析

• 单次 push_back
  • 平均复杂度：O(1) 摊销
  • 最坏复杂度：O(n)（触发扩容，搬移所有元素）
• 原因
  • 虽然扩容时需要搬移所有元素，但几何倍增保证了每个元素平均只被搬移常数次。
• 总结：vector 的增长策略使得 连续 push_back 总体是线性时间，每次插入的平均成本为常数。

五、扩容策略示例

六、扩容的性能影响

1. 内存占用
   • 扩容可能导致 未使用空间浪费（capacity() > size()）。
   • 对于大型 vector 或多次扩容，可能占用额外内存。
2. 对象搬移开销
   • 对于复杂对象，拷贝/移动成本高。
   • 建议尽量 预先 reserve()： std::vector<int> v; v.reserve(1000); // 避免多次扩容
3. 迭代器失效
   • 扩容会重新分配内存，所有指向旧 vector 的迭代器/指针/引用失效。

七、预分配 vs 自动扩容

• reserve(n)
  • 预先分配 n 个容量
  • 避免多次扩容
  • 不改变 size
• resize(n)
  • 改变 size
  • 会默认构造 n 个元素
• push_back
  • 按需扩容
  • 对于小 vector，push_back 足够灵活
• 总结
  • 大量数据插入前建议用 reserve 提前分配。

八、底层伪代码（简化版）

void vector::push_back(const T& value) {
    if (finish == end_of_storage) {
        // 扩容
        size_t new_capacity = std::max(2 * capacity(), size_t(1));
        pointer new_start = allocator.allocate(new_capacity);

        for (size_t i = 0; i < size(); ++i)
            allocator.construct(new_start + i, std::move_if_noexcept(start[i]));

        for (size_t i = 0; i < size(); ++i)
            allocator.destroy(start + i);
        allocator.deallocate(start, capacity());

        start = new_start;
        finish = new_start + size();
        end_of_storage = new_start + new_capacity;
    }
    allocator.construct(finish, value);
    ++finish;
}

九、总结

1. vector 是动态数组，连续内存存储。
2. 内部维护 [start, finish, end_of_storage) 三个指针。
3. 扩容策略：
   • 按 几何倍增；
   • 重新分配内存 + 拷贝/移动元素。
4. push_back 的摊销复杂度为 O(1)。
5. 扩容可能导致迭代器失效、额外内存占用。
6. 对于大规模数据插入，推荐使用 reserve。