Apo*_*ian 3 c++ arrays stl vector time-complexity
我被告知std :: vector在内部实现上有一个C风格的数组,但这不会否定拥有动态容器的整个目的吗？
那么在向量中插入一个值是否为O(n)运算？或者它是否像链接列表中的O(1)一样？
从C++ 11标准,在"序列容器"库部分(强调我的):
[23.3.6.1类模板
vector概述] [vector.overview]
向量是一个序列容器,它支持(分期)常量时间插入和擦除操作; 在中间插入和擦除需要线性时间.存储管理是自动处理的,但可以提供提示以提高效率.
这并没有破坏动态大小的目的 - 向量点的一部分不仅是访问单个元素非常快,而且对向量进行扫描具有非常好的内存局部性,因为所有内容都紧密地组合在一起.在实践中,具有良好的内存局部性非常重要,因为它极大地减少了缓存未命中,这对运行时有很大影响.这是一大优势,vector在list许多情况下,特别是那些需要往往比你需要添加或删除元素遍历整个容器.
| 归档时间： |
|
| 查看次数： |
735 次 |
| 最近记录： |