17370845950

vector 是 C++ STL 中最常用的动态数组容器，它能够在运行时自动扩容，支持快速的随机访问和尾部插入删除操作。理解其底层原理和扩容机制，对写出高效、稳定的代码非常有帮助。

vector 的底层数据结构

vector 底层使用一段连续的内存空间来存储元素，本质上是一个动态数组。它通过三个指针维护这段内存：

• _start：指向当前已分配内存中第一个元素的位置
• _finish：指向已使用内存中最后一个元素的下一个位置（即当前有效元素的末尾）
• _end_of_storage：指向整个分配内存块的末尾（容量上限）

这三者满足关系：
_start ≤ _finish ≤ _end_of_storage
size() = _finish - _start
capacity() = _end_of_storage - _start

vector 扩容机制详解

当 vector 中没有足够空间容纳新元素时（比如执行 push_back），就会触发扩容。整个过程如下：

• 检查当前 size() 是否等于 capacity()
• 若相等，则需要扩容：申请一块更大的连续内存
• 将原有数据从旧内存复制或移动到新内存
• 释放旧内存
• 更新内部指针指向新内存区域

关键点在于：新容量通常是旧容量的某个倍数。主流实现（如 GCC 的 libstdc++ 和 MSVC）通常采用1.5 倍或 2 倍增长策略：

• libstdc++（GCC）一般使用 2 倍扩容
• MSVC 和某些版本也使用 1.5 倍以平衡性能与内存浪费

例如，当前 capacity=4，插入第 5 个元素时，会申请 capacity=8 的新内存，复制原数据后完成扩容。

扩容带来的影响与注意事项

虽然扩容对用户透明，但会带来一些潜在问题：

• 性能开销：复制所有元素的时间复杂度是 O(n)，频繁扩容会影响效率
• 迭代器失效：一旦发生扩容，原有指针、引用、迭代器全部失效
• 内存碎片：连续内存要求可能在堆中难以分配大块空间

优化建议：

• 如果能预估元素数量，提前调用 reserve(n) 预留空间，避免多次扩容
• 避免在循环中不断 push_back 而不 reserve
• 注意不要保存 vector 的 begin() 或 &vec[0] 指针，在可能扩容的地方重新获取

小结

vector 通过连续内存 + 动态扩容实现灵活高效的数组管理。掌握其底层三指针结构和扩容策略，有助于写出更安全、高效的 C++ 代码。合理使用 reserve 可显著提升性能，避免不必要的内存拷贝。

基本上就这些。