什么是向量数据结构？

Question

什么是向量数据结构？

vectordata-structuresabstract-data-type

29

我知道在C++和Java中有Vector，它类似于动态数组，但我找不到任何关于Vector数据结构的通用定义。那么Vector是什么？它是一种通用的数据结构（像数组、栈、队列、树等），还是它只是一种依赖于语言的数据类型？

- Ikarus

这绝对是一个观点问题。 - gurghet

我对你所谓的“通用数据结构”和“仅限数据类型”所要表达的含义并不清楚。 - user1084944

3个回答

20

这是一个具有动态分配空间的数组，每当超出此空间时，就会为其分配新的内存空间，并将旧数组复制到新数组。然后释放旧内存。

此外，vector通常会分配比需要更多的内存，这样当添加新元素时，就不必复制所有数据。

可能看起来链表比向量好得多，但并非总是如此。如果您不经常更改vector（在大小方面），那么计算机的高速缓存内存使用向量比列表更好，因为它们在内存中连续。缺点是当您有较大的向量需要扩展时，您必须同意将大量数据复制到另一个内存空间。

还有，您可以向Vector末尾和前端添加新数据。因为Vector类似于数组，所以每次想要向向量开头添加元素时，必须复制整个数组。向向量末尾添加元素效率更高。链表则没有这样的问题。

Vector可以随机访问其内部保存的数据，而列表、队列和堆栈则不行。

- DawidPi

1

向量与动态数组相同，具有自动调整大小的能力，当插入或删除元素时会自动调整。
向量元素放置在连续的存储空间中，因此可以使用迭代器访问和遍历。
在向量中，数据是在末尾插入的。

- user2235747

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- JVene · Accepted Answer

"向量"这个词在计算机科学/编程中的应用是从数学借来的，这可能会让人感到困惑(你甚至可能提问多个主题)。

在数学中，最简单的向量示例是数字线，用于教授小学数学(特别是帮助可视化负数、负数减法、负数加法等)。

向量是从一个点出发的距离和方向。这就是它可能会导致混淆的原因，因为向量数据结构可以是三个点X、Y、Z，在3D图形引擎中使用的结构，或者是2D点(只是X、Y)。在这种情况下，两个这样的点的减法结果是一个向量——向量描述从一个源操作数到另一个操作数需要前进多远以及朝哪个方向前进。

这适用于存储，例如stl向量或Java向量，因为存储被表示为从地址的距离(其中内存地址类似于空间中的点或数字线)。

这个概念与数组有关，因为数组可以分配给向量的存储，但我认为向量是一个比数组更大的概念。向量必须包括从起点的距离的概念，如果你把一个数组的开头看作是起点，那么到数组末尾的距离就是它的大小。

因此，表示向量的数据结构必须包括大小，而数组没有存储来包括大小，它是通过分配方式假定的。也就是说，如果你动态地分配一个数组，就没有数据结构存储那个数组的大小，程序员必须假设知道那个大小，或者把它存储在某个整数或长整数中。

向量数据结构(比如向量类的设计)确实需要存储大小，因此，至少会有一个起点(数组的基础，或内存中的某个地址)，以及从该点开始的距离表示大小。"那确实是针对“RAM”的，因为还有一个尚未描述的要点，必须成为描述向量的数据的一部分——元素大小的概念。如果向量表示字节，并且存储器存储通常以字节为单位衡量，那么地址和距离（或大小）将表示字节向量，但没有其他内容，这是非常基于机器层面的思考。更高层次的思考，例如某些结构，具有自己的大小——比如float或double的大小，或者在C++中的结构或类的大小。无论元素大小是多少，存储N个元素所需的内存都需要向量数据结构具有一些关于它正在存储什么以及它有多大的知识。这就是为什么你会想到“字符串向量”或“点向量”。向量还必须存储一个元素大小。

因此，基本的向量数据结构必须具有：

- 地址（起始点） - 元素大小（每个存储的东西的长度为X个字节） - 存储的元素数量（多少个元素乘以元素大小是“最小”存储大小）。

在这个简单的三个条目列表中做出了一个重要的“假设”，即地址被分配了内存，必须在某个时刻释放，并且要防止超出向量的末尾进行访问。

这意味着有一些遗漏的东西。为了使向量类起作用，存储在向量中的项目数和分配给该存储器的内存量之间存在可识别的差异。通常，正如您从使用STL的vector所了解的那样，它可能“知道”它有空间存储10个项目，但当前仅有其中2个。

因此，一个有效的向量类还必须存储内存分配的数量。这将是它如何自动扩展自身的方式——它现在具有足够的信息来自动扩展存储。

思考如何使向量类运作只需要你了解操作向量类所需的数据结构。