数组vsvectorvs列表
我正在维护一个固定长度的10个条目表。 每个项目是像4个领域的结构。 将会有数字位置指定的插入，更新和删除操作。 我想知道哪个是最好的数据结构来维护这个信息表：
-
数组 – 插入/删除由于移位需要线性时间; 更新需要一定的时间; 没有空间用于指针; 使用[]访问项目更快。
-
stl向量 – 插入/删除由于移位需要线性时间; 更新需要一定的时间; 没有空间用于指针; 访问一个项目比数组慢，因为它是对operator []和一个链表的调用。
-
stl list – 插入和删除需要线性时间，因为在应用插入/删除之前需要迭代到特定位置; 指针需要额外的空间; 访问一个项目比一个数组慢，因为它是一个链表的线性遍历。
现在，我的select是使用一个数组。 这是合理的吗？ 还是我错过了什么？
哪一个更快：遍历一个列表，然后插入一个节点或将项目移动到一个数组中以产生一个空的位置，然后将该项目插入该位置？
衡量这种performance的最好方法是什么？ 我可以在操作前后显示时间戳吗？
使用STL vector 。 它提供了一个与list同样丰富的接口，并消除了pipe理arrays所需内存的痛苦。
您将不得不非常努力地暴露operator[]的性能成本 – 它通常被内联。
我没有任何号码给你，但我记得阅读性能分析，描述了vector<int>比list<int>更快，即使是插入和删除（当然在一定的大小下）。 事情的真相是，我们使用的这些处理器速度非常快 – 如果你的vector适合二级caching，那么它将会非常快速。 另一方面，列表必须pipe理会杀死L2的堆对象。
不成熟的优化是万恶之源。
根据你的文章，我会说没有理由让你select的数据结构是基于性能的。 select最方便的任何一种方法，只要性能testingcertificate这是一个问题，就会返回来改变它。
真正值得投入一些时间来理解列表和向量之间的根本区别。 两者之间最重要的区别在于它们存储元素并跟踪它们的方式。
– 列表 –
列表包含具有存储在其中的前一个和下一个元素的地址的元素。 这意味着您可以以恒定的速度O（1）在列表中的任何位置插入或删除元素，而不pipe列表大小如何。 您也可以以恒定的速度在任何位置拼接（插入另一个列表）到现有列表中。 原因是列表只需要改变我们插入到列表中的元素的两个指针（上一个和下一个）。
如果您需要随机访问，则列表不好。 所以如果打算访问列表中的第n个元素 – 一个必须逐个遍历列表 – O（n）速度
– vector –
向量包含序列中的元素，就像数组一样。 这对随机访问非常方便。 访问vector中的“nth”元素是一个简单的指针计算（O（1）速度）。 然而，向vector添加元素是不同的。 如果想要在vector的中间添加一个元素，那么在该元素之后的所有元素将不得不重新分配，以便为新条目腾出空间。 速度将取决于vector大小和新元素的位置。 最糟糕的情况是在位置2处插入一个元素，最好的方法是添加一个新的元素。 因此 – 插入速度为O（n）的作品，其中“n”是需要移动的元素的数量 – 不一定是vector的大小。
还有其他的区别涉及到内存需求等，但是理解这些列表和载体实际工作的基本原则是值得花费一些时间的。
一如既往…“ 不成熟的优化是万恶的根源 ”，所以首先考虑一下什么更方便，让事情按照你想要的方式工作，然后进行优化。 对于您提到的10个条目 – 使用什么都没有关系 – 无论您使用何种方法，都无法看到任何性能差异。
首选一个std :: vector和数组。 载体的一些优点是：
- 它们在增加大小时从自由空间分配内存。
- 他们不是伪装的指针。
- 他们可以增加/减less运行时间的大小。
- 他们可以使用at（）进行范围检查。
- 一个vector知道它的大小，所以你不需要对元素进行计数。
使用向量的最有说服力的理由是，它使您免于显式内存pipe理，并且不会泄漏内存。 vector跟踪它用来存储元素的内存。 当一个向量需要更多的元素内存时，它分配更多; 当一个向量超出范围时，它释放内存。 因此，用户不必关心向量元素的内存分配和释放。
你正在做出你不应该做的假设，比如“访问一个项目比一个数组慢，因为它是对operator []的调用”。 我可以理解它背后的逻辑，但是直到我们对其进行描述之后，我才知道。
如果你这样做，你会发现当开启优化时，根本没有开销。 编译器内联函数调用。 内存性能有所不同。 数组是静态分配的，而vector是dynamic分配的。 列表分配给每个节点，如果你不小心，可以节制caching。
一些解决scheme是从栈中分配vector ，并为list分配一个池分配器，以便节点可以放入caching。
所以，不要担心没有支持的声明，你应该担心使你的devise尽可能干净。 那么，这更有意义？ 一个数组，vector或列表？ 我不知道你在做什么，所以我不能回答你。
“默认”容器往往是一个vector 。 有时候数组也是完全可以接受的。
首先几个注意事项：
关于select数据结构的一个很好的经验法则：通常，如果您检查了所有可能性并确定数组是您的最佳select，请重新开始。 你做错了什么
STL列表不支持operator[] ，如果他们这样做的原因比编制索引数组要慢，这与函数调用的开销无关。
这些东西被说，vector是在这里明确的赢家。 对operator[]的调用实质上是可以忽略的，因为向量的内容在内存中保证是连续的。 它支持insert()和erase()操作，如果你使用了一个数组，你将自己编写自己的代码。 基本上归结为一个向量本质上是一个升级的数组已经支持所有你需要的操作。
我正在维护一个固定长度的10个条目表。 每个项目是像4个领域的结构。 将会有数字位置指定的插入，更新和删除操作。 我想知道哪个是最好的数据结构来维护这个信息表：
基于这个描述，似乎列表可能是更好的select，因为它的O（1）在数据结构的中间插入和删除。 不幸的是，当使用列表来插入和删除数组或vector时，不能使用数字位置。 这种困境导致了一系列的问题，可以用来作出哪种结构可能最适合的最初决定。 如果testing清楚地显示了错误的select，这个结构可以稍后改变。
你需要问的问题有三个。 首先是你计划在随机读取中间删除/插入的频率。 第二个是与迭代器相比使用数字位置的重要性。 最后，在你的结构中的秩序是重要的。
如果第一个问题的答案是随机读取，将会比vector/数组更为普遍。 注意，即使使用operator []表示法，遍历数据结构也不被视为随机读取。 对于第二个问题，如果你绝对需要数字位置，那么即使这可能导致性能下降，也将需要一个向量/数组。 后来的testing可能表明，相对于数字位置更容易的编码，这种性能命中可以忽略不计。 最后，如果顺序不重要，则可以使用O（1）algorithm在vector/数组中插入和删除。 示例algorithm如下所示。
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 }
