数组、向量、列表

Question

我正在维护一个包含 10 个条目的固定长度表。每个项目都是由 4 个字段组成的结构。将有插入、更新和删除操作，由数字位置指定。我想知道哪个是用于维护此信息表的最佳数据结构：

1. 数组 - 由于移位，插入/删除需要线性时间；更新需要恒定的时间；没有空间用于指针；使用 [] 访问项目速度更快。

2. stl 向量 - 由于移位，插入/删除需要线性时间；更新需要恒定的时间；没有空间用于指针；访问项目比数组慢，因为它是对运算符 [] 和链表的调用。

3. stl list - 插入和删除需要线性时间，因为您需要在应用插入/删除之前迭代到特定位置；指针需要额外的空间；访问项目比数组慢，因为它是链表线性遍历。

现在，我的选择是使用数组。有道理吗？或者我错过了什么？

哪个更快：遍历列表，然后插入节点或移动数组中的项目以产生空位置，然后在该位置插入项目？

衡量这种性能的最佳方法是什么？我可以只显示操作前后的时间戳吗？

Answer 1

使用STL矢量。它提供了与list同样丰富的接口，并消除了管理数组所需内存的麻烦。

您必须非常努力地暴露 operator[] 的性能成本 - 它通常会被内联。

我没有任何数字可以给您，但我记得读过性能分析，其中描述了 vector 比 list 即使对于插入和删除也更快（当然在一定的尺寸下）。事实是，我们使用的这些处理器非常快 - 如果您的向量适合 L2 缓存，那么它的运行速度会非常非常快。另一方面，列表必须管理堆对象，这会杀死你的 L2。

Answer 2

过早的优化是万恶之源。

根据您的帖子，我想说没有理由让您在这里选择基于性能的数据结构。当且仅当性能测试表明这是一个问题时，选择最方便的并返回更改它。

Answer 3

确实值得花一些时间来理解列表和向量之间的根本区别。
两者之间最显着的区别是它们存储元素和跟踪元素的方式。

- 列表-

列表包含存储了上一个和下一个元素的地址的元素。这意味着无论列表大小如何，您都可以以恒定的速度 O(1) 在列表中的任何位置插入或删除元素。您还可以在任意位置以恒定速度拼接（插入另一个列表）到现有列表中。原因是列表只需要更改我们要插入列表中的元素的两个指针（前一个和下一个）。

如果您需要随机访问，列表并不好。因此，如果计划访问列表中的第 n 个元素，则必须逐个遍历列表 - O(n) 速度

- 向量 -

向量按顺序包含元素，就像数组一样。这对于随机访问来说非常方便。访问向量中的“第 n”个元素是一个简单的指针计算（速度为 O(1)）。然而，向向量添加元素是不同的。如果想要在向量中间添加一个元素，则必须重新分配该元素之后的所有元素，以便为新条目腾出空间。速度将取决于向量大小和新元素的位置。最坏的情况是在向量的位置 2 处插入一个元素，最好的情况是追加一个新元素。因此 - 插入的速度为 O(n)，其中“n”是需要移动的元素数量 - 不一定是向量的大小。

还有其他涉及内存要求等方面的差异，但是了解列表和向量实际工作原理的这些基本原理确实值得花一些时间。

一如既往……“过早的优化是万恶之源”，因此首先考虑什么更方便，让事情完全按照您想要的方式运行，然后进行优化。对于您提到的 10 个条目 - 您使用什么并不重要 - 无论您使用什么方法，您都永远无法看到任何类型的性能差异。

Answer 4

更喜欢 std::vector 而不是数组。矢量的一些优点是：

• 当大小增加时，它们从可用空间分配内存。
• 它们不是伪装的指针。
• 它们可以增加/减少运行时间的大小。
• 他们可以使用at()进行范围检查。
• 向量知道它的大小，因此您不必计算元素数。

使用向量最令人信服的原因是它使您免于显式内存管理，并且不会泄漏内存。向量会跟踪它用来存储其元素的内存。当向量需要更多内存来存储元素时，它会分配更多内存；当向量超出范围时，它会释放该内存。因此，用户无需关心向量元素的内存分配和释放。

Answer 5

您正在做出不应该做出的假设，例如“访问一个项目比数组慢，因为它是对operator[]的调用。”我可以理解其背后的逻辑，但在我们对其进行分析之前，你和我都无法知道。

如果这样做，您会发现当优化打开时根本没有任何开销。编译器内联函数调用。内存性能存在差异。数组是静态分配的，而向量是动态分配的。列表为每个节点分配，如果不小心，可能会限制缓存。

一些解决方案是让向量从堆栈中分配，并为列表提供一个池分配器，以便节点可以放入缓存中。

因此，您不必担心不受支持的声明，而应该担心使您的设计尽可能简洁。那么，哪个更有意义呢？数组、向量还是列表？我不知道你想做什么，所以无法回答你。

“默认”容器往往是一个向量。有时数组也是完全可以接受的。

Answer 6

首先是一些注意事项：

关于选择数据结构的一个好的经验法则：通常，如果您检查了所有可能性并确定数组是您的最佳选择，请重新开始。你做了一件非常错误的事。

STL 列表不支持 operator[]，如果支持，它会比索引数组慢的原因与函数调用的开销无关。

话虽这么说，矢量显然是赢家。对operator[]的调用基本上可以忽略不计，因为向量的内容保证在内存中是连续的。它支持 insert() 和 erase() 操作，如果您使用数组，您必须自己编写这些操作。基本上，它可以归结为一个事实：向量本质上是一个升级的数组，它已经支持您需要的所有操作。

Answer 7

我正在维护一个包含 10 个条目的固定长度表。每个项目都是一个
类似4个字段的结构。会有插入、更新、删除
操作，由数字位置指定。我想知道哪个是
用于维护此信息表的最佳数据结构：

根据此描述，列表似乎可能是更好的选择，因为在数据结构中间插入和删除时其 O(1)。不幸的是，当使用列表进行插入和删除时，您不能像数组/向量那样使用数字位置。这种困境导致了一系列问题，可用于初步决定哪种结构最适合使用。如果测试清楚地表明其选择是错误的，则可以稍后更改此结构。

您需要问的问题有三个。第一个是相对于随机读取，您计划在中间进行删除/插入的频率。第二个是与迭代器相比使用数字位置的重要性。最后，结构的顺序很重要。

如果第一个问题的答案是随机读取将比向量/数组更普遍，可能会工作得很好。请注意，即使使用了operator[]表示法，迭代数据结构也不被视为随机读取。对于第二个问题，如果您绝对需要数字位置，则需要向量/数组，即使这可能会导致性能下降。稍后的测试可能表明，相对于更容易的数字位置编码，这种性能影响可以忽略不计。最后，如果顺序不重要，您可以使用 O(1) 算法在向量/数组中插入和删除。下面显示了示例算法。

template <class T>
void erase(vector<T> & vect, int index) //note: vector cannot be const since you are changing vector
{
  vect[index]= vect.back();//move the item in the back to the index
  vect.pop_back(); //delete the item in the back
}

template <class T>
void insert(vector<T> & vect, int index, T value) //note: vector cannot be const since you are changing vector
{
  vect.push_back(vect[index]);//insert the item at index to the back of the vector
  vect[index] = value; //replace the item at index with value
}

Answer 8

我相信，如果需要在开始或中间使用列表中进行更多插入/删除（内部双链接），如果需要随机访问数据并添加到最后一个元素使用数组（向量具有动态分配，但如果您需要更多操作如排序、调整大小等使用向量）