顺序容器选择 · 操作成本实验台
把工作负载拆成访问、定位与修改,再检查接口和存储契约。排名会实时变化,但不会把复杂度伪装成跑分。
解释性模型:分数只用于比较趋势。元素大小、分配器、缓存、实现与真实数据都会改变实际耗时,最终决策仍应测量。
容器实时评分
vector
deque
list
forward_list
array
容器 / 结论趋势分成本拆解
定位成本:先找到要操作的位置
修改成本:移动元素或改链接
局部性:顺序访问时的缓存友好度
模型如何看中间操作:
总趋势 ≈ 操作权重 ×(定位成本 + 修改成本 + 局部性惩罚)。
链表只有在“已经拿到目标迭代器”时,结构修改才体现常数级优势;只有下标时,走到第 N 个节点仍需要线性遍历。