c# - O(1) 中的 C# IEnumerable.toArray()

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)，因为不能保证序列甚至由数组支持。当它由 支持时IList<T>，它用于IList<T>.CopyTo使事情更高效，但这是一个特定于实现的细节，仍然不会将其转换为 O(1) 操作。

Answer 2

ArrayList.toArray不是O(1)，它不只是返回其内部数组。你读过 API 规范吗？

返回的数组将是“安全的”，因为此列表不维护对它的引用。（换句话说，这个方法必须分配一个新数组）。因此，调用者可以自由修改返回的数组。

Answer 3

首先，没有要返回的数组。BlockingCollection<T>使用类型对象IProducerConsumerCollection<T>作为其内部存储，并且不能保证所使用的具体类型将由数组支持。例如，默认构造函数使用 a ConcurrentQueue<T>，它将其数据存储在数组的链表中。即使在奇怪的情况下，有一个代表集合的全部内容的数组隐藏在其中的某个地方，它也不会通过IProducerConsumerCollection<T>接口公开。

其次，即使假设首先要返回一个数组（实际上没有），这也不是一件安全的事情。如果调用代码对数组进行任何修改，它将破坏集合的内部状态。