向量是链接列表的特殊情况吗？ [英] Are vector a special case of linked lists?

问题描述

当谈论STL时，我有几个同学告诉我向量是链接列表。

我有另一个说，如果你调用擦除）方法与一个迭代器，它打破了向量，因为它是一个链表。

他们也往往不明白为什么我一直在争论的矢量是连续的，就像任何其他阵列，并且似乎不了解什么随机存取的意思。向量是严格连续的，就像常规数组，或只是最接近？ （例如，如果整个数组不适合，它将分配几个连续的段）。

解决方案

你的同学完全错了。如果你的同学可以诚实地说向量是链接列表，那么你需要尊重地告诉他们，他们需要选择一个好的C ++书（或任何体面的计算机科学书），并阅读它。或者甚至是向量和列表。 （另请参阅有关动态数组和链接列表。）

---

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

例如，插入操作是链表上的常数操作，而对向量是线性时操作如果它被插入到除了结束之外的某处。 （但是，如果您在向量的末尾插入，则是固定时间）。

std :: vector c>在C ++中的类是必须连接到C ++标准：

23.2.4 / 1类模板矢量

A vector 是一种支持随机存取迭代器的序列。此外，它支持（摊销）在结束时的恒定时间插入和擦除操作;插入和擦除在中间取线性时间。存储管理是自动处理的，虽然可以提供提示以提高效率。 向量的元素连续存储，表示如果 v 是 vector 其中 T 是除 bool ，则它遵守所有 0 <= n <1>的身份& v [n] ==& v [0] + n ; std :: list

/ code>：

23.2.2 / 1类模板 $ c>

A 列表是一种支持双向迭代器的序列，在序列内的任何位置插入和擦除操作，自动处理存储管理。与向量（23.2.4）和deques（23.2.1）不同，不支持快速随机访问列表元素，但许多算法只需要顺序访问。

很明显，C ++标准规定一个向量和一个列表是两个不同的容器，它们做的事情不同。

一个向量（至少不是有意的）通过用一个有效的迭代器调用 erase（）。这将使 std :: vector 相当无用，因为它的存在点是为你管理内存！

When talking about the STL, I have several schoolmates telling me that "vectors are linked lists".

I have another one arguing that if you call the erase() method with an iterator, it breaks the vector, since it's a linked list.

They also tend to don't understand why I'm always arguing that vector are contiguous, just like any other array, and don't seem to understand what random access means. Are vector stricly contiguous just like regular arrays, or just at most contiguous ? (for example it will allocate several contiguous segments if the whole array doesn't fit).

解决方案

I'm sorry to say that your schoolmates are completely wrong. If your schoolmates can honestly say that "vectors are linked lists" then you need to respectfully tell them that they need to pick up a good C++ book (or any decent computer science book) and read it. Or perhaps even the Wikipedia articles for vectors and lists. (Also see the articles for dynamic arrays and linked lists.)

---

Vectors (as in std::vector) are not linked lists. (Note that std::vector do not derive from std::list). While they both can store a collection of data, how a vector does it is completely different from how a linked list does it. Therefore, they have different performance characteristics in different situations.

For example, insertions are a constant-time operation on linked lists, while it is a linear-time operation on vectors if it is inserted in somewhere other than the end. (However, it is amortized constant-time if you insert at the end of a vector.)

The std::vector class in C++ are required to be contiguous by the C++ standard:

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().

Compare that to 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.

Clearly, the C++ standard stipulates that a vector and a list are two different containers that do things differently.

You can't "break" a vector (at least not intentionally) by simply calling erase() with a valid iterator. That would make std::vectors rather useless since the point of its existence is to manage memory for you!

这篇关于向量是链接列表的特殊情况吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！