C# 可以快速调整大小的数组
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/413618/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Array that can be resized fast
提问by TheFlash
I'm looking for a kind of array data-type that can easily have items added, without a performance hit.
我正在寻找一种可以轻松添加项目而不会影响性能的数组数据类型。
- System.Array-
Redim Preservecopies entire RAM from old to new, as slow as amount of existing elements - System.Collections.ArrayList- good enough?
- System.Collections.IList- good enough?
- 系统。数组- 将
Redim Preserve整个 RAM 从旧的复制到新的，与现有元素的数量一样慢 - 系统。集合。ArrayList- 够好吗？
- 系统。集合。IList- 够好吗？
采纳答案by Juliet
Just to summarize a few data structures:
简单总结一下几个数据结构：
System.Collections.ArrayList: untyped data structures are obsolete. Use List(of t) instead.
System.Collections.ArrayList：无类型数据结构已过时。使用 List(of t) 代替。
System.Collections.Generic.List(of t): this represents a resizable array. This data structure uses an internal array behind the scenes. Adding items to List is O(1) as long as the underlying array hasn't been filled, otherwise its O(n+1) to resize the internal array and copy the elements over.
System.Collections.Generic.List(of t)：这代表一个可调整大小的数组。这个数据结构在幕后使用了一个内部数组。只要底层数组没有被填充，向 List 添加项目是 O(1)，否则它的 O(n+1) 来调整内部数组的大小并复制元素。
List<int> nums = new List<int>(3); // creates a resizable array
// which can hold 3 elements
nums.Add(1);
// adds item in O(1). nums.Capacity = 3, nums.Count = 1
nums.Add(2);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3
nums.Add(3);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3
nums.Add(4);
// adds item in O(n). Lists doubles the size of our internal array, so
// nums.Capacity = 6, nums.count = 4
Adding items is only efficient when adding to the back of the list. Inserting in the middle forces the array to shift all items forward, which is an O(n) operation. Deleting items is also O(n), since the array needs to shift items backward.
添加项目仅在添加到列表后面时才有效。在中间插入会强制数组向前移动所有项目，这是一个 O(n) 操作。删除项目也是 O(n)，因为数组需要向后移动项目。
System.Collections.Generic.LinkedList(of t): if you don't need random or indexed access to items in your list, for example you only plan to add items and iterate from first to last, then a LinkedList is your friend. Inserts and removals are O(1), lookup is O(n).
System.Collections.Generic.LinkedList(of t)：如果您不需要随机或索引访问列表中的项目，例如您只计划添加项目并从头到尾迭代，那么 LinkedList 就是您的朋友。插入和删除是 O(1)，查找是 O(n)。
回答by Mats Fredriksson
You should use the Generic List<> (System.Collections.Generic.List) for this. It operates in constant amortized time.
为此，您应该使用 Generic List<> ( System.Collections.Generic.List)。它以固定的摊销时间运行。
It also shares the following features with Arrays.
它还与数组共享以下功能。
- Fast random access (you can access any element in the list in O(1))
- It's quick to loop over
- Slow to insert and remove objects in the start or middle (since it has to do a copy of the entire listbelieve)
- 快速随机访问（你可以在 O(1) 中访问列表中的任何元素）
- 循环很快
- 在开始或中间插入和删除对象很慢（因为它必须复制整个列表相信）
If you need quick insertions and deletions in the beginning or end, use either linked-list or queues
如果您需要在开头或结尾快速插入和删除，请使用链表或队列
回答by BenAlabaster
Would the LinkedList< T> structure work for you? It's not (in some cases) as intuitive as a straight array, but is very quick.
LinkedList< T> 结构对你有用吗？它（在某些情况下）不像直阵列那样直观，但速度非常快。
- AddLast to append to the end
- AddBefore/AddAfter to insert into list
- AddFirst to append to the beginning
- AddLast 追加到最后
- AddBefore/AddAfter 插入列表
- AddFirst 追加到开头
It's not so quick for random access however, as you have to iterate over the structure to access your items... however, it has .ToList() and .ToArray() methods to grab a copy of the structure in list/array form so for read access, you could do that in a pinch. The performance increase of the inserts may outweigh the performance decrease of the need for random access or it may not. It will depend entirely on your situation.
然而，随机访问并不是那么快，因为你必须遍历结构来访问你的项目......但是，它有 .ToList() 和 .ToArray() 方法来获取列表/数组形式的结构副本所以对于读取访问，你可以在紧要关头做到这一点。插入的性能提升可能会超过随机访问需求的性能下降，也可能不会。这将完全取决于您的情况。
There's also this reference which will help you decide which is the right way to go:
还有这个参考资料可以帮助您确定正确的方法：
回答by Michael Borgwardt
What is "good enough" for you? What exactly do you want to do with that data structure?
对你来说什么是“足够好”？你到底想用那个数据结构做什么？
No array structure (i.e. O(n) access) allows insertion in the middle without an O(n) runtime; insertion at the end is O(n) worst case an O(1) amortized for self-resizing arrays like ArrayList.
没有数组结构（即 O(n) 访问）允许在没有 O(n) 运行时间的情况下插入中间；最后的插入是 O(n) 最坏的情况，O(1) 对于像 ArrayList 这样的自调整大小的数组进行摊销。
Maybe hashtables (amortized O(1) access and insertion anywhere, but O(n) worst case for insertion) or trees (O(log(n)) for access and insertion anywhere, guaranteed) are better suited.
也许哈希表（摊销 O(1) 访问和插入任何地方，但 O(n) 最坏情况下插入）或树（O(log(n)) 访问和插入任何地方，保证）更适合。
回答by Bill K
If speed is your problem, I don't see how the selected answer is any better than using a raw Array, although it resizes itself, it uses the exact same mechanism you would use to resize an array (and should take just a touch longer) UNLESS you are always adding to the end, in which case it should do things a bit smarter because it allocates a chunk at a time instead of just one element.
如果速度是你的问题，我看不出所选择的答案比使用原始数组更好，尽管它会自行调整大小，但它使用与调整数组大小完全相同的机制（并且应该只需要稍微触摸一下) 除非你总是添加到最后，在这种情况下它应该做的事情更聪明一点，因为它一次分配一个块而不是一个元素。
If you often add near the beginning/middle of your collection and don't index into the middle/end very often, you probably want a Linked List. That will have the fastest insert time and will have great iteration time, it just sucks at indexing (such as looking at the 3rd element from the end, or the 72nd element).
如果您经常在集合的开头/中间添加内容并且不经常索引到中间/结尾，则您可能需要链接列表。这将具有最快的插入时间并且将有很好的迭代时间，它只是在索引方面很糟糕（例如从末尾查看第 3 个元素，或第 72 个元素）。
