讲一下STL中的list
哪些公司问过
答案要点
- 双向链表,节点含数据、prev、next,常见实现带哨兵节点形成环
- 已知迭代器时任意位置插删 O(1),其他迭代器不失效
- 不支持随机访问,迭代器为双向迭代器
- 排序用成员函数 list::sort(常见为归并排序),因为 std::sort 需要随机访问迭代器
- splice 不拷贝即可转移节点;缺点是额外指针开销、缓存不友好
易错点
- 对 list 使用 std::sort 导致编译错误
- 以为 list 插入删除会使所有迭代器失效
- 认为 list 在所有插入场景都比 vector 快
面试官常见追问
- list 和 vector 怎么选?
- 为什么 std::sort 不能用于 list?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- vector 的扩容机制与性能174 场
- map 与 unordered_map 的区别167 场
- STL 的组成与常用容器151 场
- vector 与 list 的区别85 场
- STL 迭代器失效的场景47 场
- map 的底层实现:为什么用红黑树47 场
- STL 内存分配器12 场
- deque 的底层实现10 场
- unordered_map 底层实现、哈希冲突与 rehash9 场
- vector 和数组的区别8 场