谁能知道为什么将元素插入列表中间比将元素插入向量中间更快？
我更喜欢使用向量，但如果可以的话，我会被告知使用列表。任何人都可以解释为什么？是否总是建议使用列表而不是向量？
问问题
4423 次
4 回答
9
如果我逐字回答这个问题，找到一个数组的中间（std::vector）是一个简单的操作，你将长度除以二，然后向上或向下舍入以获得索引。查找双向链表（std::list）的中间需要遍历所有元素。即使你知道它的大小，你仍然需要走过一半以上的元素。因此 std::vector 比 std::list 快，换句话说，一个是 O(1) 而另一个是 O(n)。
在已知位置插入需要对数组的相邻元素进行混洗，并仅在另一个节点中链接以获得双向链表，正如其他人在此处解释的那样。因此，使用 O(1) 的 std::list 比使用 O(n) 的 std::vector 快。
在一起，要插入到精确的中间，我们有 O(1) + O(n) 的数组和 O(n) + O(1) 的双向链表，使得两者都插入到中间 O(n)容器类型。所有这些都忽略了诸如 CPU 缓存和分配器速度之类的东西，它只是比较了“简单”操作的数量。总之，您需要了解如何使用容器。如果你真的在随机位置插入/删除了很多，std::list 可能会更好。如果您很少这样做，然后只读取容器，则 std::vector 可能会更好。如果你只有十个元素，那么所有的 O(x) 都可能毫无价值，你应该选择你最喜欢的那个。
于 2013-04-25T06:25:20.347 回答
1
插入向量的中间需要将插入点之后的所有元素打乱以腾出空间，这可能涉及大量复制。
该列表被实现为一个链表，每个节点在内存中占用自己的空间并引用相邻节点，因此添加一个新节点只需要更改 2 个引用以指向新节点。
根据您使用的数据类型，向量的执行速度可能比列表快得多。但是要复制的对象越复杂，向量就越糟糕。
于 2013-04-25T01:56:40.467 回答
0
简单来说，向量就是一个数组。因此，它的元素存储在连续的内存位置（即，一个挨一个）。唯一的例外是向量允许在运行时调整大小，而不会导致数据丢失。
现在，要插入列表，您需要识别节点，然后创建新元素（内存中的任何位置），存储值并连接指针。
但是在向量（数组）的情况下，您必须物理地将元素从一个单元格移动到另一个单元格，以便为新元素创建该空间。这种物理移动是导致延迟的原因，尤其是在需要移动许多元素（即数据）的情况下。您不是在物理上移动数组元素。相反，它的内容。
于 2013-04-25T01:58:55.973 回答
0
Ulrich Eckhardt 的回答非常好。我没有足够的声誉来添加评论，所以我会自己写一个答案。就像 Ulrich 所说的那样，列表和向量在中间的插入速度在理论上都是 O(n)。在实践中，现代 CPU 有一个叫做“预取器”的东西。它非常擅长获取连续数据。由于向量在内存中是连续的，因此由于预取器，移动大量元素非常快。您需要操作非常非常大的向量，以使它们的插入速度比列表慢。有关更多详细信息，请查看这篇很棒的博客文章：
于 2017-02-02T11:57:38.590 回答