Overview of the BCL Collection Types

In last month’s column, I described the fundamental concepts related to managing and enumerating a set of resources or objects. In this month’s article, I’m going to continue this discussion and show how the .NET Framework builds on the concepts presented last month to offer a consistent programming paradigm for working with collections, lists, and dictionaries.

Formal Collections

A collection is an object that manages an ordered set of items (that is, other objects). In last month’s column, we looked at how to enumerate the items of a “simple” collection. The BCL offers a formal definition of a collection, as defined by the System.Collections.ICollection interface:

public interface ICollection : IEnumerable {
 void    CopyTo(Array array, Int32 index);
 Int32   Count          { get; }
 Boolean IsSynchronized { get; }
 Object  SyncRoot       { get; }
}

All of the types in the System.Collections namespace implement the ICollections interface. These types are described briefly in the following table:

Collection Type

Description

BitArray

The BitArray type manages a compact array of 1-bit flags.

Queue

A variable-size FIFO queue of objects.

Stack

A variable-sized LIFO stack of objects.

As you can see from the ICollection interface definition shown above, any type that implements ICollection must also implement IEnumerable, which allows the collection’s items to be enumerated in the fashion discussed last month. But types that implement ICollection offer the following members, which expose additional functionality:

  • CopyTo: This method allows the user of the collection to obtain an array of the collection’s items. This is useful since it is typically easier to manipulate an array of items versus using an enumerator. This method could be helpful when constructing an enumerator.
  • Count: This read-only property returns the number of items currently in the collection. For some types, calculating the number of items may be quite time consuming. These types may choose to throw a NotSupportedException exception instead of calculating and returning the actual count. Your code should be able to handle this case gracefully.
  • IsSynchronized: This read-only property returns true if the collection type has been designed to be thread safe. If you are using a single collection object from multiple threads, and this property is false, then you must add the proper code in order to synchronize operations on this object.
  • SyncRoot: This read-only property returns the object, which can be used to manually synchronize the collection. The object returned is typically used with the C# lock statement or may be passed to System.Threading.Monitor type’s Enter and Leave methods.

Sorting a Collection’s Items

It is frequently convenient to impose an ordering between items of a collection. Of course, to impose an order there must be some mechanism that allows two items to be compared. This mechanism must indicate whether the two items are identical, whether the first item sorts before the second item, or whether the second item should sort before the first item.

When creating a type, consider implementing the System.IComparable interface:

public interface IComparable {
   int CompareTo(Object object);
}

This simple interface defines just one method, CompareTo. The purpose of this method is to compare the ‘this’ object with the specified object and return an integer indicating which object should come before the other. The table below shows what the return value means:

Return value

Meaning

A negative integer

The current object should come before the specific object

0

The objects are equal; either can come first

A positive integer

The specified object should come before the current object

The CompareTo method is designed to compare objects of the same type. If the specified object is not the same type as the current object, then an ArgumentException should be thrown. In addition, if the specified object reference is null, then a positive integer should be returned since null objects logically come before real objects. The code below demonstrates how to implement a generic CompareTo method:

public int CompareTo(Object object) {
   if (object == null) return 1;  // null sorts before current

   if (!(object is this.GetType())) {
      // object identifies a different type of object
      throw new ArgumentException();
   }

   // Compare this's value to object's value
   // and return appropriate integer
   return(nCompareToResult);
}

The IComparable interface provides a general mechanism that is not specific to collections. This is why the IComparable interface is in the System name space and not in the System.Collections name space. The CompareTo method is good when you have an object and wish to compare it to another object of the same type. On the other hand, a collection may contain objects of different types and you may wish to impose some sort order on this set of heterogeneous types. For example, consider a folder containing subfolders and files where you always want the subfolders sorted before the files.

To impose this type of sort order on a collection, the collection should implement the System.Collections.IComparer interface:

public interface IComparer {
   int Compare(Object x, Object y);
}

The Compare method is similar to the CompareTo method except that Compare takes two objects as parameters, compares these two objects with each other and returns an integer value indicating which object should come first in the sort order. The meaning of the return value is identical to CompareTo’s return value.

So now, a collection that supports the sorting of its item must implement the Compare method so that it can compare whatever object types are added to the collection. To make things easy, the base class library provides a type, System.Collections.Comparer, which offers a standard implementation of this method. The Comparer type is implemented something like this:

public sealed class Comparer : IComparer {
   // Create just one instance of this type
   public static readonly Comparer Default = new Comparer();

   // Prevent external code from creating any instance
   private Comparer() { }

   public int Compare(Object a, Object b) {
      // ASSUMPTION: objects are of same type
      if (a == b) return 0;     // a & b refer to the same object
      if (a == null) return -1; // a should come first
      if (b == null) return 1;  // b should come first

      // If a knows how to compare itself to another object,
      // return how a compares to b
      IComparable ia = a as IComparable;
      if (ia != null) return ia.CompareTo(b);

      // Maybe b knows how to compare itself to another object
      IComparable ib = b as IComparable;
      if (ib != null) return -ib.CompareTo(a);

      // Both a & b don't know how to compare themselves
      throw new ArgumentException();
   }
}

By default, a collection that supports sorting will use the Comparer object accessed via Comparer’s Default property to compare two objects. As you can see, the Comparer attempts only simple comparisons for homogeneous types. For a collection of heterogeneous types, the collection will have to implement its own IComparer interface.

For convenience, the base class library also offers another type, System.Collections.CaseInsensitiveComparer, which implements the IComparer interface. To use perform case-insensitive comparisons, you should construct a CaseInsensitiveComparer object. If you use the default constructor, it will compare strings using the thread’s current culture. However, you can explicitly specify a culture using the constructor that accepts a CultureInfo object as a parameter.

The CaseInsensitiveComparer’s Compare method basically checks if the two objects passed to it are strings. If either object is not a string, then the objects are compared using the same method as Comparer’s Compare method.

To recap, you now know how to implement an IComparable interface so that an object can compare itself to another object of the same type. You also know how an IComparer interface allows any type to compare two objects of the same or different types. You also know that the BCL offers two standard implementations of the IComparer interface: Comparer and CaseInsensitiveComparer. Both of these types rely on the object being compared as implementing the IComparable interface.

Now, let’s see how we apply all this knowledge to a collection so items are sorted the way we want them. Certain collections, such as SortedList and Hashtable, offer constructors that accept an object implementing the IComparer interface. Once constructed, these collection types use the IComparer object when any new items are added to the collection.

Some collections use a different paradigm. For example, the Array and ArrayList collections, just maintain a set of objects. At any given point, you may sort the items that are currently in the collection by calling either type’s Sort method. The Sort method has a parameter that accepts an object implementing the IComparer interface. When Sort is called, it sorts all the items in the collection using the specified IComparer object. This paradigm is more flexible than the constructor paradigm because you can sort the collection items using one IComparer object and then resort the items using a different IComparer object.

Incidentally, the Array and ArrayList types also offer BinarySearch methods that also take an IComparer object as a parameter. Before calling BinarySearch, make sure that you have called Sort using the same IComparer object or the search is sure to return unpredictable results.

Formal Lists

A list is an object that manages an ordered set of items (other objects). The base class library offers a formal definition of a list, as defined by the System.Collections.IList interface:

public interface IList : ICollection {
   Int32   Add(Object value);
   void    Clear();
   Boolean Contains(Object value);
   Int32   IndexOf(Object value);
   void    Insert(Int32 index, Object value);
   void    Remove(Object value);
   void    RemoveAt(Int32 index);
   Boolean IsFixedSize       { get; }
   Boolean IsReadOnly        { get; }
   Object  this[Int32 index] { get; set; }
}

Only a few of the types in the System.Collections namespace implement the IList interface. These types are described briefly in the following table:

List Type

Description

ArrayList

A variable-sized list of objects

StringCollection

An ArrayList strongly typed to use String objects

As you can see from the IList interface definition shown above, any type that implement IList must also implement ICollection (which also requires IEnumerable). But types that implement IList offer the following members, which expose additional functionality:

  • Add: Adds an item to the list and returns the index where the item was placed.
  • Clear: Removes all items in the list.
  • Contains: Returns true if the list contains the specified value.
  • IndexOf: Returns the index of the specified item in the list. If the item is not in the list, -1 is returned.
  • Insert: Inserts an item into the list at the specified index.
  • Remove: Removes the specified item from the list.
  • RemoveAt: Removes the item at the specified index from the list.
  • IsFixedSize property: Returns true is the list contains a fixed number of items.
  • IsReadOnly property: Returns true if the collection of items cannot change.
  • Index property: Gets or sets the value of the item at the specified index.

Formal Dictionaries

A dictionary is an object that manages a set of key-value pairs where both the keys and values are objects. The base class library offers a formal definition of a dictionary, as defined by the System.Collections.IDictionary interface:

public interface IDictionary : ICollection {
   void        Add(Object key, Object value);
   void        Clear();
   Boolean     Contains(Object key);

   // 'new' below in order to hide IEnumerable's GetEnumerator
   new IDictionaryEnumerator GetEnumerator();

   void        Remove(Object key);
   Boolean     IsFixedSize      { get; }
   Boolean     IsReadOnly       { get; }
   ICollection Keys             { get; }
   ICollection Values           { get; }
   Object      this[Object key] { get; set; }
}

Only a few of the types in the System.Collections namespace implement the IDictionary interface. These types are described briefly in the following table:

Dictionary Type

Description

Hashtable

A variable-sized collection of keys and their values
managed by the keys hash code allowing for fast lookup.

SortedList

A variable-size list of keys and their values (sorted by
key).

As you can see from the IDictionary interface definition shown above, any type that implements IDictionary must also implement ICollection and also require IEnumerable. But types that implement IDictionary offer the following members, which expose additional functionality:

  • Add: Adds a key/value pair to the dictionary.
  • Clear: Removes all items in the dictionary.
  • Contains: Returns true if the dictionary contains the specified key.
  • GetEnumerator: Returns an IDictionaryEnumerator allowing you to enumerate the individual key/value pair items in the dictionary.
  • Remove: Removes the key/value pair identified by the specified key from the dictionary.
  • IsFixedSize property: Returns true is the list contains a fixed number of items.
  • IsReadOnly property: Returns true if the collection of items cannot change.
  • Keys property: Returns a collection consisting of the dictionary’s keys.
  • Values property: Returns a collection consisting of the dictionary’s values.
  • Index property: Gets or sets the value of the item with the specific key. //

More by Author

Get the Free Newsletter!

Subscribe to Developer Insider for top news, trends & analysis

Must Read