std::list与std::forward_list的插入删除性能对比
在实际使用中，std::list和std::forward_list的插入/删除操作真的是O(1)吗？为什么说"已知迭代器位置"这个前提很关键？它们各自在什么场景下性能退化？与vector的插入删除相比如何？
回答
苦行僧
O(1)的前提：必须已经持有指向插入/删除位置的迭代器。如果先find(O(n))再操作，总复杂度O(n)。
list操作：
insert(it, val)：当前节点前插入O(1)(双向链表维护prev指针)erase(it)：O(1)- splice(合并另一个list)：O(1)移动整个链表
- sort：归并排序O(n log n)，但C++23前list::sort是稳定排序
forward_list操作：
insert_after(it, val)：当前位置后插入O(1)erase_after(it)：删除下一个元素O(1)- 没有splice(只有splice_after)
性能退化场景：
- 缓存不友好——list节点在堆中分散分配，遍历比vector慢数倍(缓存未命中)
- 频繁分配/释放——每次插入分配节点，每次删除释放节点，malloc压力大
- 小对象场景——节点指针开销(prev+next)可能超过数据本身
与vector对比：
- vector遍历性能和缓存友好性远超list
- vector即使中间插入(需移动元素)，在小数据量(≤64)也比list快(缓存效应)
- 实测：list 100万次遍历约比vector慢5-10倍
建议：除非有经过验证的频繁中间操作需求且有稳定迭代器，否则优先用vector或deque。