C++ vector扩容机制 C++ push_back导致内存重新分配的策略【性能】

vector::push_back触发扩容的条件是size() == capacity()，此时按实现决定倍数（如1.5倍）重新分配内存，以保证均摊O(1)时间复杂度；建议用reserve预分配避免多次realloc。

vector::push_back 触发扩容的判断条件

当 push_back 要插入新元素，但当前容量 capacity() 已满（即 size() == capacity()），就会触发扩容。这不是每次调用都发生，只在“容器装不下”时才启动重新分配内存流程。

关键点在于：C++ 标准只要求扩容后新容量至少大于当前大小（new_capacity > size()），**不规定具体倍数**——实际行为由 STL 实现决定：

• libstdc++（GCC）和 libc++（Clang）通常采用 1.5 倍扩容（如 1→2→3→4→6→9→13…）
• MSVC 的 std::vector 早期版本用 2 倍，新版也趋于 1.5 倍以平衡内存碎片与拷贝开销
• 扩容后旧元素需逐个移动（C++11 起优先用移动构造，否则用拷贝构造）

为什么不是固定增长（比如每次 +1 或 +10）

固定增量会导致 push_back 均摊时间复杂度退化为 O(n)。例如每次只增 1，插入 n 个元素就要做 n 次分配，总拷贝次数达 O(n²)。

而倍增策略（如 1.5×）能保证均摊 O(1)：虽然单次扩容代价高，但两次扩容之间插入的元素越来越多，摊到每个元素上的平均代价收敛到常数。

立即学习“C++免费学习笔记（深入）”；

Kite

代码检测和自动完成工具

下载

• 设初始容量为 1，按 1.5 倍增长：1 → 2 → 3 → 4 → 6 → 9 → 13 → …
• 第 k 次扩容前已插入约 1.5ᵏ 个元素，本次拷贝最多 1.5ᵏ 个对象
• 总拷贝量 ≈ Σ 1.5ᵏ = O(1.5ᵏ)，而总插入数也是 O(1.5ᵏ)，比值有界

如何避免意外的多次 realloc —— reserve 的使用时机

如果你事先知道大概要存多少元素（比如读取文件行数、网络包数量），直接调用 reserve(n) 预分配空间，可彻底规避中间多次扩容。

• reserve(n) 只改变 capacity()，不改变 size()，也不调用元素构造函数
• 若 n ≤ 当前 capacity()，该调用无效果（不会缩容）
• 若后续插入总数 ≤ n，则全程零 realloc；哪怕超了，也只从第 n+1 个开始重新算扩容节奏
• 错误做法：resize(n) —— 它会构造 n 个默认对象，浪费时间和内存

示例：

std::vector lines;
lines.reserve(1000); // 预估 1000 行，避免反复分配 string 缓冲区
for (std::string line; std::getline(in, line); ) {
    lines.push_back(std::move(line)); // 移动语义进一步减少拷贝
}

移动语义对扩容性能的实际影响

扩容时，旧元素必须转移到新内存。如果元素类型支持移动构造（如 std::string、std::unique_ptr），且编译器未禁用优化，STL 会优先调用移动而非拷贝。

• 移动通常只是指针/整数赋值，O(1)；拷贝 std::string 可能涉及堆内存分配和 memcpy
• 自定义类务必显式提供 noexcept 的移动构造函数，否则 STL 可能因异常安全顾虑退回到拷贝
• POD 类型（如 int、double）无移动/拷贝区别，但 memcpy 仍随容量线性增长

一个容易被忽略的细节：即使你写了移动构造函数，若它没加 noexcept，libstdc++ 在扩容时可能拒绝使用它，导致降级为深拷贝——检查方式是看 std::is_nothrow_move_constructible_v 是否为 true。