std::vector实现使用内部数组、链表或其他数据结构吗？

Question

我听说std::vector在内部实现中有一个C风格的数组，但这不是动态容器的整个目的吗？

那么，在向vector插入值时，它是O(n)操作吗？还是像链表一样是O(1)？

- Aposhian

---

C++中的链表类是std::list。因此，std::vector不是链表--它基本上是一个动态数组，并且具有与您所期望的相同的插入时间（O(n)），除非插入到序列的末尾。https://dev59.com/NHVC5IYBdhLWcg3wykej - PaulMcKenzie

Answer 1

根据C++11标准中"序列容器"库部分（重点在于）：

[23.3.6.1 类模板vector概述][vector.overview] 向量是一种序列容器，支持（摊销的）常数时间插入和删除操作在末尾；在中间插入和删除需要线性时间。存储管理由程序自动处理，但可以给出提示以提高效率。

这并不会破坏动态大小的目的 - 向量的部分优点在于不仅访问单个元素非常快，而且扫描向量具有非常好的内存局部性，因为所有内容都紧密地打包在一起。实际上，具有良好的内存局部性非常重要，因为它大大减少了缓存未命中，这对运行时间有很大影响。这是在许多情况下，特别是在需要经常迭代整个容器而不是添加或删除元素的情况下，向量比列表的主要优势之一。

- Chris Beck

Answer 2

std::vector中的内存必须是连续的，因此通常表示为数组。

你关于std::vector操作复杂度的问题很好 - 我记得自己刚开始编程时也曾经想过这个问题。如果将元素附加到std::vector中，则可能需要执行调整大小操作并将所有现有元素复制到新数组中。在最坏情况下，这将花费O(n)时间。然而，附加元素的摊销成本为O(1)。我们的意思是，任何n次附加到std::vector的序列的总成本始终为O(n)。其背后的直觉是，std::vector通常会在其数组中过度分配空间，留下许多免费插槽供元素插入而无需重新分配。因此，大多数附加操作将花费O(1)的时间，即使偶尔有一个需要花费O(n)的时间。

话虽如此，在 std::vector 中进行插入操作的成本将是 O(n)，因为您可能需要将所有东西向下移动。

您还问了为什么这样做，如果它破坏了动态数组的目的。即使 std::vector 只像托管数组一样工作，它仍然优于原始数组。 std::vector 知道其大小，可以使用 at 进行边界检查，是一个实际的对象（不像数组），并且不会退化为指针。这些额外的功能 - 加上使附加操作快速工作的额外逻辑 - 几乎总是值得的。

- templatetypedef