C#IEnumerable.toArray()in O(1)

Question

我一直在玩BlockingCollection类,我想知道为什么ToArray()方法是一个O(n)操作.来自Java背景,ArrayList的ToArray()方法在O(1)中运行,因为它只返回它使用的内部数组(elementData).那么为什么在世界上他们遍历所有项目,并在IEnumerable.ToArray方法中创建一个新的数组,当他们可以覆盖它并返回集合使用的内部数组？

Answer 1

来自Java背景,ArrayList的ToArray()方法在O(1)中运行,因为它只返回它使用的内部数组(elementData).

不,它确实没有.它会创建数组的副本.来自以下文档ArrayList.toArray:

以适当的顺序(从第一个元素到最后一个元素)返回包含此列表中所有元素的数组.

返回的数组将是"安全的",因为此列表不会保留对它的引用.(换句话说,此方法必须分配一个新数组).因此调用者可以自由修改返回的数组.

所以基本上,你的问题的前提在Java意义上是有缺陷的.

现在,除此之外,Enumerable.ToArray(扩展方法IEnumerable<T>)通常是O(N),因为不能保证序列甚至可以由数组支持.当它由a支持时IList<T>,它用于IList<T>.CopyTo提高效率,但这是一个特定于实现的细节,仍然不会将其转换为O(1)操作.