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

面试每日一题 Day 1 —— C vector 扩容机制一、题目描述C 中std::vector的扩容机制是什么请详细说明触发条件、扩容策略、底层过程和复杂度。二、考点分析项目内容核心知识点STL 容器底层实现、动态数组、均摊复杂度分析难度⭐⭐⭐面试出现频率⭐⭐⭐⭐⭐高频三、详细回答3.1 触发条件当vector的当前元素个数size()等于当前容量capacity()时再执行push_back()等添加元素的操作会触发扩容。#includeiostream#includevectorusingnamespacestd;intmain(){vectorintv;coutsize: v.size(), capacity: v.capacity()endl;// 输出size: 0, capacity: 0v.push_back(1);coutsize: v.size(), capacity: v.capacity()endl;// 输出size: 1, capacity: 1触发扩容v.push_back(2);coutsize: v.size(), capacity: v.capacity()endl;// 输出size: 2, capacity: 2触发扩容v.push_back(3);coutsize: v.size(), capacity: v.capacity()endl;// 输出size: 3, capacity: 4触发扩容return0;}3.2 扩容策略不同编译器的实现差异编译器扩容因子说明GCC (libstdc)×2新容量 旧容量 × 2Clang (libc)×2新容量 旧容量 × 2MSVC×1.5新容量 旧容量 × 1.5为什么选择 1.5 或 2倍数太小频繁扩容性能差倍数太大内存浪费严重1.5-2 倍是经验上空间和时间的最优平衡3.3 扩容的底层过程详细步骤判断检测到size capacity需要扩容计算新容量 旧容量 × 扩容因子至少为 1因为容量为 0 时需要特殊处理分配在堆上申请一块新的连续内存大小为新容量 × sizeof(T)迁移C98 标准逐个拷贝构造元素到新内存C11 及以后尽可能使用移动构造提升效率释放释放旧内存更新指针指向新内存3.4 时间复杂度分析操作单次复杂度说明push_back不扩容O(1)直接在末尾构造元素push_back触发扩容O(n)需要迁移 n 个元素n 次push_back的总时间O(n)均摊到每次是 O(1)均摊分析以扩容因子 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 - 1n 次 push 总操作数 ≈ n构造 (n-1)迁移 O(n)均摊到每次 push_backO(1)3.5 完整代码验证#includeiostream#includevectorusingnamespacestd;intmain(){vectorintv;cout初始: sizev.size(), capacityv.capacity()endl;for(inti0;i20;i){intoldCapv.capacity();v.push_back(i);intnewCapv.capacity();if(newCapoldCap){coutpush i 后触发扩容: capacity 从 oldCap 变为 newCapendl;}}return0;}输出GCC 环境初始: size0, capacity0 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()预分配空间vectorintv;v.reserve(1000);// 一次性分配 1000 个元素的空间for(inti0;i1000;i){v.push_back(i);// 不会触发任何扩容}coutsize: v.size(), capacity: v.capacity()endl;// 输出size: 1000, capacity: 10004.2resize()vsreserve()的区别方法作用是否构造元素是否改变 sizereserve(n)预分配 n 个元素的空间❌ 不构造❌ 不变resize(n)将 size 改为 n✅ 构造/析构✅ 改变vectorintv;v.reserve(10);// capacity10, size0没有元素coutv[0];// 错误越界访问v.resize(10);// capacity10, size10有 10 个元素默认值为 0coutv[0];// 正确输出 04.3 释放多余内存shrink_to_fit()vectorintv(1000);// size1000, capacity1000v.clear();// size0, capacity1000内存未释放v.shrink_to_fit();// 请求释放多余内存capacity 可能变为 0注意shrink_to_fit()只是一个请求标准库不保证一定释放内存。五、常见面试追问Q1扩容时是拷贝还是移动C11 之后如果元素类型提供了移动构造则使用移动否则使用拷贝classMyClass{public:// 有移动构造时扩容会用移动MyClass(MyClassother)noexcept{// 转移资源}// 没有移动构造时扩容会用拷贝MyClass(constMyClassother){// 复制资源}};Q2为什么不用reallocrealloc只适用于平凡可复制类型如int、char。对于非平凡类型如string、自定义类realloc只会复制内存字节不会调用移动/拷贝构造函数会导致错误。// 以下类型可以安全使用 realloc// int, char, double, POD 结构体// 以下类型不能使用 realloc// string, vector, 有虚函数的类自定义构造/析构的类Q3扩容时迭代器会失效吗会。所有指向原容器的迭代器、指针、引用都会失效。vectorintv{1,2,3};autoitv.begin();// 指向元素 1v.push_back(4);// 如果触发扩容it 将失效// cout *it; // 未定义行为Q4为什么 vector 的初始 capacity 是 0不同编译器实现不同GCC初始capacity 0第一次push_back时扩容到 1MSVC初始capacity 0或小值六、总结要点内容触发条件size() capacity()时push_back触发扩容扩容因子GCC/Clang ×2MSVC ×1.5底层过程申请新内存 → 迁移元素 → 释放旧内存时间复杂度单次 O(n)均摊 O(1)优化方法使用reserve()预分配迭代器失效扩容后所有迭代器失效一句话记忆vector 满时按倍数扩容GCC 2 倍申请新内存后拷贝/移动元素均摊 O(1)。