deque 的底层实现
哪些公司问过
答案要点
- deque 由中控器(map,存放指针的数组)加多个固定大小的缓冲区组成
- 迭代器保存当前位置、所在缓冲区首尾和中控器指针,可在缓冲区间跳转,支持随机访问
- 两端插入:缓冲区未满直接放,满了分配新缓冲区;扩容只拷贝指针,不搬移元素,O(1)
- 中间插入删除需要移动元素,O(n)
- 适合需要两端操作的场景;是 stack、queue 默认的底层容器
易错点
- 说 deque 是一整块连续内存
- 认为 deque 中间插入也是 O(1)
- 混淆 deque 与 list
- 忘了迭代器与引用的失效规则不同
面试官常见追问
- deque 和 vector 有什么区别?
- 为什么 stack 和 queue 默认用 deque?
- deque 的迭代器会失效吗?
- deque 的随机访问怎么实现?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- vector 的扩容机制与性能174 场
- map 与 unordered_map 的区别167 场
- STL 的组成与常用容器151 场
- vector 与 list 的区别85 场
- STL 迭代器失效的场景47 场
- map 的底层实现:为什么用红黑树47 场
- STL 内存分配器12 场
- unordered_map 底层实现、哈希冲突与 rehash9 场
- vector 和数组的区别8 场
- 迭代器的作用与分类7 场