面试题库 › C++ / 后端 › vector 常用操作的时间复杂度与 push_back 均摊分析

vector 常用操作的时间复杂度与 push_back 均摊分析

难度 ★★☆在 3 场真实面经中被问到 方向:C++ / 后端考点:STL容器与算法

哪些公司问过

蔚来1文远知行1PDD1

常见岗位:C/C++ 软件开发、C++ 后端

答案要点

  1. 随机访问、尾部插入删除 O(1),push_back 为均摊 O(1);中间插入删除和查找 O(n)
  2. 扩容按倍数增长(GCC 2 倍、MSVC 1.5 倍),插入 N 个元素总搬移次数 O(N),均摊 O(1)
  3. 按固定增量扩容会使总代价变成 O(N²),所以必须几何增长
  4. swap 只交换内部指针,O(1);clear 只析构元素、不释放容量
  5. 扩容会使迭代器、指针和引用失效;已知规模时先 reserve 减少重新分配

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题