C++ 数组 vs 向量 vs 列表

array vs vector vs list

提问by jasonline

I am maintaining a fixed-length table of 10 entries. Each item is a structure of like 4 fields. There will be insert, update and delete operations, specified by numeric position. I am wondering which is the best data structure to use to maintain this table of information:

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

1. array - insert/delete takes linear time due to shifting; update takes constant time; no space is used for pointers; accessing an item using [] is faster.

2. stl vector - insert/delete takes linear time due to shifting; update takes constant time; no space is used for pointers; accessing an item is slower than an array since it is a call to operator[] and a linked list .

3. stl list - insert and delete takes linear time since you need to iterate to a specific position before applying the insert/delete; additional space is needed for pointers; accessing an item is slower than an array since it is a linked list linear traversal.

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

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

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

Right now, my choice is to use an array. Is it justifiable? Or did I miss something?

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

Which is faster: traversing a list, then inserting a node or shifting items in an array to produce an empty position then inserting the item in that position?

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

What is the best way to measure this performance? Can I just display the timestamp before and after the operations?

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

回答by Frank Krueger

Use STL vector. It provides an equally rich interface as listand removes the pain of managing memory that arrays require.

使用 STLvector。它提供了一个同样丰富的接口，list并消除了管理数组所需的内存的痛苦。

You will have to try very hard to expose the performance cost of operator[]- it usually gets inlined.

您将不得不非常努力地暴露性能成本operator[]- 它通常会被内联。

I do not have any number to give you, but I remember reading performance analysis that described how vector<int>was faster than list<int>even for inserts and deletes (under a certain size of course). The truth of the matter is that these processors we use are very fast - and if your vector fits in L2 cache, then it's going to go really really fast. Lists on the other hand have to manage heap objects that will kill your L2.

我没有任何数字可以给你，但我记得读过性能分析，其中描述了甚至vector<int>比list<int>插入和删除（当然在一定大小下）还要快。事情的真相是，我们使用的这些处理器非常快——如果你的向量适合 L2 缓存，那么它会非常快。另一方面，列表必须管理会杀死 L2 的堆对象。

回答by Don Neufeld

Premature optimization is the root of all evil.

过早的优化是万恶之源。

Based on your post, I'd say there's no reason to make your choice of data structure here a performance based one. Pick whatever is most convenient and return to change it if and only if performance testing demonstrates it's a problem.

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

回答by djogon

It is really worth investing some time in understanding the fundamental differences between lists and vectors. The most significant difference between the two is the way they store elements and keep track of them.

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

- Lists -

- 列表 -

List contains elements which have the address of a previous and next element stored in them. This means that you can INSERT or DELETE an element anywhere in the list with constant speed O(1) regardless of the list size. You also splice (insert another list) into the existing list anywhere with constant speed as well. The reason is that list only needs to change two pointers (the previous and next) for the element we are inserting into the list.

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

Lists are not good if you need random access. So if one plans to access nth element in the list - one has to traverse the list one by one - O(n) speed

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

- Vectors -

- 向量 -

Vector contains elements in sequence, just like an array. This is very convenient for random access. Accessing the "nth" element in a vector is a simple pointer calculation (O(1) speed). Adding elements to a vector is, however, different. If one wants to add an element in the middle of a vector - all the elements that come after that element will have to be re allocated down to make room for the new entry. The speed will depend on the vector size and on the position of the new element. The worst case scenario is inserting an element at position 2 in a vector, the best one is appending a new element. Therefore - insert works with speed O(n), where "n" is the number of elements that need to be moved - not necessarily the size of a vector.

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

There are other differences that involve memory requirements etc., but understanding these basic principles of how lists and vectors actually work is really worth spending some time on.

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

As always ... "Premature optimization is the root of all evil" so first consider what is more convenient and make things work exactly the way you want them, then optimize. For 10 entries that you mention - it really does not matter what you use - you will never be able to see any kind of performance difference whatever method you use.

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

回答by Vijay Mathew

Prefer an std::vector over and array. Some advantages of vector are:

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

• They allocate memory from the free space when increasing in size.
• They are NOT a pointer in disguise.
• They can increase/decrease in size run-time.
• They can do range checking using at().
• A vector knows its size, so you don't have to count elements.

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

The most compelling reason to use a vector is that it frees you from explicit memory management, and it does not leak memory. A vector keeps track of the memory it uses to store its elements. When a vector needs more memory for elements, it allocates more; when a vector goes out of scope, it frees that memory. Therefore, the user need not be concerned with the allocation and deallocation of memory for vector elements.

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

回答by GManNickG

You're making assumptions you shouldn't be making, such as "accessing an item is slower than an array since it is a call to operator[]." I can understand the logic behind it, but you nor I can know until we profile it.

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

If you do, you'll find there is no overhead at all, when optimizations are turned on. The compiler inlines the function calls. There isa difference in memory performance. An array is statically allocated, while a vector dynamically allocates. A list allocates per node, which can throttle cache if you're not careful.

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

Some solutions are to have the vectorallocate from the stack, and have a pool allocator for a list, so that the nodes can fit into cache.

一些解决方案是vector从堆栈中分配，并为 a 设置一个池分配器list，以便节点可以放入缓存中。

So rather than worry about unsupported claims, you should worry about making your design as clean as possible. So, which makes more sense? An array, vector, or list? I don't know what you're trying to do so I can't answer you.

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

The "default" container tends to be a vector. Sometimes an array is perfectly acceptable too.

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

回答by Graphics Noob

First a couple of notes:

首先是几个注意事项：

A good rule of thumb about selecting data structures: Generally, if you examined all the possibilities and determined that an array is your best choice, start over. You did something very wrong.

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

STL lists don't support operator[], and if they did the reason that it would be slower than indexing an array has nothing to do with the overhead of a function call.

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

Those things being said, vector is the clear winner here. The call to operator[]is essentially negligible since the contents of a vector are guaranteed to be contiguous in memory. It supports insert()and erase()operations which you would essntially have to write yourself if you used an array. Basically it boils down to the fact that a vector is essentially an upgraded array which already supports all the operations you need.

话虽如此，vector显然是这里的赢家。对 的调用operator[]基本上可以忽略不计，因为向量的内容保证在内存中是连续的。它支持insert()与erase()你将essntially有，如果你使用一个数组来写自己的操作。基本上它归结为这样一个事实，即向量本质上是一个升级的数组，它已经支持您需要的所有操作。

回答by Zachary Kraus

I am maintaining a fixed-length table of 10 entries. Each item is a structure of like 4 fields. There will be insert, update and delete operations, specified by numeric position. I am wondering which is the best data structure to use to maintain this table of information:

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

Based on this description it seems like list might be the better choice since its O(1) when inserting and deleting in the middle of the data structure. Unfortunately you cannot use numeric positions when using lists to do inserts and deletes like you can for arrays/vectors. This dilemma leads to a slew of questions which can be used to make an initial decision of which structure may be best to use. This structure can later be changed if testing clearly shows its the wrong choice.

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

The questions you need to ask are three fold. The first is how often are you planning on doing deletes/inserts in the middle relative to random reads. The second is how important is using a numeric position compared to an iterator. Finally, is order in your structure important.

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

If the answer to the first question is random reads will be more prevalent than a vector/array will probably work well. Note iterating through a data structure is not considered a random read even if the operator[] notation is used. For the second question, if you absolutely require numeric position than a vector/array will be required even though this may lead to a performance hit. Later testing may show this performance hit is negligible relative to the easier coding with numerical positions. Finally if order is unimportant you can insert and delete in a vector/array with an O(1) algorithm. A sample algorithm is shown below.

如果第一个问题的答案是随机读取将比向量/数组更普遍。请注意，即使使用 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
}