The Non-Generic Collections
The non-generic collections have been part of C# since version 1.0. They are defined in the System.Collections namespace. The non-generic collections are general-purpose data structures that operate on object references. Thus, they can manage any type of object, but not in a type-safe manner. This is both their advantage and disadvantage. Because they operate on object references, you can mix various types of data within the same collection. This makes them useful in situations in which you need to manage a collection of different type objects, or when the type of objects being stored is not known in advance. However, if you intend a collection to store a specific type of object, then the non-generic collections do not have the type-safety that is found in the generic collections.
The non-generic collections are defined by a set of interfaces and by the classes that implement those interfaces. Each is described by the following sections.
The Non-Generic Interfaces
System.Collections defines a number of non-generic interfaces. It is necessary to begin with the collection interfaces because they determine the functionality common to all of the non-generic collection classes. The interfaces that underpin non-generic collections are summarized in Table 23-1. The following sections examine each interface in detail.
| Interface | Description |
|---|---|
| ICollection | Defines the elements that all non-generic collections must have. |
| IComparer | Defines the Compare( ) method that performs a comparison on objects stored in a collection. |
| IDictionary | Defines a collection that consists of key/value pairs. |
| IDictionaryEnumerator | Defines the enumerator for a collection that implements IDictionary. |
| IEnumerable | Defines the GetEnumerator( ) method, which supplies the enumerator for a collection class. |
| IEnumerator | Provides methods that enable the contents of a collection to be obtained one at a time. |
| IEqualityComparer | Compares two objects for equality. (Added by C# 2.0.) |
| IHashCodeProvider | Declared obsolete by C# 2.0. Use IEqualityComparer instead. |
| IList | Defines a collection that can be accessed via an indexer. |
The ICollection Interface
The ICollection interface is the foundation upon which all non-generic collections are built. It declares the core methods and properties that all non-generic collections will have. It also inherits the IEnumerable interface.
ICollection defines the following properties:
| Property | Meaning |
|---|---|
| int Count { get; } | The number of items currently held in the collection. |
| bool IsSynchronized { get; } | Is true if the collection is synchronized and false if it is not. By default, collections are not synchronized. It is possible, though, to obtain a synchronized version of most collections. |
| object SyncRoot { get; } | An object upon which the collection can be synchronized. |
Count is the most often used property because it contains the number of elements currently held in a collection. If Count is zero, then the collection is empty.
ICollection defines the following method:
void CopyTo(Array target, int startIdx)
CopyTo( ) copies the contents of a collection to the array specified by target, beginning at the index specified by startIdx. Thus, CopyTo( ) provides a pathway from a collection to a standard C# array.
Since ICollection inherits IEnumerable, it also includes the sole method defined by IEnumerable, that is, GetEnumerator( ), which is shown here:
IEnumerator GetEnumerator( )
It returns the enumerator for the collection.
The IList Interface
The IList interface declares the behavior of a non-generic collection that allows elements to be accessed via a zero-based index. It inherits ICollection and IEnumerable. In addition to the methods defined by ICollection and IEnumerable, IList defines several of its own. These are summarized in Table 23-2. Several of these methods imply the modification of a collection. If the collection is read-only or of fixed size, then these methods will throw a NotSupportedException.
| Method | Description |
|---|---|
| int Add(object obj) | Adds obj into the invoking collection. Returns the index at which the object is stored. |
| void Clear( ) | Deletes all elements from the invoking collection. |
| bool Contains(object obj) | Returns true if the invoking collection contains the object passed in obj. Returns false if obj is not in the collection. |
| int IndexOf(object obj) | Returns the index of obj if obj is contained within the invoking collection. If obj is not found, −1 is returned. |
| void Insert(int idx, object obj) | Inserts obj at the index specified by idx. Elements at and below idx are moved down to make room for obj. |
| void Remove(object obj) | Removes the first occurrence of obj from the invoking collection. Elements at and below the removed element are moved up to close the gap. |
| void RemoveAt(int idx) | Removes the object at the index specified by idx from the invoking collection. Elements at and below idx are moved up to close the gap. |
Objects are added to an IList collection by calling Add( ). Notice that Add( ) takes an argument of type object. Since object is a base class for all types, any type of object can be stored in a non-generic collection. This includes the value types, because boxing and unboxing will automatically take place.
You can remove an element using Remove( ) or RemoveAt( ). Remove( ) removes the specified object. RemoveAt( ) removes the object at a specified index. To empty the collection, call Clear( ).
You can determine whether a collection contains a specific object by calling Contains( ). You can obtain the index of an object by calling IndexOf( ). You can insert an element at a specific index by calling Insert( ).
IList defines the following properties:
bool IsFixedSize { get; } bool IsReadOnly { get; } If the collection is of fixed size, IsFixedSize is true. This means that elements cannot be inserted or removed. If the collection is read-only, then IsReadOnly is true. This means the contents of the collection cannot be changed.
IList defines the following indexer:
object this[int idx] { get; set; } You will use this indexer to get or set the value of an element. However, you cannot use it to add a new element to the collection. To add an element to a list, call Add( ). Once it is added, you can access the element through the indexer.
The IDictionary Interface
The IDictionary interface defines the behavior of a non-generic collection that maps unique keys to values. A key is an object that you use to retrieve a value at a later date. Thus, a collection that implements IDictionary stores key/value pairs. Once the pair is stored, you can retrieve it by using its key. IDictionary inherits ICollection and IEnumerable. The methods declared by IDictionary are summarized in Table 23-3. Several methods throw an ArgumentNullException if an attempt is made to specify a null key.
| Method | Description |
|---|---|
| void Add(object k, object v) | Adds the key/value pair specified by k and v to the invoking collection. k must not be null. |
| void Clear( ) | Removes all key/value pairs from the invoking collection. |
| bool Contains(object k) | Returns true if the invoking collection contains k as a key. Otherwise, returns false. |
| IDictionaryEnumerator GetEnumerator( ) | Returns the enumerator for the invoking collection. |
| void Remove(object k) | Removes the entry whose key equals k. |
To add a key/value pair to an IDictionary collection, use Add( ). Notice that the key and its value are specified separately. To remove an element, specify the key of the object in a call to Remove( ). To empty the collection, call Clear( ).
You can determine whether a collection contains a specific object by calling Contains( ) with the key of the desired item. GetEnumerator( ) obtains an enumerator compatible with an IDictionary collection. This enumerator operates on key/value pairs.
IDictionary defines the following properties:
| Property | Description |
|---|---|
| bool IsFixedSize { get; } | Is true if the dictionary is of fixed size. |
| bool IsReadOnly { get; } | Is true if the dictionary is read-only. |
| ICollection Keys { get; } | Obtains a collection of the keys. |
| ICollection Values { get; } | Obtains a collection of the values. |
Notice that the keys and values contained within the collection are available as separate lists through the Keys and Values properties.
IDictionary defines the following indexer:
object this[object key] { get; set; } You can use this indexer to get or set the value of an element. You can also use it to add a new element to the collection. Notice that the “index” is not actually an index, but rather the key of the item.
IEnumerable, IEnumerator, and IDictionaryEnumerator
IEnumerable is the non-generic interface that a class must implement if it is to support enumerators. As explained, all of the non-generic collection classes implement IEnumerable because it is inherited by ICollection. The sole method defined by IEnumerable is GetEnumerator( ), which is shown here:
IEnumerator GetEnumerator( )
It returns the enumerator for the collection. Also, implementing IEnumerable allows the contents of a collection to be obtained by a foreach loop.
IEnumerator is the interface that defines the functionality of an enumerator. Using its methods, you can cycle through the contents of a collection. For collections that store key/ value pairs (dictionaries), GetEnumerator( ) returns an object of type IDictionaryEnumerator, rather than IEnumerator. IDictionaryEnumerator inherits IEnumerator and adds functionality to facilitate the enumeration of dictionaries.
The methods defined by IEnumerator and the techniques needed to use it are described later in this chapter.
IComparer and IEqualityComparer
The IComparer interface defines a method called Compare( ), which defines the way two objects are compared. It is shown here:
int Compare(object v1, object v2)
It must return greater than zero if v1 is greater than v2, less than zero if v1 is less than v2, and zero if the two values are the same. This interface can be used to specify how the elements of a collection should be sorted.
The IEqualityComparer interface was added by C# 2.0. IEqualityComparer defines these two methods:
bool Equals(object obj1, object obj2) int GetHashCode(object obj)
Equals( ) must return true if obj1 and obj2 are equal. GetHashCode( ) must return the hash code for obj.
The DictionaryEntry Structure
System.Collections defines one structure type called DictionaryEntry. Non-generic collections that hold key/value pairs store those pairs in a DictionaryEntry object. This structure defines the following two properties:
public object Key { get; set; } public object Value { get; set; } These properties are used to access the key or value associated with an entry. You can construct a DictionaryEntry object by using the following constructor:
public DictionaryEntry(object k, object v)
Here, k is the key and v is the value.
The Non-Generic Collection Classes
Now that you are familiar with the non-generic collection interfaces, we can examine the standard classes that implement them. With the exception of BitArray, described later, the non-generic collection classes are summarized here:
| Class | Description |
|---|---|
| ArrayList | A dynamic array. This is an array that can grow as needed. |
| Hashtable | A hash table for key/value pairs. |
| Queue | A first-in, first-out list. |
| SortedList | A sorted list of key/value pairs. |
| Stack | A first-in, last-out list. |
The following sections examine these collection classes and illustrate their use.
ArrayList
The ArrayList class supports dynamic arrays, which can grow or shrink as needed. In C#, standard arrays are of a fixed length, which cannot be changed during program execution. This means that you must know in advance how many elements an array will hold. But sometimes you may not know until runtime precisely how large an array you will need. To handle this situation, use ArrayList. An ArrayList is a variable-length array of object references that can dynamically increase or decrease in size. An ArrayList is created with an initial size. When this size is exceeded, the collection is automatically enlarged. When objects are removed, the array can be shrunk. ArrayList is currently in wide use in existing code. For these reasons it is examined in depth here. However, many of the same techniques that apply to ArrayList apply to the other collections as well, including the generic collections.
ArrayList implements ICollection, IList, IEnumerable, and ICloneable. ArrayList has the constructors shown here:
public ArrayList( ) public ArrayList(ICollection c) public ArrayList(int capacity)
The first constructor builds an empty ArrayList with an initial capacity of 0. The second constructor builds an ArrayList that is initialized with the elements specified by c and has an initial capacity equal to the number of elements. The third constructor builds an array list that has the specified initial capacity. The capacity is the size of the underlying array that is used to store the elements. The capacity grows automatically as elements are added to an ArrayList.
In addition to the methods defined by the interfaces that it implements, ArrayList defines several methods of its own. Some of the more commonly used ones are shown in Table 23-4. An ArrayList can be sorted by calling Sort( ). Once sorted, it can be efficiently searched by BinarySearch( ). The contents of an ArrayList can be reversed by calling Reverse( ).
| Method | Description |
|---|---|
| public virtual void AddRange(ICollection c) | Adds the elements in c to the end of the invoking ArrayList. |
| public virtual int BinarySearch(object v) | Searches the invoking collection for the value passed in v. The index of the matching element is returned. If the value is not found, a negative value is returned. The invoking list must be sorted. |
| public virtual int BinarySearch(object v, IComparer comp) | Searches the invoking collection for the value passed in v using the comparison object specified by comp. The index of the matching element is returned. If the value is not found, a negative value is returned. The invoking list must be sorted. |
| public virtual int BinarySearch(int startIdx, int count, object v, IComparer comp) | Searches the invoking collection for the value passed in v using the comparison object specified by comp. The search begins at startIdx and runs for count elements. The index of the matching element is returned. If the value is not found, a negative value is returned. The invoking list must be sorted. |
| public virtual void CopyTo(Array ar) | Copies the contents of the invoking collection to the array specified by ar, which must be a one-dimensional array compatible with the type of the elements in the collection. |
| public virtual void CopyTo(Array ar, int startIdx) | Copies the contents of the invoking collection to the array specified by ar, beginning at startIdx. The array must be a one-dimensional array compatible with the type of the elements in the collection. |
| public virtual void CopyTo(int srcIdx, Array ar, int destIdx, int count) | Copies a portion of the invoking collection, beginning at srcIdx and running for count elements, to the array specified by ar, beginning at destIdx. ar must be a one-dimensional array compatible with the type of the elements in the collection. |
| public static ArrayList FixedSize(ArrayList ar) | Wraps ar in a fixed-size ArrayList and returns the result. |
| public virtual ArrayList GetRange(int idx, int count) | Returns a portion of the invoking ArrayList. The range returned begins at idx and runs for count elements. The returned object refers to the same elements as the invoking object. |
| public virtual int IndexOf(object v) | Returns the index of the first occurrence of v in the invoking collection. Returns −1 if v is not found. |
| public virtual void InsertRange(int startIdx, ICollection c) | Inserts the elements of c into the invoking collection, starting at the index specified by startIdx. |
| public virtual int LastIndexOf(object v) | Returns the index of the last occurrence of v in the invoking collection. Returns −1 if v is not found. |
| public static ArrayList ReadOnly(ArrayList ar) | Wraps ar in a read-only ArrayList and returns the result. |
| public virtual void RemoveRange(int idx, int count) | Removes count elements from the invoking collection, beginning at idx. |
| public virtual void Reverse( ) | Reverses the contents of the invoking collection. |
| public virtual void Reverse(int startIdx, int count) | Reverses count elements of the invoking collection, beginning at startIdx. |
| public virtual void SetRange(int startIdx, ICollection c) | Replaces elements within the invoking collection, beginning at startIdx, within those specified by c. |
| public virtual void Sort( ) | Sorts the collection into ascending order. |
| public virtual void Sort(IComparer comp) | Sorts the collection using the specified comparison object. If comp is null, the default comparison for each object is used. |
| public virtual void Sort(int startIdx, int count, IComparer comp) | Sorts a portion of the collection using the specified comparison object. The sort begins at startIdx and runs for count elements. If comp is null, the default comparison for each object is used. |
| public static ArrayList Synchronized(ArrayList list) | Returns a synchronized version of the invoking ArrayList. |
| public virtual object[ ] ToArray( ) | Returns an array that contains copies of the elements of the invoking object. |
| public virtual Array ToArray(Type type) | Returns an array that contains copies of the elements of the invoking object. The type of the elements in the array is specified by type. |
| public virtual void TrimToSize( ) | Sets Capacity to Count. |
ArrayList supports several methods that operate on a range of elements within a collection. You can insert another collection into an ArrayList by calling InsertRange( ). You can remove a range by calling RemoveRange( ). You can overwrite a range within an ArrayList with the elements of another collection by calling SetRange( ). You can also sort or search a range rather than the entire collection.
By default, an ArrayList is not synchronized. To obtain a synchronized wrapper around a collection, call Synchronized( ).
In addition to those properties defined by the interfaces that it implements, ArrayList adds Capacity, shown here:
public virtual int Capacity { get; set; } Capacity gets or sets the capacity of the invoking ArrayList. The capacity is the number of elements that can be held before the ArrayList must be enlarged. As mentioned, an ArrayList grows automatically, so it is not necessary to set the capacity manually. However, for efficiency reasons, you might want to set the capacity when you know in advance how many elements the list will contain. This prevents the overhead associated with the allocation of more memory.
Conversely, if you want to reduce the size of the array that underlies an ArrayList, you can set Capacity to a smaller value. However, this value must not be smaller than Count. Recall that Count is a property defined by ICollection that holds the number of objects currently stored in a collection. Attempting to set Capacity to a value less than Count causes an ArgumentOutOfRangeException to be generated. To obtain an ArrayList that is precisely as large as the number of items that it is currently holding, set Capacity equal to Count. You can also call TrimToSize( ).
The following program demonstrates ArrayList. It creates an ArrayList and then adds characters to it. The list is then displayed. Some of the elements are removed, and the list is displayed again. Next, more elements are added, forcing the capacity of the list to be increased. Finally, the contents of elements are changed.
// Demonstrate ArrayList. using System; using System.Collections; class ArrayListDemo { public static void Main() { // create an array list ArrayList al = new ArrayList(); Console.WriteLine("Initial number of elements: " + al.Count); Console.WriteLine(); Console.WriteLine("Adding 6 elements"); // Add elements to the array list al.Add('C'); al.Add('A'); al.Add('E'); al.Add('B'); al.Add('D'); al.Add('F'); Console.WriteLine("Number of elements: " + al.Count); // Display the array list using array indexing. Console.Write("Current contents: "); for(int i=0; i < al.Count; i++) Console.Write(al[i] + " "); Console.WriteLine("\n"); Console.WriteLine("Removing 2 elements"); // Remove elements from the array list. al.Remove('F'); al.Remove('A'); Console.WriteLine("Number of elements: " + al.Count); // Use foreach loop to display the list. Console.Write("Contents: "); foreach(char c in al) Console.Write(c + " "); Console.WriteLine("\n"); Console.WriteLine("Adding 20 more elements"); // Add enough elements to force al to grow. for(int i=0; i < 20; i++) al.Add((char)('a' + i)); Console.WriteLine("Current capacity: " + al.Capacity); Console.WriteLine("Number of elements after adding 20: " + al.Count); Console.Write("Contents: "); foreach(char c in al) Console.Write(c + " "); Console.WriteLine("\n"); // Change contents using array indexing. Console.WriteLine("Change first three elements"); al[0] = 'X'; al[1] = 'Y'; al[2] = 'Z'; Console.Write("Contents: "); foreach(char c in al) Console.Write(c + " "); Console.WriteLine(); } } The output from this program is shown here:
Initial number of elements: 0 Adding 6 elements Number of elements: 6 Current contents: C A E B D F Removing 2 elements Number of elements: 4 Contents: C E B D Adding 20 more elements Current capacity: 32 Number of elements after adding 20: 24 Contents: C E B D a b c d e f g h i j k l m n o p q r s t Change first three elements Contents: X Y Z D a b c d e f g h i j k l m n o p q r s t
Sorting and Searching an ArrayList An ArrayList can be sorted by Sort( ). Once sorted, it can be efficiently searched by BinarySearch( ). The following program demonstrates these methods:
// Sort and search an ArrayList. using System; using System.Collections; class SortSearchDemo { public static void Main() { // create an array list ArrayList al = new ArrayList(); // Add elements to the array list al.Add(55); al.Add(43); al.Add(-4); al.Add(88); al.Add(3); al.Add(19); Console.Write("Original contents: "); foreach(int i in al) Console.Write(i + " "); Console.WriteLine("\n"); // Sort al.Sort(); // Use foreach loop to display the list. Console.Write("Contents after sorting: "); foreach(int i in al) Console.Write(i + " "); Console.WriteLine("\n"); Console.WriteLine("Index of 43 is " + al.BinarySearch(43)); } } The output is shown here:
Original contents: 55 43 -4 88 3 19 Contents after sorting: -4 3 19 43 55 88 Index of 43 is 3
Although an ArrayList can store objects of any type within the same list, when sorting or searching a list, it is necessary for those objects to be comparable. For example, the preceding program would have generated an exception if the list had included a string. (It is possible to create custom comparison methods that would allow the comparison of strings and integers, however. Custom comparators are discussed later in this chapter.)
Obtaining an Array from an ArrayList When working with ArrayList, you will sometimes want to obtain an actual array that contains the contents of the list. You can do this by calling ToArray( ). There are several reasons why you might want to convert a collection into an array. Here are two: you may want to obtain faster processing times for certain operations, or you might need to pass an array to a method that is not overloaded to accept a collection. Whatever the reason, converting an ArrayList to an array is a trivial matter, as the following program shows:
// Convert an ArrayList into an array. using System; using System.Collections; class ArrayListToArray { public static void Main() { ArrayList al = new ArrayList(); // Add elements to the array list. al.Add(1); al.Add(2); al.Add(3); al.Add(4); Console.Write("Contents: "); foreach(int i in al) Console.Write(i + " "); Console.WriteLine(); // Get the array. int[] ia = (int[]) al.ToArray(typeof(int)); int sum = 0; // sum the array for(int i=0; i<ia.Length; i++) sum += ia[i]; Console.WriteLine("Sum is: " + sum); } } The output from the program is shown here:
Contents: 1 2 3 4 Sum is: 10
The program begins by creating a collection of integers. Next, ToArray( ) is called with the type specified as int. This causes an array of integers to be created. Since the return type of ToArray( ) is Array, the contents of the array must still be cast to int[ ]. Finally, the values are summed.
Hashtable
Hashtable creates a collection that uses a hash table for storage. As most readers will know, a hash table stores information using a mechanism called hashing. In hashing, the informational content of a key is used to determine a unique value, called its hash code. The hash code is then used as the index at which the data associated with the key is stored in the table. The transformation of the key into its hash code is performed automatically—you never see the hash code, itself. The advantage of hashing is that it allows the execution time of lookup, retrieve, and set operations to remain constant, even for large sets. Hashtable implements the IDictionary, ICollection, IEnumerable, ISerializable, IDeserializationCallback, and ICloneable interfaces.
Hashtable defines many constructors, including these frequently used ones:
public Hashtable( ) public Hashtable(IDictionary c) public Hashtable(int capacity) public Hashtable(int capacity, float fillRatio)
The first form constructs a default Hashtable. The second form initializes the Hashtable by using the elements of c. The third form initializes the capacity of the Hashtable to capacity. The fourth form initializes both the capacity and fill ratio. The fill ratio (also called the load factor) must be between 0.1 and 1.0, and it determines how full the hash table can be before it is resized upward. Specifically, when the number of elements is greater than the capacity of the table multiplied by its fill ratio, the table is expanded. For constructors that do not take a fill ratio, 1.0 is used.
In addition to the methods defined by the interfaces that it implements, Hashtable also defines several methods of its own. Some commonly used ones are shown in Table 23-5. To determine if a Hashtable contains a key, call ContainsKey( ). To see if a specific value is stored, call ContainsValue( ). To enumerate the contents of a Hashtable, obtain an IDictionaryEnumerator by calling GetEnumerator( ). Recall that IDictionaryEnumerator is used to enumerate the contents of a collection that stores key/value pairs.
| Method | Description |
|---|---|
| public virtual bool ContainsKey(object k) | Returns true if k is a key in the invoking Hashtable. Returns false otherwise. |
| public virtual bool ContainsValue(object v) | Returns true if v is a value in the invoking Hashtable. Returns false otherwise. |
| public virtual IDictionaryEnumerator GetEnumerator( ) | Returns an IDictionaryEnumerator for the invoking Hashtable. |
| public static Hashtable Synchronized(Hashtable ht) | Returns a synchronized version of the Hashtable passed in ht. |
In addition to those properties defined by the interfaces implemented by Hashtable, it adds several public properties of its own. You can obtain a collection of a Hashtable’s keys or values by using the properties shown here:
public virtual ICollection Keys { get; } public virtual ICollection Values { get; } Because Hashtable does not maintain an ordered collection, there is no specific order to the collection of keys or values obtained. Hashtable also has a protected property that was added by C# 2.0: EqualityComparer. C# 2.0 flags two other properties, hcp and comparer, as obsolete.
Hashtable stores key/value pairs in the form of a DictionaryEntry structure, but most of the time you won’t be aware of it directly, because the properties and methods work with keys and values individually. For example, when you add an element to a Hashtable, you call Add( ), which takes two arguments: the key and the value.
It is important to note that Hashtable does not guarantee the order of its elements. This is because the process of hashing does not usually lend itself to the creation of sorted tables.
Here is an example that demonstrates Hashtable:
// Demonstrate Hashtable. using System; using System.Collections; class HashtableDemo { public static void Main() { // Create a hash table. Hashtable ht = new Hashtable(); // Add elements to the table ht.Add("house", "Dwelling"); ht.Add("car", "Means of transport"); ht.Add("book", "Collection of printed words"); ht.Add("apple", "Edible fruit"); // Can also add by using the indexer. ht["tractor"] = "Farm implement"; // Get a collection of the keys. ICollection c = ht.Keys; // Use the keys to obtain the values. foreach(string str in c) Console.WriteLine(str + ": " + ht[str]); } } The output from this program is shown here:
book: Collection of printed words tractor: Farm implement apple: Edible fruit house: Dwelling car: Means of transport
As the output shows, the key/value pairs are not stored in sorted order. Notice how the contents of the hash table ht were obtained and displayed. First, a collection of the keys was retrieved by use of the Keys property. Each key was then used to index the ht, yielding the value associated with each key. Remember, the indexer defined by IDictionary and implemented by Hashtable uses a key as the index.
SortedList
SortedList creates a collection that stores key/value pairs in sorted order, based on the value of the keys. SortedList implements the IDictionary, ICollection, IEnumerable, and ICloneable interfaces.
SortedList has several constructors, including those shown here:
public SortedList( ) public SortedList(IDictionary c) public SortedList(int capacity) public SortedList(IComparer comp)
The first constructor builds an empty collection with an initial capacity of 0. The second constructor builds a SortedList that is initialized with the elements of c and has an initial capacity equal to the number of elements. The third constructor builds an empty SortedList that has the initial capacity specified by capacity. The capacity is the size of the underlying array that is used to store the elements. The fourth form lets you specify a comparison method that will be used to compare the object contained in the list. This form creates an empty collection with an initial capacity of 0.
The capacity of a SortedList grows automatically as needed when elements are added to an array list. When the current capacity is exceeded, the capacity is increased. The advantage of specifying a capacity when creating a SortedList is that that you can prevent or minimize the overhead associated with resizing the collection. Of course, it makes sense to specify an initial capacity only if you have some idea of how many elements will be stored.
In addition to the methods defined by the interfaces that it implements, SortedList also defines several methods of its own. Some of the most commonly used ones are shown in Table 23-6. To determine if a SortedList contains a key, call ContainsKey( ). To see if a specific value is stored, call ContainsValue( ). To enumerate the contents of a SortedList, obtain an IDictionaryEnumerator by calling GetEnumerator( ). Recall that IDictionaryEnumerator is used to enumerate the contents of a collection that stores key/value pairs. You can obtain a synchronized wrapper around a SortedList by calling Synchronized( ).
| Method | Description |
|---|---|
| public virtual bool ContainsKey(object k) | Returns true if k is a key in the invoking SortedList. Returns false otherwise. |
| public virtual bool ContainsValue(object v) | Returns true if v is a value in the invoking SortedList. Returns false otherwise. |
| public virtual object GetByIndex(int idx) | Returns the value at the index specified by idx. |
| public virtual IDictionaryEnumerator GetEnumerator( ) | Returns an IDictionaryEnumerator for the invoking SortedList. |
| public virtual object GetKey(int idx) | Returns the value of the key at the index specified by idx. |
| public virtual IList GetKeyList( ) | Returns an IList collection of the keys in the invoking SortedList. |
| public virtual IList GetValueList( ) | Returns an IList collection of the values in the invoking SortedList. |
| public virtual int IndexOfKey(object k) | Returns the index of the key specified by k. Returns −1 if the key is not in the list. |
| public virtual int IndexOfValue(object v) | Returns the index of the first occurrence of the value specified by v. Returns −1 if the value is not in the list. |
| public virtual void SetByIndex(int idx, object v) | Sets the value at the index specified by idx to the value passed in v. |
| public static SortedList Synchronized(SortedList sl) | Returns a synchronized version of the SortedList passed in sl. |
| public virtual void TrimToSize( ) | Sets Capacity to Count. |
There are various ways to set or obtain a value or key. To obtain the value associated with a specific index, call GetByIndex( ). To set a value given its index, call SetByIndex( ). You can retrieve the key associated with a specific index by calling GetKey( ). To obtain a list of all the keys, use GetKeyList( ). To get a list of all the values, use GetValueList( ). You can obtain the index of a key by calling IndexOfKey( ) and the index of a value by calling IndexOfValue( ). Of course, SortedList also supports the indexer defined by IDictionary that lets you set or obtain a value given its key.
In addition to those properties defined by the interfaces that it implements, SortedList adds two of its own. You can obtain a read-only collection of a SortedList’s keys or values by using the properties shown here:
public virtual ICollection Keys { get; } public virtual ICollection Values { get; } The order of the keys and values reflects that of the SortedList.
Like Hashtable, a SortedList stores key/value pairs in the form of a DictionaryEntry structure, but you will usually access the keys and values individually using the methods and properties defined by SortedList.
The following program demonstrates SortedList. It reworks and expands the Hashtable demonstration program from the previous section, substituting SortedList. When you examine the output, you will see that the SortedList version is sorted by key.
// Demonstrate a SortedList. using System; using System.Collections; class SLDemo { public static void Main() { // Create a sorted SortedList. SortedList sl = new SortedList(); // Add elements to the table sl.Add("house", "Dwelling"); sl.Add("car", "Means of transport"); sl.Add("book", "Collection of printed words"); sl.Add("apple", "Edible fruit"); // Can also add by using the indexer. sl["tractor"] = "Farm implement"; // Get a collection of the keys. ICollection c = sl.Keys; // Use the keys to obtain the values. Console.WriteLine("Contents of list via indexer."); foreach(string str in c) Console.WriteLine(str + ": " + sl[str]); Console.WriteLine(); // Display list using integer indexes. Console.WriteLine("Contents by integer indexes."); for(int i=0; i<sl.Count; i++) Console.WriteLine(sl.GetByIndex(i)); Console.WriteLine(); // Show integer indexes of entries. Console.WriteLine("Integer indexes of entries."); foreach(string str in c) Console.WriteLine(str + ": " + sl.IndexOfKey(str)); } } The output is shown here:
Contents of list via indexer. apple: Edible fruit book: Collection of printed words car: Means of transport house: Dwelling tractor: Farm implement Contents by integer indexes. Edible fruit Collection of printed words Means of transport Dwelling Farm implement Integer indexes of entries. apple: 0 book: 1 car: 2 house: 3 tractor: 4
Stack
As most readers know, a stack is a first-in, last-out list. To visualize a stack, imagine a stack of plates on a table. The first plate put down is the last one to be picked up. The stack is one of the most important data structures in computing. It is frequently used in system software, compilers, and AI-based backtracking routines, to name just a few.
The collection class that supports a stack is called Stack. It implements the ICollection, IEnumerable, and ICloneable interfaces. Stack is a dynamic collection that grows as needed to accommodate the elements it must store.
Stack defines the following constructors:
public Stack( ) public Stack(int capacity) public Stack(ICollection c)
The first form creates an empty stack with an initial capacity of 10. The second form creates an empty stack with the initial capacity specified by capacity. The third form creates a stack that contains the elements of the collection specified by c and an initial capacity equal to the number of elements.
In addition to the methods defined by the interfaces that it implements, Stack defines the methods shown in Table 23-7. In general, here is how you use Stack. To put an object on the top of the stack, call Push( ). To remove and return the top element, call Pop( ). An InvalidOperationException is thrown if you call Pop( ) when the invoking stack is empty. You can use Peek( ) to return, but not remove, the top object.
| Method | Description |
|---|---|
| public virtual void Clear( ) | Sets Count to zero, which effectively clears the stack. |
| public virtual bool Contains(object v) | Returns true if v is on the invoking stack. If v is not found, false is returned. |
| public virtual object Peek( ) | Returns the element on the top of the stack, but does not remove it. |
| public virtual object Pop( ) | Returns the element on the top of the stack, removing it in the process. |
| public virtual void Push(object v) | Pushes v onto the stack. |
| public static Stack Synchronized(Stack stk) | Returns a synchronized version of the Stack passed in stk. |
| public virtual object[ ] ToArray( ) | Returns an array that contains copies of the elements of the invoking stack. |
Here is an example that creates a stack, pushes several Integer objects onto it, then pops them off again:
// Demonstrate the Stack class. using System; using System.Collections; class StackDemo { static void showPush(Stack st, int a) { st.Push(a); Console.WriteLine("Push(" + a + ")"); Console.Write("stack: "); foreach(int i in st) Console.Write(i + " "); Console.WriteLine(); } static void showPop(Stack st) { Console.Write("Pop -> "); int a = (int) st.Pop(); Console.WriteLine(a); Console.Write("stack: "); foreach(int i in st) Console.Write(i + " "); Console.WriteLine(); } public static void Main() { Stack st = new Stack(); foreach(int i in st) Console.Write(i + " "); Console.WriteLine(); showPush(st, 22); showPush(st, 65); showPush(st, 91); showPop(st); showPop(st); showPop(st); try { showPop(st); } catch (InvalidOperationException) { Console.WriteLine("Stack empty."); } } } Here’s the output produced by the program. Notice how the exception handler for InvalidOperationException manages a stack underflow.
Push(22) stack: 22 Push(65) stack: 65 22 Push(91) stack: 91 65 22 Pop -> 91 stack: 65 22 Pop -> 65 stack: 22 Pop -> 22 stack: Pop -> Stack empty.
Queue
Another familiar data structure is the queue, which is a first-in, first-out list. That is, the first item put in a queue is the first item retrieved. Queues are common in real life. For example, lines at a bank or fast-food restaurant are queues. In programming, queues are used to hold such things as the currently executing processes in the system, a list of pending database transactions, or data packets received over the Internet. They are also often used in simulations.
The collection class that supports a queue is called Queue. It implements the ICollection, IEnumerable, and ICloneable interfaces. Queue is a dynamic collection that grows as needed to accommodate the elements it must store. When more room is needed, the size of the queue is increased by a growth factor, which by default is 2.0.
Queue defines the following constructors:
public Queue( ) public Queue (int capacity) public Queue (int capacity, float growFact) public Queue (ICollection c)
The first form creates an empty queue with an initial capacity of 32 that uses the default growth factor of 2.0. The second form creates an empty queue with the initial capacity specified by capacity and a growth factor of 2.0. The third form allows you to specify a growth factor in growFact. The fourth form creates a queue that contains the elements of the collection specified by c, and an initial capacity equal to the number of elements. In this form, the default growth factor of 2.0 is used.
In addition to the methods defined by the interfaces that it implements, Queue defines the methods shown in Table 23-8. In general, here is how you use Queue. To put an object in the queue, call Enqueue( ). To remove and return the object at the front of the queue, call Dequeue( ). An InvalidOperationException is thrown if you call Dequeue( ) when the invoking queue is empty. You can use Peek( ) to return, but not remove, the next object.
| Method | Description |
|---|---|
| public virtual void Clear( ) | Sets Count to zero, which effectively clears the queue. |
| public virtual bool Contains(object v) | Returns true if v is in the invoking queue. If v is not found, false is returned. |
| public virtual object Dequeue( ) | Returns the object at the front of the invoking queue. The object is removed in the process. |
| public virtual void Enqueue(object v) | Adds v to the end of the queue. |
| public virtual object Peek( ) | Returns the object at the front of the invoking queue, but does not remove it. |
| public static Queue Synchronized(Queue q) | Returns a synchronized version of q. |
| public virtual object[ ] ToArray( ) | Returns an array that contains copies of the elements of the invoking queue. |
| public virtual void TrimToSize( ) | Sets Capacity to Count. |
Here is an example that demonstrates Queue:
// Demonstrate the Queue class. using System; using System.Collections; class QueueDemo { static void showEnq(Queue q, int a) { q.Enqueue(a); Console.WriteLine("Enqueue(" + a + ")"); Console.Write("queue: "); foreach(int i in q) Console.Write(i + " "); Console.WriteLine(); } static void showDeq(Queue q) { Console.Write("Dequeue -> "); int a = (int) q.Dequeue(); Console.WriteLine(a); Console.Write("queue: "); foreach(int i in q) Console.Write(i + " "); Console.WriteLine(); } public static void Main() { Queue q = new Queue(); foreach(int i in q) Console.Write(i + " "); Console.WriteLine(); showEnq(q, 22); showEnq(q, 65); showEnq(q, 91); showDeq(q); showDeq(q); showDeq(q); try { showDeq(q); } catch (InvalidOperationException) { Console.WriteLine("Queue empty."); } } } The output is shown here:
Enqueue(22) queue: 22 Enqueue(65) queue: 22 65 Enqueue(91) queue: 22 65 91 Dequeue -> 22 queue: 65 91 Dequeue -> 65 queue: 91 Dequeue -> 91 queue: Dequeue -> Queue empty.
EAN: 2147483647
Pages: 300