.net 队列<T> 与列表<T>

Queue<T> vs List<T>

提问by Hyman

I'm currently using a List<T>as a queue (use lst[0]then lst.removeAt(0)) to hold objects. There's about 20 items max at a given time. I realized there was an actual Queue<T>class. I'm wondering if there's any benefit (performance, memory, etc.) to using a Queue<T>over a List<T>acting like a queue?

我目前使用 aList<T>作为队列（使用lst[0]then lst.removeAt(0)）来保存对象。在给定时间最多有大约 20 个项目。我意识到有一Queue<T>堂真正的课。我想知道使用像队列一样的Queue<T>over a是否有任何好处（性能、内存等）List<T>？

回答by Adam Houldsworth

Performance can be profiled. Though in this case of so few items, you may need to run the code millions of times to actually get worthwhile differences.

可以分析性能。尽管在这种项目很少的情况下，您可能需要运行代码数百万次才能真正获得有价值的差异。

I will say this: Queue<T>will expose your intentmore explicitly, people know how a queue works.

我会这样说：Queue<T>会更明确地暴露你的意图，人们知道队列是如何工作的。

A list being used like a queue is not as clear, especially if you have a lot of needless indexing and RemoveAt(magicNumber)code. Dequeueis a lot more consumable from a code maintenance point of view.

像队列一样使用的列表不是很清楚，尤其是当您有很多不必要的索引和RemoveAt(magicNumber)代码时。Dequeue从代码维护的角度来看，它更易消耗。

If this then gives you measurable performance issues, you can address it. Don't address every potentialperformance issue upfront.

如果这会给您带来可衡量的性能问题，您可以解决它。不要预先解决每个潜在的性能问题。

回答by nawfal

Short answer:
Queue<T>is faster than List<T>when it's used like a queue. List<T>is faster than Queue<T>when used like a list.

简短回答：
Queue<T>比List<T>像队列一样使用时更快。List<T>比Queue<T>像列表一样使用时更快。

Long answer:
A Queue<T>is faster for dequeuing operation, which is an O(1) operation. The entire block of subsequent items of the array is not moved up. This is possible because a Queue<T>need not facilitate removal from random positions, but only from the top. So it maintains a head (from which the item is pulled upon Dequeue) and tail position (to which the item is added upon Enqueue). On the other hand removing from the top of a List<T>requires itself to shift positions of every subsequent item one up. This is O(n) - worst case if you're removing from the top, which is what a dequeue operation is. The speed advantage can be noticeable if you're dequeuing in a loop.

长答案：
AQueue<T>对于出列操作更快，这是一个 O(1) 操作。数组的整个后续项目块不会向上移动。这是可能的，因为Queue<T>不需要促进从随机位置移除，而只需要从顶部移除。所以它保持一个头部（从那里拉动项目Dequeue）和尾部位置（项目被添加到其上Enqueue）。另一方面，从 a 的顶部移除List<T>需要自己将每个后续项目的位置向上移动。这是 O(n) - 如果您从顶部移除，这是最坏的情况，这就是出队操作。如果您在循环中出队，速度优势会很明显。

A List<T>is more performant if you need indexed access, random retrieval etc. A Queue<T>will have to enumerate fully to find the appropriate index position (it doesn't expose IList<T>).

一List<T>，如果你需要索引访问，随机检索等。为更好的性能Queue<T>将有枚举完全找到合适的索引位置（不公开IList<T>）。

That said, a Stack<T>vs List<T>is much closer, there is no performance difference in pushing and popping operations. They both push to end and remove from end of array structures (both of which are O(1)).

也就是说，a Stack<T>vsList<T>更接近，推送和弹出操作没有性能差异。它们都推送到数组结构的末尾和从数组结构的末尾移除（两者都是 O(1)）。

---

---

Of course you should use the correct structure that reveals the intent.In most cases they will perform better as well since they are tailor-made for the purpose. I believe had there been no performance difference at all, Microsoft wouldn't have included Queue<T>and Stack<T>in the framework for merely different semantics. It would have been simply easily extensible if that was the case. Think about SortedDictionary<K, V>and SortedList<K, V>, both of which do exactly the same but is differentiated by only performance characteristic; they find a place in BCL.

当然，您应该使用能够揭示意图的正确结构。在大多数情况下，它们的性能也会更好，因为它们是为此目的量身定制的。我相信，如果根本没有性能差异，微软不会仅仅因为不同的语义Queue<T>而将其包含Stack<T>在框架中。如果是这样的话，它会很容易扩展。想想SortedDictionary<K, V>and SortedList<K, V>，两者的作用完全相同，但仅通过性能特征来区分；他们在 BCL 找到了一席之地。

回答by Martin Liversage

Besides the fact that the Queue<T>class implements a queue and the List<T>class implement a list there is a performance difference.

除了Queue<T>类实现队列和List<T>类实现列表这一事实之外，还有性能差异。

Every time you remove the first element from List<T>all elements in the queue are copied. With only 20 elements in the queue it may not be noticeable. However, when you dequeue the next element from Queue<T>no such copying is happening and that will always be faster. If the queue is long the difference can be significant.

每次从List<T>队列中的所有元素中删除第一个元素时都会被复制。队列中只有 20 个元素时，可能不会引起注意。但是，当您从Queue<T>没有发生此类复制的情况下将下一个元素出列时，这将始终更快。如果队列很长，则差异可能很大。

回答by tradetree

I wanted to emphasize what HugoRune already pointed out. Queueis significantly faster than List, where memory accesses are 1vs. nfor Listin this use case. I have a similar use case but I have hundreds of values and I will use Queuebecause it is an order of magnitude faster.

我想强调 HugoRune 已经指出的内容。 Queue明显快于List，在此用例中，内存访问1与nfor相比List。我有一个类似的用例，但我有数百个值，我会使用Queue它，因为它快了一个数量级。

A note about Queuebeing implemented on top of List: the key word is "implemented". It doesn't copy every value to a new memory location upon dequeue, rather using a circular buffer. This can be done on "top of List" without the penalties of copies that direct usage of Listimplies.

关于Queue在之上实施的注意事项List：关键词是“实施”。它不会在出队时将每个值复制到新的内存位置，而是使用循环缓冲区。这可以在“顶部List”完成，而不会受到直接使用所List暗示的副本的惩罚。