Skip to content

Collections

by Alex Peck on September 16th, 2009

The overarching design of System.Collections is obscured by the poorly conceived nomenclature (others concur). Concrete collections in .NET are based on these key interfaces:

  • IEnumerable simply provides a method to return an IEnumerator. IEnumerator provides the mechanism for forward only iteration.
  • ICollection extends IEnumerable adding some basic machinery for thread safe access and a Count property. Note that ICollection does not provide any way of adding/removing elements.
  • IList extends ICollection to support indexing and the facility to add and remove elements. ILists can be fixed size and/or read only.
  • IDictionary extends ICollection to support key value pairs. Values may be added, retrieved and removed by key. Both the keys and the values can be retreived as ICollections. IDictionarys can be fixed size and/or read only.

ArrayList : IList

ArrayList provides an IList interface over an array which is dynamically resized as you insert elements. Iterating over an ArrayList returns items in the order they were inserted (unless it has been sorted).

The following snippet demonstrates adding, inserting and removing elements and ranges of elements.

ArrayList al = new ArrayList();
al.Add("this");
 
// Add range requires an ICollection arg
string [] strs = { "is", "a", "list" };
al.AddRange(strs);
 
al.Insert(0, "hello");
 
string[] more = { "non", "sense" };
al.InsertRange(1, more);
 
al.RemoveAt(0);
al.RemoveRange(1, 2);

Note that runtime performance is similar to what you might expect if manipulating a raw array. For example, in the worst case, InsertRange is an O(m + n) operation, where n is the number of elements to be added and m is the number of elements in the ArrayList.

Casting and boxing

System.Collections classes come from a time before .NET generics. As a consequence, collection elements are objects – everything is cast to/from object as it is stored/retrieved. Value types also get boxed/uboxed. This is all additional overhead.

Contary to what it says in the Framework Foundation book, generics are *sometimes* faster because they avoid this casting and boxing (depending on your use case). Rico Mariani has an interesting performance comparison (the real killer is the repeated allocation of the ArrayList Enumerator).

No comments yet

Leave a Reply

Note: XHTML is allowed. Your email address will never be published.

Subscribe to this comment feed via RSS