7.3 Predefined Collection Classes

The FCL provides a reasonably comprehensive set of prebuilt data structures providing concrete implementations of all the interfaces described in this chapter. However, since C# does not yet support generics, the implementations work in terms of the generic object type, which has the same disadvantages (excessive casting, boxing) as the generic IEnumerator interface described earlier. If you prefer more type-safe collection classes, you may use one of these predefined types as a starting point for your own type-safe variant.

7.3.1 The Array Class

The Array class is the canonical aggregate data structure in the FCL, representing a fixed-size array of object references of uniform type. Since the Array data structure is fundamental, the C# language provides explicit array declaration and initialization syntax (for more details, see Chapter 2 and Chapter 3). The storage for the array is allocated on the GC heap at the time a class is instantiated, and cannot change (see the ArrayList class for a growable array-like data structure). The Array class implements ICollection, IList, and IEnumerable, so arrays can be treated as lists, generic cloneable collections, or sets of elements that can be enumerated. In addition, the Array class supports sorting and searching of the array. Sorting of the array is often accomplished by delegating to IComparable implementations on the contained elements, which requires that you implement IComparable on types that are intended for use in arrays that need to be sorted. The following is an example of using the Array class:

string[ ] strs1 = { "time", "the", "now", "is" };
Array strs2 = Array.CreateInstance(typeof(string), 4);
strs2.SetValue("for", 0);
strs2.SetValue("all", 1);
strs2.SetValue("good", 2);
strs2.SetValue("men", 3);
Array strings = Array.CreateInstance(typeof(string), 8);
Array.Copy(strs1, strings, 4);
strs2.CopyTo(strings, 4);
foreach (string s in strings)

7.3.2 The ArrayList Class

The ArrayList class provides a dynamically sized array of objects that implements the IList interface. An ArrayList works by maintaining an internal array of objects that is replaced with a larger array when it reaches its capacity of elements. It is very efficient at adding elements (since there is usually a free slot at the end), but is inefficient at inserting elements (since all elements have to be shifted to make a free slot). Searching can be efficient if the BinarySearch( ) method is used on an ArrayList that has been sorted, but is otherwise inefficient as it requires that each item is checked individually. The following is an example of using the ArrayList class:

ArrayList a = new ArrayList( );
a.Sort( );
for (int i = 0; i < a.Count; i++)

7.3.3 The Hashtable Class

A Hashtable is a standard dictionary (key/value) data structure that uses a hashing algorithm to store and index values efficiently. This hashing algorithm is performed using the hashcode returned by the GetHashCode( ) method on System.Object. Types stored in a Hashtable should therefore override GetHashCode( ) to return a good hash of the object's internal value. Hashtable also implements the IDictionary interface, and therefore can also be manipulated as a normal dictionary data structure. The following is an example of using the Hashtable class:

Hashtable ht = new Hashtable( );
ht["One"] = 1;
ht["Two"] = 2;
ht["Three"] = 3;
Console.WriteLine(ht["Two"]); // Prints "2"

7.3.4 The Queue Class

A Queue is a standard first-in first-out (FIFO) data structure, providing simple operations to enqueue, dequeue, peek at the element at the top of the queue, etc. The following is an example of using the Queue class:

Queue q = new Queue( );
Console.WriteLine(q.Dequeue( )); // Prints "1"
Console.WriteLine(q.Dequeue( )); // Prints "2"

7.3.5 The Stack Class

A Stack is a standard last-in first-out (LIFO) data structure, providing simple operations to Push and Pop elements on and off the stack. The following is an example of using the Stack class:

Stack s = new Stack( );
s.Push(1); // Stack = 1
s.Push(2); // Stack = 1,2
s.Push(3); // Stack = 1,2,3
Console.WriteLine(s.Pop( )); // Prints 3, Stack=1,2
Console.WriteLine(s.Pop( )); // Prints 2, Stack=1
Console.WriteLine(s.Pop( )); // Prints 1, Stack=

7.3.6 The BitArray Class

A BitArray is a dynamically sized array of bool values. It is more memory-efficient than a simple array of bools, because it uses only one bit for each value, whereas a bool array uses one byte for each value. The following is an example of using the BitArray class:

BitArray bits = new BitArray( );
bits.Length = 2;
bits[1] = true;
bits.Xor(bits); // Xor the array with itself

7.3.7 The SortedList Class

A SortedList is a standard dictionary data structure that uses a binary-chop search to index efficiently. SortedList implements the IDictionary interface and is manipulated like any other dictionary data structure. SortedList also implements the ICollection and IEnumerable interfaces. The following is an example of using a SortedList:

SortedList s = new SortedList( );
s["Zebra"] = 1;
s["Antelope"] = 2;
s["Eland"] = 3;
s["Giraffe"] = 4;
s["Meerkat"] = 5;
s["Dassie"] = 6;
s["Tokoloshe"] = 7;
Console.WriteLine(s["Meerkat"]); // Prints "5" in 3 lookups

7.3.8 The StringCollection Class

The StringCollection class is a standard collection data structure for storing strings. StringCollection implements the ICollection interface and can be manipulated like any other collection data structure. The following is an example of using a StringCollection:

StringCollection sc = new StringCollection( );
string[ ] sarr =  {"s2", "s3", "s4"};
foreach (string s in sc)
  Console.Write("{0} ", s); // s1 s2 s3 s4

7.3.9 The StringDictionary Class

The StringDictionary class is a dictionary data structure for storing key/value pairs in which the type of the key is a string. This class offers very similar methods to the Hashtable class, although the only standard interface it implements is IEnumerable. The following is an example of using a StringDictionary:

StringDictionary sd = new StringDictionary( );
sd["One"] = 1;
sd["Two"] = 2;
sd["Three"] = 3;
Console.WriteLine(sd["Two"]); // Prints "2"

    Part II: Programming with the .NET Framework
    Part IV: API Quick Reference