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

Question

I have been playing around with the BlockingCollection class, and I was wondering why the ToArray() Method is an O(n) operation. Coming from a Java background, the ArrayList's ToArray() method runs in O(1), because it just returns the internal array it uses (elementData). So why in the world do they iterate through all of the items, and create a new Array in the IEnumerable.ToArray method, when they could just override it and return the internal array the collection uses?

Answer 1

Coming from a Java background, the ArrayList's ToArray() method runs in O(1), because it just returns the internal array it uses (elementData).

No, it really doesn't. It creates a copy of the array. From the docs for ArrayList.toArray:

Returns an array containing all of the elements in this list in proper sequence (from first to last element).

The returned array will be "safe" in that no references to it are maintained by this list. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array.

So basically, the premise of your question is flawed in the Java sense.

Now, beyond that, Enumerable.ToArray (the extension method on IEnumerable<T>) in general would be O(N), as there's no guarantee that the sequence is even backed by an array. When it's backed by an IList<T>, it uses IList<T>.CopyTo to make things more efficient, but this is an implementation-specific detail and still doesn't transform it into an O(1) operation.

Answer 2

ArrayList.toArray is not O(1), and it does not just return its internal array. Did you read the API specification?

The returned array will be "safe" in that no references to it are maintained by this list. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array.

Answer 3

First, there's no array to return. BlockingCollection<T> uses an object of type IProducerConsumerCollection<T> for its internal storage, and there's no guarantee that the concrete type being used will be backed by an array. For example the default constructor uses a ConcurrentQueue<T>, which stores its data in a linked list of arrays. Even in the odd case where there is an array which represents the full contents of the collection hiding somewhere in there it won't be exposed through the IProducerConsumerCollection<T> interface.

Second, even assuming there were an array to be returned in the first place (which there isn't), it wouldn't be a safe thing to do. If the calling code made any modifications to the array it would corrupt the internal state of the collection.