1

我的主要问题是向量如何工作。

我知道链接列表是连接在一起的节点列表。这就是我在脑海中想象的样子。但我无法想象向量是什么样的。

我读到向量具有随机访问权限，就像数组一样。但什么是随机访问？计算机最终不会在内部搜索索引吗？我这样说是因为我可以通过运行 for 循环重载[]运算符以给我链表中的第 i个元素。

还有一个数组是由什么组成的？我知道数组是如何工作的，但它背后是什么，它也是节点的集合吗？我问这个只是为了一般知识。

这是一个关于向量的问题。它看起来与用于链表的函数非常相似。

4

5 回答 5

6

C++ 中的Avector是一个本质上包装数组并在您向其中添加新元素时自动调整其大小的类。

数组本质上只是一个连续的内存块，其中每个元素都在内存中紧挨着放置。

随机访问基本上意味着通过索引访问一个元素，即获取列表中的第 5 个元素。数组（因此vector）通过元素的恒定时间查找提供有效的随机访问。这意味着访问第 5 个元素与访问第 573 个元素一样快。

由于vector包装了一个数组并将其数据作为数组在内部存储，因此元素查找的效率与数组的效率相同（基本上）。它不需要查找索引或类似的东西，因为它将数据保存在数组中。

于 2013-04-23T16:46:39.093 回答
4

通常一个向量有三个数据成员：

  • 指向数据开头的指针
  • 指向数据末尾的指针（或保存向量大小的整数）
  • 一个包含向量当前容量的整数（不要担心这个）

“数据”是一个数组，所以最终一个向量看起来像一个指向包含一些额外信息的数组的指针。

数组是内存中相邻对象的序列，因此每个对象都从比前一个对象的最后一个字节高一个字节的地址开始。

计算机最终不会在内部搜索索引吗？

不，RAM 硬件的部分功能是在不扫描内存的情况下获取指定地址的内容。这就是 RAM 与（例如）转鼓存储器的区别。

在这种情况下，“随机访问”是指最多在固定时间内访问任何地址。

对于向量和数组，i可以通过将偏移量添加到第一个元素的地址来计算第一个元素的地址。以字节为单位的偏移量等于i单个元素大小的倍数。对于链表，获取第ith 个元素的唯一方法是遵循next指针i时间。因此，如果您确实operator[]为链表实现了该功能，则执行更大的值将花费更长的时间i，因此不会提供随机访问。

于 2013-04-23T16:49:07.947 回答
2

一个向量（至少在 C++ 中）表示一个连续的内存块，它保存着大小相等的对象。这允许它在恒定时间内计算任何给定项目的地址，例如：

address = base_address + index * item_size;

请注意，大部分内容都在幕后（可以这么说）——C++（就像之前的 C 一样）根据计算某些指定大小的对象的地址来定义索引，所以实际上代码可能看起来像：

T &operator[](size_t index) { return base[index]; }

...并且编译器处理生成代码以基于sizeof(T).

这意味着访问数组的任何部分都需要代码部分基本相同的机制。公平地说，这并不意味着所有访问都必然具有相同的速度。

例如，数据的一部分可能在缓存中，其他部分在主内存中，还有其他部分很可能在虚拟内存中，其中检索需要从磁盘驱动器读取数据。这可能很容易意味着一百万到一（或更多）的速度差异。

然而，这仍然与链表形成对比，链表需要线性复杂度才能找到链表中任意项的地址。从那里，我们获得了关于如何存储数据的所有相同可能性（并且由于数据不连续，我们往往会获得较差的参考局部性，从而导致任何给定数据更有可能在一种较慢的存储形式）。

于 2013-04-23T16:59:59.877 回答
1

数组是内存中的一个位置以及它后面的一系列串行位置。

考虑我是否有数组int[] a = [1,2,3,4,5,6,7,8,9,10]；

如果我们查看内存中的这个数组，它可能看起来像这样——

15  null           00000000
    null           00000000
    null           00000000
    a[10]          00001011
    a[9]           00001010
10  a[8]           00001001
    a[7]           00001000
    a[6]           00000111
    a[5]           00000110
    a[4]           00000101
5   a[3]           00000100
    a[2]           00000011
    a[1]           00000010
    a[0]           00000001
    other stuff    00011101
0   other stuff    01010101

您可以在数组中随机访问，因为编译器正在为您工作以找到您正在寻找的确切地址。

例如在这种情况下，如果我运行该函数

print(a*); //print the location in memory of a (the pointer to a)

它会输出

2

现在，当我要求 [2]

print (a[2])

编译器实际上在做什么

print (&(a*+2) // print the values at the memory location 
               // that is 2 plus the pointer to a

这意味着它应该打印出内存位置 4 的值，即

3

当我们说一个数组可以随机访问时，这意味着访问的时间是恒定的，因为找到元素 a[100000] 和 a[1] 都需要相同的时间。

1.) look-up a.
2.) add the index to a. 
3.) look-up the value at a + index.

现在向量只是一个数组的包装器。它为数组添加了特殊功能并定义了“行为”。想象它像一个具有 3-4 条数据的结构，其中一些数据是指向特殊“向量函数”的指针。

想象一下这样的数据。

struct vect { 
    int* array; 
    int  arraysize; 
    int* functionPtr1;
    int* functionPtr2;
    int* functi....
};

我要避免在 c 中看起来如何的 gorp，因为我不是很好并且肯定会出错，但是在像 java 这样的面向对象语言中，我们的向量看起来像这样

vect.array[1];
int arg2 = vect.array[2]; 
vect.functionPtr1(2); 
int vectSize = vect.arraysize;

很简单。令人困惑的是，c++ 允许您在对象上定义 [] 运算符。当您执行此操作时，在 c++ 中的向量中。

vect[2];

它实际上只是这里 java 等价物的语法糖：

vect.array[2];

但是 tl;博士; 这一切的版本是向量只是一个用于将函数包装在原始数组周围的对象。C++ 提供了特殊的语法糖，因此您可以直接从对象指针寻址原始数组，而不仅仅是从对象数组成员，但是获取对象数组成员的工作仍在完成，只是抽象出来。

于 2013-04-23T17:18:37.587 回答
1

在不特定于语言的情况下，这些术语通常意味着：

  • 数组是一个固定长度的、非结构化的连续内存区域。通过计算与基地址的偏移量来访问位置。
  • 向量像数组一样是随机访问的，但知道它的长度，因此可以动态更改它。
  • 链表是完全动态且不连续的，因此它不是随机访问的。
于 2013-04-23T16:47:53.880 回答