vector 是链表的特例吗? [英] Are vector a special case of linked lists?

问题描述

说到STL，有几个同学跟我说向量就是链表".

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

我还有另外一个说法，如果你用迭代器调用 erase() 方法，它会破坏向量，因为它是一个链表.

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.

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

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

推荐答案

很抱歉，你的同学完全错了.如果你的同学可以诚实地说向量是链表"那么你需要恭敬地告诉他们他们需要拿起一本好的 C++ 书籍(或任何像样的计算机科学书籍)并阅读它.或者甚至是关于 vectors 和 列表.(另请参阅动态数组和链接列表.)

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

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

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

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

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

23.2.4/1 类模板vector

A vector 是一种支持随机访问迭代器的序列.此外，它支持(摊销)最后的恒定时间插入和擦除操作；在中间插入和擦除需要线性时间.存储管理是自动处理的，但可以提供提示以提高效率.vector 的元素是连续存储的，这意味着如果 v 是一个 vector 其中T 是除 bool 以外的某种类型，那么它服从 &v[n] == &v[0] + n对于所有 0 <= n .

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 类模板list

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

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++ 标准规定向量和列表是两种不同的容器，它们的作用不同.

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

您不能通过使用有效迭代器简单地调用 erase() 来破坏"向量(至少不是故意的).那会使 std::vector 变得毫无用处，因为它存在的意义在于为您管理内存！

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!

这篇关于vector 是链表的特例吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！