Ika*_*rus 14 vector abstract-data-type data-structures
我知道C++和Java中的Vector,它就像动态数组,但我找不到Vector数据结构的任何一般定义.那么Vector是什么？Vector是一般数据结构(如arrray,stack,queue,tree,...)还是只是一种取决于语言的数据类型？
JVe*_*ene 19
应用于计算机科学/编程的"向量"一词借鉴了数学,这可能使得使用容易混淆(甚至你的问题也可以在多个主题上).
数学中矢量的最简单的例子是数字线,用于教授基本数学(特别是帮助可视化负数,减去负数,添加负数等).
矢量是距离点的距离和方向.这就是为什么它会混淆讨论的原因,因为矢量数据结构可能是三维点,X,Y,Z,在3D图形引擎中使用的结构,或2D点(只是X,Y).在该上下文中,减去两个这样的点导致向量 - 向量描述从一个源操作数到另一个源操作数的行进距离和方向.
这适用于存储,如stl向量或Java向量,因为存储被表示为距地址的距离(其中存储器地址类似于空间中的点或数字线).
这个概念与数组有关,因为数组可能是为向量分配的存储空间,但我认为向量是一个比数组更大的概念.向量必须包含距起点的距离概念,如果您将数组的开头视为起点,则到数组末尾的距离是它的大小.
因此,表示向量的数据结构必须包含大小,而数组没有包含大小的存储,它是通过它的分配方式来假定的.也就是说,如果动态分配数组,则没有数据结构存储该数组的大小,程序员必须假定知道该大小,或者将其存储在某个整数或长整数中.
矢量数据结构(比如矢量类的设计)需要存储大小,所以至少会有一个起点(数组的基数,或者内存中的某个地址)和距离的起点.指示大小的点.
然而,在描述中,这确实是"RAM"导向,因为还有一点尚未描述,它必须是描述向量的数据的一部分 - 元素大小的概念.如果向量表示字节,并且存储器存储通常以字节为单位测量,则地址和距离(或大小)将表示字节向量,但没有其他任何东西 - 这是一个非常机器级的思考.一个更高的思想,一些结构的思想,有它自己的大小 - 比如,浮点数或双精度的大小,或者C++中的结构或类的大小.无论元素大小是多少,存储N个元素所需的内存都要求向量数据结构知道它存储的内容,以及它的大小.这就是为什么你会想到"字符串向量"或"点向量".
因此,基本矢量数据结构必须具有:
地址(起点)
元素大小(它存储的每个东西都是X字节长)
存储了许多元素(元素大小的元素数量是'最小'存储大小).
在向量数据结构中的这个简单的3项条目列表中做出的一个重要的"假设"是地址被分配了存储器,该存储器必须在某一点被释放,并且要防止在向量的末尾之外的访问.
这意味着缺少一些东西.为了使矢量类工作,存储在矢量中的ITEMS的数量与该存储的ALLOCATED存储量之间存在可识别的差异.通常情况下,正如您可能从使用STL中的矢量中看到的那样,它可能"知道"它有足够的空间存储10个项目,但目前只有2个项目.
因此,工作向量类还必须存储内存分配量.这将是它如何动态扩展自己 - 它现在有足够的信息来自动扩展存储.
通过思考如何使向量类操作,可以为您提供操作向量类所需的数据结构.
它是一个具有动态分配空间的数组,每次超过此空间时,内存中的新位置都会被分配,旧数组将被复制到新数据库中.旧的那个被释放了.
而且,vector通常会分配比它需要的更多的内存,所以当添加新元素时,它不必复制所有数据.
看起来,列表可能要好得多,但并不一定如此.如果你不经常更改矢量(就大小而言),那么计算机的高速缓存存储器对于矢量而不是列表的功能要好得多,因为它们在存储空间中是连续的.缺点是当你有大矢量时,你需要扩展.然后你必须同意将大量数据复制到内存中的另一个空间.
更重要的是.您可以将新数据添加到矢量的末尾和前面.因为Vector类似于数组,所以每次要将元素添加到向量的开头时,都必须复制所有数组.在向量末尾添加元素效率更高.链表没有这样的问题.
Vector可以随机访问内部保存的数据,而列表,队列,堆栈则不然.