STL是什么？随机访问和顺序访问是什么意思？

Question

STL是什么？随机访问和顺序访问是什么意思？

7

我很好奇什么是随机访问？

我查了一点，但没有找到太多相关信息。我现在的理解是，容器中的“块”是随机放置的（如此处所示）。然后，随机访问意味着我可以访问容器中的每个块，无论位置如何（因此我可以读取第5个位置上的内容，而不必遍历前面的所有块），而使用顺序访问，则需要依次遍历前四个块才能到达第五个块。

我的理解正确吗？如果不是，那么有人可以向我解释一下什么是随机访问和顺序访问吗？

- Sumsar1812

4

是的，你关于它们如何被访问的说法是正确的。但我不确定你所说的“容器中的块是随机放置”的意思。无论它是什么意思，听起来都不正确。 - Benjamin Lindley

@BenjaminLindley 谢谢！ - Sumsar1812

我不在乎教科书如何定义它，如果你上面的定义是正确的，那么我猜迭代器实际上是顺序访问而不是随机访问。但这并不意味着数组不是随机访问。 - windmaomao

3个回答

3

有两个主要方面需要考虑，不清楚其中哪一个与你的问题更相关。其中一个方面是通过迭代器访问STL容器的内容，这些迭代器允许随机访问或前向（顺序）访问。另一个方面是以随机或顺序方式访问容器甚至只是内存本身。

迭代器-随机访问 vs. 顺序访问

首先看迭代器，以两个示例为例：std::vector<T>和std::list<T>。向量存储值的数组，而列表存储值的链接列表。前者在内存中按顺序存储，这使得任意随机访问变得高效：计算任何元素的位置就像计算下一个元素的位置一样快。因此，顺序存储为您提供了有效的随机访问，并且迭代器是随机访问迭代器。

相比之下，列表为每个节点执行单独的分配，每个节点只知道其邻居的位置。因此，直接计算随机的非邻居节点的位置是不可能的。任何这样尝试的行为都必须遍历所有中间节点，因此试图跳过节点的算法可能表现很差。非顺序存储产生随机位置，因此仅提供有效的顺序访问。因此，列表提供的迭代器是一种双向迭代器，其中有几种不同的顺序迭代器。

内存 - 随机访问与顺序访问

然而，您的问题还有另一个问题。迭代器部分仅涉及容器的遍历。在此之下，CPU将以特定模式访问内存本身。虽然在高级别上，CPU能够无需计算其位置就寻址任何随机地址（就像一个大向量），但实际上，读取内存涉及缓存和许多微妙之处，使得访问不同部分的内存需要不同的时间。

例如，一旦您开始使用相当大的数据集，即使您正在使用向量，按顺序访问所有元素比以任意顺序访问所有元素更有效率。相比之下，列表无法做到这一点。由于列表的节点甚至不一定位于连续的内存位置上，即使按顺序访问列表的项也可能不会按顺序读取内存，并且因此可能更加昂贵。

- Michael Urman

我正在验证自己的理解，如果我错了，请纠正我。所以这就是访问固定大小数组中的元素比向量更有效的原因，因为由于所有固定大小数组的内存一次性分配，您可以保证数组的每个元素实际上是按顺序存储在内存中的？而对于像向量这样的东西，迭代它只是模拟按顺序存储的元素的行为（因为有些可能在不同的时间分配）。 - echochamber

1

@echochamber 不，向量的分配与数组相同，因为如果它需要调整大小，则向量将重新分配并复制/移动所有元素，因此这些应该是等效的（除非您使用vec.at(n)或者编译器优化不佳）。重要的区别在于，例如，向量和列表。 - Michael Urman

啊，这样就说得通了。感谢您的澄清。 - echochamber

@MichaelUrman：通常使用迭代器时很少听到“sequential access”，我们通常使用以下标签之一：“input”、“output”、“forward”、“bidirectional”或“random access”。 - Mooing Duck

@MooingDuck 这很公平。把它表述为“顺序遍历”会更好吗？例如，“[List提供]双向迭代器之一，提供顺序遍历的迭代器类型。” - Michael Urman

@MichaelUrman：我不确定我在暗示什么。我只是假设他指的是内存，因为有“访问”这个词，但你说得对，他可能指的是迭代器，两者都讨论是很好的。 - Mooing Duck

2

这些术语本身并不意味着任何性能特征，正如@echochamber所说。这些术语只是指一种访问方法。

“随机访问”是指以任意顺序访问容器中的元素。例如，std::vector是C++容器的一个例子，它在随机访问方面表现出色。而std::stack则是C++容器的一个例子，它甚至不允许随机访问。

“顺序访问”是指按顺序访问元素。这仅适用于有序容器。有些容器对顺序访问进行了更好的优化，例如std::list。

以下是一些代码以展示它们的区别：

// random access. picking elements out, regardless of ordering or sequencing.
// The important factor is that we are selecting items by some kind of
// index.
auto a = some_container[25];
auto b = some_container[1];
auto c = some_container["hi"];

// sequential access. Here, there is no need for an index.
// This implies that the container has a concept of ordering, where an
// element has neighbors
for(container_type::iterator it = some_container.begin();
    it != some_container.end();
    ++ it)
{
    auto d = *it;
}

- tenfour

不，我说这些术语本身并不意味着性能。仅仅说“这个容器支持随机访问”并不意味着它的性能行为。 - tenfour

我越想越觉得你是对的，但很难想到任何可以称为随机访问的O(n)算法，但我确实见过O(log(n))的随机访问，所以你的观点是正确的。 - Mooing Duck

需要注意的是，“sequential”可以指存储和访问方式。例如，std::vector是一种具有随机访问的顺序存储容器，而std::list是一种具有顺序访问的顺序存储容器。 - wulfgarpro

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

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

- echochamber · Accepted Answer

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

随机访问意味着访问集合中的任何元素都具有相同的成本。仍然只需要一次操作即可找到集合的第五个元素。

因此，在随机访问数据结构中访问随机元素将具有O(1)的成本，而在顺序访问数据结构中访问随机元素将具有O(n/2) -> O(n)的成本。n/2来自于如果想在一个集合中访问100次随机元素，那么该元素的平均位置将大约在集合中间。因此，对于n个元素的集合，这将变成n/2（在大O符号表示法中可以近似为n）。

你可能会发现很酷：

Hashmap是实现随机访问的数据结构之一。值得注意的是，在哈希映射中发生哈希冲突时，两个冲突元素将存储在哈希映射桶中的一个顺序链表中。这意味着，如果哈希映射存在100％的冲突，则实际上会得到顺序存储。

下面是一个哈希映射的示例图：

Hashmap

这意味着哈希映射的最坏情况是访问元素的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的第二次编辑：

我想先说明一下，这是我理解顺序存储的优势/用例的方式，但我对顺序容器的好处理解不如上面的回答那么确定。所以，请在我有误的地方指正我。

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

你可以通过将指针偏移存储单个元素所需的字节数来访问顺序存储数据集的下一个成员。

因此，由于有符号整数需要8个字节来存储，如果你有一个整数固定数组，并且有一个指向第一个整数的指针：

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

someInts是指向该数组第一个元素的指针。将1添加到该指针只是通过8个字节偏移其在内存中的指向位置。

(someInts+1)* //returns 5

这意味着，如果您需要按特定顺序访问数据结构中的每个元素，则由于对于顺序存储的每个查找只需将一个常量值添加到指针中，因此速度会更快。对于随机访问存储，无法保证每个元素都存储在其他元素附近，这意味着每次查找都比仅添加常量值要昂贵得多。随机访问存储容器仍可以通过使用迭代器模拟似乎是有序元素的列表。但是，只要允许随机访问查找元素，就无法保证这些元素按顺序存储在内存中。这意味着，即使容器可以表现出随机访问容器和顺序容器的行为，它也不会表现出顺序容器的优点。因此，如果容器中元素的顺序具有意义，或者您计划迭代并操作数据集中的每个元素，则可能从顺序容器中受益。实际上，情况还要更加复杂，因为顺序容器中的链表实际上并没有按顺序存储在内存中，而向量（另一种顺序容器）则是如此。这是一篇很好的文章，比我能做得更好地解释了每个特定容器的用例。