c++ - STL什么是随机访问和顺序访问？

Question

所以我很好奇地知道，什么是随机访问？

我搜索了一下，却找不到很多。我现在的理解是容器中的“块”是随机放置的(如here所示)。那么，随机访问意味着无论处于什么位置，我都可以访问容器的每个块(因此，我无需先遍历所有块就可以读取位置5上的内容)，而对于顺序访问，我必须经过1st，2nd，第三和第四到达第五块。

我对吗？否则，有人可以向我解释什么是随机访问，什么是顺序访问？

Answer 1

顺序访问意味着访问第5个元素的成本是访问第一个元素的成本的5倍，或者至少与集合中的元素位置相关联的成本增加。这是因为要访问集合的第5个元素，必须首先执行一个操作以找到第1个，第2个，第3个和第4个元素，因此访问第5个元素需要5个操作。

随机访问意味着访问集合中的任何元素的成本与集合中任何其他元素的成本相同。查找集合的第5个元素仍然只是一个操作。

因此，访问随机访问数据结构中的随机元素将具有O(1)成本，而访问顺序数据结构中的随机元素将具有O(n/2)-> O(n)成本。 n/2来自于如果要访问集合中的随机元素100次，则该元素的平均位置将约为集合的一半。因此，对于一组n个元素，得出的结果为n/2(使用大O表示法可以近似地表示为n)。

您可能会觉得很酷的一些东西:

哈希图是实现随机访问的数据结构的示例。要注意的一件很酷的事情是，在哈希图中的哈希冲突中，两个冲突的元素存储在哈希图上该存储桶中的顺序链接列表中。因此，这意味着，如果您对哈希映射有100％的冲突，那么实际上您将最终获得顺序存储。

这是一个哈希图的图像，说明了我正在描述的内容:

这意味着哈希映射的最坏情况实际上是用于访问元素的O(n)，与顺序存储的平均情况相同，或更准确地说，在哈希图中找到元素是Ω(n)，O(1) )和Θ(1)。 Ω是最坏的情况，Θ是最好的情况，O是平均情况。

所以:

顺序访问:在n个元素的集合中找到一个随机元素是Ω(n)，O(n/2)和Θ(1)，对于非常大的数，它们变为Ω(n)，O(n)和Θ(1)。

随机访问:在n个元素的集合中找到一个随机元素是Ω(n/2)，O(1)和Θ(1)，对于非常大的数，它们变为Ω(n)，O(1)和Θ(1)

因此，随机访问具有为元素访问提供更好性能的好处，但是顺序存储数据结构在其他方面也有好处。

@ sumsar1812的第二次编辑:

我想以此作为我对顺序存储的优点/用例的理解，但是我对顺序容器的好处的了解不如上面的答案那么确定。因此，请在任何我误会的地方纠正我。

顺序存储很有用，因为数据实际上将顺序存储在内存中。

通过将指向该集合的前一个元素的指针偏移存储该类型的单个元素所需的字节数，您实际上可以访问顺序存储的数据集的下一个成员。

因此，由于带符号的int需要存储8个字节，因此，如果您有一个固定的整数数组，且其指针指向第一个整数:

int someInts[5];
someInts[1] = 5;

someInts是一个指向该数组第一个元素的指针。向该指针添加1只会使它指向内存中的位置偏移8个字节。

(someInts+1)* //returns 5

这意味着，如果您需要以特定的顺序访问数据结构中的每个元素，它将更快得多，因为每次顺序存储的查找都只是向指针添加了一个常量值。

对于随机存取存储，不能保证每个元素都存储在其他元素附近。这意味着每次查找都将比仅添加恒定量的查询更为昂贵。

随机访问存储容器仍可以使用迭代器来模拟看似是元素的有序列表。但是，只要您允许对元素进行随机访问查找，就不能保证这些元素按顺序存储在内存中。这意味着即使容器可以同时显示随机访问容器和顺序容器的行为，也不会显示顺序容器的好处。

因此，如果假定容器中元素的顺序有意义，或者计划对数据集中的每个元素进行迭代和操作，则可能会受益于顺序容器。

实际上，由于链表(一个顺序容器)实际上没有顺序存储在内存中，而 vector (另一个顺序容器)却在存储，因此它仍然会更加复杂。 Here's a good article that explains use cases for each specific container better than I can.