What is the cost of initializing an IEnumerable into a List/Queue/Stack?

Question

I have a collection that could potentially have millions of elements within it. However, during certain operations, this collection may be culled and then overwritten.

I would like to know the cost of creating a new data-structure using IEnumerable, for example:

IEnumerable<int> collection = /* some arbitrary collection here */

/// On average, how long will this take?
List<int> converted = new List(collection);

This will dictate whether I will cull manually (i.e. Remove, Dequeue, Pop, etc.) or by overwriting.

The way I imagine it is handled internally is that no copying is involved making this O(1) - where the beginning is the entry-point and elements are followed accordingly - but I'm not sure.

Answer 1

The constructor for List<T> in particular has specific handling for ICollection<T>

     public List(IEnumerable<T> collection)
     {
         if (collection == null)
             ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);

         if (collection is ICollection<T> c)
         {
             int count = c.Count;
             if (count == 0)
             {
                 _items = s_emptyArray;
             }
             else
             {
                 _items = new T[count];
                 c.CopyTo(_items, 0);
                 _size = count;
             }
         }
         else
         {

This calls through to here

     public void CopyTo(T[] array, int arrayIndex)
     {
         // Delegate rest of error checking to Array.Copy.
         Array.Copy(_items, 0, array, arrayIndex, _size);
     }

which is a pretty efficient native array copy.

Other collections may have different implementations, but most do have optimizations for ICollection<T> because it is possible to calculate the size.

The size of an arbitrary IEnumerable<T> is unknowable, and may not exist until all items have been enumerated.