vector - 什么是向量数据结构

Question

我知道C ++和Java中的Vector，就像动态数组一样，但是我找不到Vector数据结构的任何一般定义。那么什么是Vector？ Vector是一种通用的数据结构（如arrray，堆栈，队列，树等）还是只是一种取决于语言的数据类型？

Answer 1

运用于计算机科学/编程的“向量”一词是从数学中借用的，这会使使用变得混乱（即使您的问题可能涉及多个主题）。

数学中向量的最简单示例是数字线，用于教授基础数学（尤其是帮助形象化负数，减负数，加负数等）。

向量是到一个点的距离和方向。这就是为什么它会引起讨论混乱的原因，因为在3D图形引擎中使用的矢量数据结构可能是X，Y，Z三个点，或者是2D点（仅X，Y）。在这种情况下，两个这样的点相减得出一个向量-向量描述了从一个源操作数到另一个操作数的传播距离和方向。

这适用于类似于stl向量或Java向量的存储，因为存储表示为距地址（内存地址类似于空间中的点或数字线上的点）的距离。

这个概念与数组有关，因为数组可以是为向量分配的存储空间，但是我认为向量是比数组更大的概念。向量必须包含到起点的距离的概念，如果您将数组的起点视为起点，则到数组终点的距离就是它的大小。

因此，表示向量的数据结构必须包含大小，而数组没有存储空间来包含大小，这是通过分配方式来假定的。也就是说，如果您动态分配一个数组，则没有存储该数组大小的数据结构，程序员必须假定知道该大小，或者将其存储为某个整数或长整数。

矢量数据结构（例如，矢量类的设计）确实需要存储大小，因此，至少要有一个起点（数组的基点，或内存中的某个地址）以及与之的距离点指示大小。

不过，在描述中，这实际上是面向“ RAM”的，因为还没有描述一点，它必须是描述向量的数据的一部分-元素大小的概念。如果向量代表字节，并且内存存储通常以字节为单位，则地址和距离（或大小）将代表字节向量，但除此之外别无其他-这是一个非常机器层面的思考。更高的思想（某种结构的思想）具有自己的大小-例如，float或double的大小，或者C ++中的结构或类的大小。无论元素大小是多少，存储N个元素所需的内存都要求矢量数据结构了解其存储的内容以及该对象的大小。这就是为什么您会考虑“字符串向量”或“点向量”的原因。向量还必须存储元素大小。

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

地址（起点）

元素大小（存储的每个元素长X个字节）

存储的元素数量（元素数量乘以元素大小等于“最小”存储大小）。

在向量数据结构的这个简单的3项条目列表中做出的一个重要“假设”是，为地址分配了内存，必须在某个时候释放该地址，并应防止在向量的末尾进行访问。

这意味着缺少一些东西。为了使向量类起作用，在向量中存储的ITEMS数量与为该存储分配的内存量之间存在可识别的差异。通常，正如您可能从STL的矢量中发现的那样，它可能“知道”它有存储10个项目的空间，但是目前只有2个项目。

因此，工作向量类还必须存储内存分配量。这将是它可以动态扩展自身的方式-现在它将具有足够的信息来自动扩展存储。

通过仔细考虑如何使向量类进行操作，可以为您提供操作向量类所需的数据结构。