矢量是链表的特例吗？

Question

在谈论STL时，有几个同学告诉我“向量是链表”。

我还有另一个观点，如果你用迭代器调用擦除（）方法，它会破坏向量，因为它是一个链接列表。

他们也往往不理解为什么我总是认为向量是连续的，就像任何其他数组一样，并且似乎不理解随机访问的含义。向量是像常规数组一样严格连续，还是最多连续？ （例如，如果整个数组不适合，它将分配几个连续的段）。

Answer 1

我很遗憾地告诉你，你的同学完全错了。如果你的同学可以诚实地说“向量是链表”，那么你需要恭敬地告诉他们，他们需要拿起一本好的 C++ 书籍（或任何像样的计算机科学书籍）并阅读它。或者甚至可能是 向量 和 列表。 （另请参阅动态数组和链表。）

---

向量（如 std::vector）不是链表。 （请注意，std::vector 不是从 std::list 派生的）。虽然它们都可以存储数据集合，但向量的存储方式与链表的存储方式完全不同。因此，它们在不同的情况下具有不同的性能特点。

例如，插入是链表上的常量时间操作，而如果插入到末尾以外的其他位置，则它是向量上的线性时间操作。 （但是，如果在向量末尾插入，则它是摊销常量时间。）

C++ 中的 std::vector 类是必需的 按照 C++ 标准是连续的：

23.2.4/1 类模板向量

向量是一种支持随机访问迭代器的序列。此外，它还支持末尾（摊销）恒定时间插入和擦除操作；中间的插入和擦除需要线性时间。存储管理是自动处理的，但可以给出提示以提高效率。 向量的元素是连续存储的，这意味着如果v是一个向量，其中T 是 bool 以外的某种类型，那么它遵循恒等式 &v[n] == &v[0] + n对于所有 0 <= n < v.size().

与 std::list 进行比较：

23.2.2/1 类模板列表

列表是一种支持双向迭代器的序列，并允许在序列中的任何位置进行恒定时间插入和擦除操作，并自动处理存储管理。与向量（23.2.4）和双端队列（23.2.1）不同，不支持对列表元素的快速随机访问，但许多算法无论如何只需要顺序访问。

显然，C++ 标准规定向量和列表是两个不同的容器，它们的作用不同。

您不能通过简单地使用有效迭代器调用 erase() 来“破坏”向量（至少不是故意的）。这将使 std::vector 变得毫无用处，因为它存在的目的是为您管理内存！

Answer 2

vector 会将其所有存储空间保存在一个位置。 向量 与链表一点也不像。事实上，如果我必须选择两个最不同的数据结构，那就是向量和列表。 “至多连续”是双端队列的运作方式。

Vector：

1. 保证所有元素的连续存储 - 将复制或移动元素。
2. O(1) 访问时间。
3. O(n) 用于插入或删除。
4. 迭代器在插入或删除任何元素时失效。

列表：

1. 根本没有连续存储 - 从不复制或移动元素。
2. O(n) 访问时间 - 加上您将遇到的所有令人讨厌的缓存未命中。
3. O(1) 插入或删除。
4. 只要特定元素未被删除，迭代器就有效。

正如您所看到的，它们在每个数据结构用例中的行为都不同。

Answer 3

根据定义，向量是类似于 C 数组的连续内存块。请参阅：http://en.wikipedia.org/wiki/Vector_(C%2B) %2B)

向量允许随机访问；那是，
向量的元素可以是
以同样的方式引用
数组的元素（按数组索引）。
另一方面，链表和集合
手，不支持随机访问或
指针算术。

Answer 4

向量不是链接的链表，它们提供随机访问并且像数组一样是连续的。为了实现这一目标，他们在后台重新分配内存。

列表的设计目的是允许快速插入和删除，同时不会使任何引用或迭代器无效，除了
那些到被删除的元素。