面试每日一题 Day 1 —— C++ vector 扩容机制

面试每日一题 Day 1 —— C++ vector 扩容机制

一、题目描述

C++ 中std::vector的扩容机制是什么？请详细说明触发条件、扩容策略、底层过程和复杂度。

二、考点分析

三、详细回答

3.1 触发条件

当vector的当前元素个数size()等于当前容量capacity()时，再执行push_back()等添加元素的操作会触发扩容。

#include<iostream>#include<vector>usingnamespacestd;intmain(){vector<int>v;cout<<"size: "<<v.size()<<", capacity: "<<v.capacity()<<endl;// 输出：size: 0, capacity: 0v.push_back(1);cout<<"size: "<<v.size()<<", capacity: "<<v.capacity()<<endl;// 输出：size: 1, capacity: 1（触发扩容）v.push_back(2);cout<<"size: "<<v.size()<<", capacity: "<<v.capacity()<<endl;// 输出：size: 2, capacity: 2（触发扩容）v.push_back(3);cout<<"size: "<<v.size()<<", capacity: "<<v.capacity()<<endl;// 输出：size: 3, capacity: 4（触发扩容）return0;}

3.2 扩容策略（不同编译器的实现差异）

为什么选择 1.5 或 2？

• 倍数太小：频繁扩容，性能差
• 倍数太大：内存浪费严重
• 1.5-2 倍是经验上空间和时间的最优平衡

3.3 扩容的底层过程

详细步骤：

1. 判断：检测到size == capacity，需要扩容
2. 计算：新容量 = 旧容量 × 扩容因子（至少为 1，因为容量为 0 时需要特殊处理）
3. 分配：在堆上申请一块新的连续内存，大小为新容量 × sizeof(T)
4. 迁移：
   • C++98 标准：逐个拷贝构造元素到新内存
   • C++11 及以后：尽可能使用移动构造（提升效率）
5. 释放：释放旧内存，更新指针指向新内存

3.4 时间复杂度分析

均摊分析（以扩容因子 2 为例）：

• 假设初始capacity = 1
• 第 1 次 push：容量 1 → 2，迁移 1 个元素
• 第 2 次 push：容量 2 → 4，迁移 2 个元素
• 第 4 次 push：容量 4 → 8，迁移 4 个元素
• 第 8 次 push：容量 8 → 16，迁移 8 个元素

扩容总迁移次数 = 1 + 2 + 4 + 8 + … + n/2 = n - 1

n 次 push 总操作数 ≈ n（构造）+ (n-1)（迁移）= O(n)

均摊到每次 push_back：O(1)

3.5 完整代码验证

#include<iostream>#include<vector>usingnamespacestd;intmain(){vector<int>v;cout<<"初始: size="<<v.size()<<", capacity="<<v.capacity()<<endl;for(inti=0;i<20;i++){intoldCap=v.capacity();v.push_back(i);intnewCap=v.capacity();if(newCap>oldCap){cout<<"push "<<i<<" 后触发扩容: "<<"capacity 从 "<<oldCap<<" 变为 "<<newCap<<endl;}}return0;}

输出（GCC 环境）：

初始: size=0, capacity=0 push 0 后触发扩容: capacity 从 0 变为 1 push 1 后触发扩容: capacity 从 1 变为 2 push 2 后触发扩容: capacity 从 2 变为 4 push 4 后触发扩容: capacity 从 4 变为 8 push 8 后触发扩容: capacity 从 8 变为 16 push 16 后触发扩容: capacity 从 16 变为 32

四、效率优化技巧

4.1 使用reserve()预分配空间

vector<int>v;v.reserve(1000);// 一次性分配 1000 个元素的空间for(inti=0;i<1000;i++){v.push_back(i);// 不会触发任何扩容}cout<<"size: "<<v.size()<<", capacity: "<<v.capacity()<<endl;// 输出：size: 1000, capacity: 1000

4.2resize()vsreserve()的区别

vector<int>v;v.reserve(10);// capacity=10, size=0，没有元素cout<<v[0];// 错误！越界访问v.resize(10);// capacity=10, size=10，有 10 个元素（默认值为 0）cout<<v[0];// 正确，输出 0

4.3 释放多余内存：shrink_to_fit()

vector<int>v(1000);// size=1000, capacity=1000v.clear();// size=0, capacity=1000（内存未释放）v.shrink_to_fit();// 请求释放多余内存，capacity 可能变为 0

注意：shrink_to_fit()只是一个请求，标准库不保证一定释放内存。

五、常见面试追问

Q1：扩容时是拷贝还是移动？

C++11 之后：

• 如果元素类型提供了移动构造，则使用移动
• 否则使用拷贝

classMyClass{public:// 有移动构造时，扩容会用移动MyClass(MyClass&&other)noexcept{// 转移资源}// 没有移动构造时，扩容会用拷贝MyClass(constMyClass&other){// 复制资源}};

Q2：为什么不用realloc？

realloc只适用于平凡可复制类型（如int、char）。

对于非平凡类型（如string、自定义类），realloc只会复制内存字节，不会调用移动/拷贝构造函数，会导致错误。

// 以下类型可以安全使用 realloc// int, char, double, POD 结构体// 以下类型不能使用 realloc// string, vector, 有虚函数的类，自定义构造/析构的类

Q3：扩容时迭代器会失效吗？

会。所有指向原容器的迭代器、指针、引用都会失效。

vector<int>v={1,2,3};autoit=v.begin();// 指向元素 1v.push_back(4);// 如果触发扩容，it 将失效// cout << *it; // 未定义行为！

Q4：为什么 vector 的初始 capacity 是 0？

不同编译器实现不同：

• GCC：初始capacity = 0，第一次push_back时扩容到 1
• MSVC：初始capacity = 0或小值

六、总结

一句话记忆：vector 满时按倍数扩容（GCC 2 倍），申请新内存后拷贝/移动元素，均摊 O(1)。