c – std :: vector实现是否使用内部数组或链表或其他？

发布时间：2020-12-16 10:01:24 所属栏目：百科来源：网络整理

导读：我被告知std :: vector在内部实现上有一个C风格的数组,但这不会否定拥有动态容器的整个目的吗？那么在向量中插入一个值是否为O(n)运算？或者它是否像链接列表中的O(1)一样？解决方法从C 11标准,在“序列容器”库部分(强调我的)： [23.3.6.1 Class templat

我被告知std :: vector在内部实现上有一个C风格的数组,但这不会否定拥有动态容器的整个目的吗？

那么在向量中插入一个值是否为O(n)运算？或者它是否像链接列表中的O(1)一样？

解决方法

从C 11标准,在“序列容器”库部分(强调我的)：

[23.3.6.1 Class template vector overview][vector.overview]
A vector is a sequence container that supports (amortized) constant time insert and erase operations at the
end; insert and erase in the middle take linear time. Storage management is handled automatically,though
hints can be given to improve efficiency.

这并没有破坏动态大小的目的 – 向量点的一部分不仅是访问单个元素非常快,而且对向量的扫描具有非常好的内存局部性,因为所有内容都紧密地组合在一起.在实践中,具有良好的内存局部性非常重要,因为它极大地减少了缓存未命中,这对运行时有很大影响.在许多情况下,这是矢量超列表的一个主要优点,特别是那些需要比需要添加或删除元素更频繁地迭代整个容器的情况.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!