面试题库 › 音视频 › STL 常用容器插入操作的时间复杂度

STL 常用容器插入操作的时间复杂度

难度 ★☆☆在 3 场真实面经中被问到 方向:音视频考点:STL容器与算法

哪些公司问过

百度1哔哩哔哩1灵犀互娱1

常见岗位:游戏客户端、音视频开发、C/C++ 软件开发

答案要点

  1. vector 尾插均摊 O(1),中间或头部插入 O(n),扩容时搬迁全部元素
  2. deque 头尾插入 O(1),中间插入 O(n)
  3. list 已知迭代器时任意位置插入 O(1),查找位置需 O(n)
  4. map/set 基于红黑树插入 O(log n);unordered 系列平均 O(1)、最坏 O(n)
  5. priority_queue 插入 O(log n);vector 扩容会使迭代器全部失效

易错点

面试官常见追问

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

相关面试题