(How)
C^# You Are - 25 March 2007

This weeks questions are related to collection classes.

1. What is the difference between IList<T> and ICollection<T>?  Answer

   ICollection<T> is a generic collection of items that allows for adding and removing items from a collection.  It does not expose any functionality to access the items in a collection other than through the read-only enumerator.  You can add and remove items from the collection but you can not control where the items are inserted.  IList<T> derives from ICollection<T>and therefore has all the same characteristics as a collection but also allows for accessing the items in the collection by index and inserting and removing items by index.  This difference is fundamentally important and is the cause for a lot of confusion.

   Generally when we talk about a collection we are referring to the Collection<T> class and not the interface.  This class is not a pure collection but rather implements IList<T> as well.  Therefore when we talk about a collection as a class we generally are referring to a list of items (IList<T>) whereas when we talk about a collection interface we are referring to a collection of items without regard for how we access those items.

   This makes sense when you think about it.  Items in a dictionary are referenced by their keys.  Stacks and queues work only with the last or first item contained in them.  They are all collections but none of them are lists.  Using an index in any of these classes makes little sense as the index is meaningless.  However by treating them as collections we can still pass them around and interact with them although we can not directly access the items they contain without knowing more about the actual type.

   When designing types that will use collections you should strive to target ICollection<T> whenever possible to make your types generally usable.  You can still enumerate items within the collection using the enumerator (which all collections have) however you can not modify the collection or its contents.  IList<T> is considered an implementation detail.  Therefore only directly expose this type when you must have index-based enumeration support.

2. What is the difference between IList and ICollection (non-generic versions)?  Answer

   These are pre-v2 interfaces for collections of items.  Like the generic versions they serve different purposes.  IList derives from ICollection.  However in this case ICollection is a read-only collection of items.  The only real functionality is to get the number of items in the collection and enumerate them.  All writing comes from IList (although it supported read-only lists as well).  This is a stark change from v2 where ICollection<T> allows you to add and remove items but not directly access them.

3. What is the difference between Hashtable and HybridDictionary?  Answer

   These are pre-v2 classes that should generally be replaced by Dictionary<K,V>.  In general the HybridDictionary is the preferred class.  Internally it uses the fast ListDictionary for a small number of items and switches to the slower but more optimal Hashtable for larger number of items.  This gives you really good performance in most cases.  Unfortunately most people use Hashtable exclusively.  Hashtable is slower for small collections and faster for large collections.  Unfortunately HybridDictionary was not made generic in v2 so you must either settle for the performance of Dictionary<K,V>, write your own HybridDictionary<K,V> and support type or use the non-generic version and cast things to and from object.

4. How do you copy items in a collection to an array?  Answer

   Surprisely this requires three lines of code.

   public T[] ToArray ( ICollection<T> items )
   {
      T[] arr = new T[items.Count];
      items.CopyTo(arr, 0);
      return arr;
   }

   Personally I created an extended collection class that I use (available in the Kraken library) that exposes this very method (albeit with no parameters).  It is not thread-safe but it reduces boilerplate code down to one line.

5. How can you store AND RETRIEVE a list of items in a specific order yet still have excellent search performance?  Answer

   For the fastest searching a dictionary is needed.  However dictionaries do not store items in any usable order.  You can build your own that combines a dictionary (for searching) with a collection (for sorted access) but why bother when .NET already has a class for the job.  It is SortedList<K,V> or SortedDictionary<K,V>.  Each class provides fast searching through a dictionary but also allows sorted access.  Refer to MSDN on the difference between these two classes.

6. How are items in a dictionary found so quickly?  Answer

   As you should know by know all types inherit the GetHashCode method from Object.  It is this method that is used to store an item in a dictionary.  When you insert an item into a dictionary GetHashCode is called to get the numeric hashcode for the item.  The item is then stored in a bucket of other items with the same hashcode. 

   On lookup the item to be found has its GetHashCode method called.  The resulting hashcode is looked up in the dictionary.  If a bucket is found then a quick enumeration of the bucket contents can be used to find the desired item.  For optimal hash algorithms each hashcode maps to a single item but in reality this is really hard to accomplish.  Further discussion on hashing algorithms can be found in most academic texts.

7. How can you enumerate a collection of items while changing the contents of the list?  Answer

   You can not use the IEnumerator interface (which means you can not use a foreach statement) for this.  The interface is set up such that if the collection being enumerated changes then the next time the enumerator attempts to move to the next element it will throw an InvalidOperationException.  This is done internally by versioning the collection.  Note that insertion, removal and updating of an item in the collection changes the version and hence will cause the exception.  If you were to change the properties of an item in the collection this would not impact the collection.  In C#, however, the foreach loop treats the items as read-only so you can not even modify the item.

   To enumerate a list and change the contents at the same time you will have to resort to a standard for loop.  For example suppose you wanted to remove any string in a collection of strings that started with 'S'.  The following code would do that.  Notice that you must be careful how you manage the indice to ensure that you do not access the array outside its bounds.

   Collection names = new Collection();
   names.Add("Bobby");
   names.Add("Billy");
   names.Add("Sue");
   names.Add("John");
   names.Add("Sarah");
   names.Add("Sheila");
   names.Add("Mark");
   names.Add("Paul");
   names.Add("Sally");
   
   for (int nIdx = 0; nIdx < names.Count; ++nIdx)
   {
      if (names[nIdx].StartsWith("S", StringComparison.OrdinalIgnoreCase))
      {
         //Remove it
         names.RemoveAt(nIdx);
   
         //Adjust the index
         --nIdx;
      };
   };

   The problem I have with the above code is that there is great opportunity for error and it makes maintenance more difficult.  I feel that any code that mucks with the loop variant should be rewritten.  Fortunately some languages do not even allow it.  Memory is cheap and rarely do I care about having two copies of a list in memory at the same time.  Therefore I recommend the following approach instead.  It should work in pretty much any case that the former code would work.  I find it easier to read and understand and less error prone.  Your mileage may vary.

   Collection names = new Collection();
   names.Add("Bobby");
   names.Add("Billy");
   names.Add("Sue");
   names.Add("John");
   names.Add("Sarah");
   names.Add("Sheila");
   names.Add("Mark");
   names.Add("Paul");
   names.Add("Sally");
   
   Collection newNames = new Collection();
   for (int nIdx = 0; nIdx < names.Count; ++nIdx)
   {
      if (!names[nIdx].StartsWith("S", StringComparison.OrdinalIgnoreCase))
         newNames.Add(names[nIdx]);
   };
   
   names = newNames;

8. What is the difference between IEnumerable<T> and IEnumerator<T>?  Answer

   The IEnumerable<T> interface exposes a single method that gives you access to the IEnumerator<T> for a collection (generally).  The IEnumerator<T> interface is used to enumerate a collection of items.  It exposes methods to move to the next item, get the current item and reset the enumeration process.  Although enumerators can be defined for any type they are generally used only for collections.

9. What does the yield keyword in C# do?  Answer

   This keyword was added in C# 2.0 to allow you to create enumerators for custom collections without creating a separate class.  Prior to v2 you would write the following code in order to enumerate a collection of integers.

   public class Int32Collection : ICollection, IList
   { 
      //ICollection and IList members skipped...
   
      //Private type
      private class Int32CollectionEnumerator : IEnumerator
      {
         private Int32Collection m_Items;
         private int m_Index = -1;
   
         public Int32CollectionEnumerator ( Int32Collection items )
         { m_Items = items; }
   
         public object Current
         {
             get
             {
                 if ((m_Index < 0) || (m_Index >= m_Items.Count))
                    throw new InvalidOperationException("Index is invalid."); 
   
                 return m_Items[m_Index];
             } 
         } 
   
         public bool MoveNext ()
         {
             ++m_Index;
             return (m_Index < m_Items.Count);
         }
    
         public void Reset ()
         { m_Index = 0; } 
      } 
   
      public IEnumerator GetEnumerator () 
      { return new Int32CollectionEnumerator(this); }
   }

   The same boilerplate code has to go in each collection that you write.  In v2 you can simplify this (if you don't simply use the Collection<T> base class which already does this for you) to the following code.  It is technically usable in any block where you want to iterator over a list of items and makes up what is known as an iterator block.

   public class Int32Collection : ICollection, IList
   { 
      //ICollection and IList members skipped...
   
      public IEnumerator GetEnumerator ()
      {
         for (int nIdx = 0; nIdx < Count; ++nIdx)
            yield return m_Items[nIdx]; 
      }
   }

   Notice the private type goes away and, although the return type is IEnumerator, the value returned is actually an item in the collection.  The boilerplate code is generated for you automatically.  The code containing the yield keyword is formally known as an iterator block. Although normally only used for collections it can technically be used whenever you need to iterate over a group of items.

10. How can you print each item in a collection without manually enumerating it?  Answer

    In v2 List<T> and Array gained the methods ForEach to perform an action for each item in the collection.  Collection<T> nor the interfaces have this method.    The action is a delegate that accepts a parameter of type T and performs an operation.  If you need to pass parameters to the method then you'll need to create a class that wraps the method to be called and stored the parameters there.  Here is a quick example on how to print the contents of a list of strings.

    void Print ( string value )
    { Console.WriteLine(value); }
    
    void PrintNames ( List<string> names )
    { names.ForEach(Print); }