c++ - vector 是链表的特例吗？

Question

说起STL，有几个同学跟我说“vector 就是链表”。

我还有一个人争辩说，如果你用迭代器调用 erase() 方法，它会破坏 vector ，因为它是一个链表。

他们也往往不明白为什么我总是认为 vector 是连续的，就像任何其他数组一样，并且似乎不明白随机访问的含义。 vector 是否像常规数组一样严格连续，或者最多是连续的？ (例如，如果整个数组不适合，它将分配几个连续的段)。

Answer 1

很抱歉，你的同学完全错了。如果你的同学可以诚实地说“vector 是链表”，那么你需要恭敬地告诉他们，他们需要拿起a good C++ book (或任何体面的计算机科学书籍)并阅读它。或者甚至是 vectors 的 Wikipedia 文章和 lists . (另见 dynamic arrays 和 linked lists 的文章。)

---

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

例如，插入是链表上的常数时间操作，而如果插入到末尾以外的位置，则它是 vector 上的线性时间操作。 (但是，如果您在 vector 的末尾插入，它是摊销常数时间。)

std::vector C++ 中的类要求按照 C++ 标准是连续的:

23.2.4/1 Class template vector

A vector is a kind of sequence that supports random access iterators. In addition, it 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 efficienty. The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

将其与 std::list 进行比较:

23.2.2/1 Class template list

A list is a kind of sequence that supports bidirectional iterators and allows constant time insert and erase operations anywhere within the sequence, with storage management handled automatically. Unlike vectors (23.2.4) and deques (23.2.1), fast random access to list elements is not supported, but many algorithms only need sequential access anyway.

显然，C++ 标准规定 vector 和列表是两个不同的容器，它们做事不同。

你不能通过简单地调用 erase() 来“破坏”一个 vector (至少不是故意的)。使用有效的迭代器。这将使 std::vector s 相当没用，因为它的存在就是为你管理内存!