Most lightweight .NET collection

Question

I wonder, what are the differences in collection implementations in .NET .

For instance, I constantly use List<int> etc to store a list of items. However I just need a container for items, and I guess I don't need all the features that List have. I just need an container that has put method, and will enable client code to iterate over the container.

Are there any quicker, more lightweight collection implementations that implement IEnumerable<T> in .NET?

Answer 1

The most lightweight container which implements IEnumerable<T> is a typed array. It has no Add method (and therefore does not dynamically resize like a list does) but if you know what number of elements you want up front you can define the array and insert elements at a given position.

var myArray = new int[10];
myArray[0] = 123;
myArray[1] = 234;

Answer 2

If you only need add and iteration I would believe that a linked list to be the most light weight. I haven't looked at the implementation of Stack put it's rather easy to create one that doesn't take to much space. It's a rather naïve solution that could be optimized for size. My point is that it's simple to implement a leightweight collection

public class Stack<T>{
   readonly T _head;
   readonly Stack<T> _tail;
   public Stack(T head,Stack<T> tail){
       _head = head;
       _tail = tail;
   }

   public Stack<T> Push(T element){
       return new Stack<T>(element,this);
   }

   public IEnumerator<T> GetEnumerator(){
         yield return _head;
         var current = _tail;
         while(_tail != null){
             yield return current._head;
             current = current._tail;
         }
   }
}

Performancewise this will be slower than an implementation that uses a preallocated array since assigning to an element is faster than newing a new object and depending on how filled the internal array of eg. list is this might actually take up more space but that overhead can be traded for performance by newing a new array each time with just one more element but that has a significant overhead performancewise. You could also opt for a balance between the two where you keep sufficient space for a number of new elements overallocaating memory in most cases but increasing performance in most cases.

public class Stack<T>{
   T[] _heads;
   T[] _tail;
   int _next;
   public Stack(T head,T[] tail){
       _heads = new T[tail.length];
       _next = _heads.Length -2; 
       _heads[_heads.Length -1] = head;
       _tail = tail;
   }

   public void Push(T element){
        if(_next < 0){
            var length = _heads.Length;
            var _new = new T[length * 2];
            _heads = new T[length * 2];                
            _next = length * 2-1;
            Array.Copy(_heads,_new,length);
            Array.Copy(_tails,0,_new,length,length);
            _tails = _new;
        } else{
            _heads[_next--] = element;
        }
   }

   public IEnumerator<T> GetEnumerator(){
         yield return _head;
         var current = _tail;
         while(_tail != null){
             yield return current._head;
             current = current._tail;
         }
   }
}

and the you are basically back to the balance that collection such as List have. It's build on an internal array which is often too big to allow for high speed additions while not wasting too much memory.

So as with all optimization questions it really depends on what you wish to optimize for. You can often optimize for memory if you are willing to sacrifice performance and vice versa

Answer 3

What exactly are you storing in the collection? If it's a type (T), then List<T> is your best bet yes.

For non-generic types, consider using a HashSet, they can significantly improve performance in certain cases.

AS @RuneFS said, as you are asking for iteration and put. Iterating a HashSet is equal(ish) to iterating List however adding an object to HashSet is slower (comparing hashes) than adding it to a list and functionaly not equivalent either (distinct hashes in hashset).