|
|
< Day Day Up > |
|
4.4. Working with .NET Collection Classes and InterfacesIn .NET, collection is a general term that applies to the set of classes that represent the classic data structures used to group related types of data. These classes include stacks, queues, hash tables, arrays, and dictionaries. All are contained in one of two namespaces: System.Collections or System.Collections.Generic. In .NET versions 1.0 and 1.1, System.Collections was home to all collection classes. In the .NET 2.0 release, these original classes were revised to support generics梐 way to make collections type-safe. The .NET developers left the original namespace in for backward compatibility and added the System.Collections.Generic namespace to contain the generic classes. With the exception of the generics features, the classes in the two namespaces offer the same functionality梐lthough there are a few name changes. To avoid confusion, much of this section refers to the System.Collections namespace. The details of generics are presented at the end of the section. To best work with container classes such as the ArrayList and Hashtable, a developer should be familiar with the interfaces they implement. Interfaces not only provide a uniform way of managing and accessing the contents of a collection, but they are the key to creating a custom collection. We'll begin the section by looking at the most useful interfaces and the behavior they impart to the collection classes. Then, we'll examine selected collection classes. Collection InterfacesInterfaces play a major role in the implementation of the concrete collection classes. All collections inherit from the ICollection interface, and most inherit from the IEnumerable interface. This means that a developer can use common code semantics to work with the different collections. For example, the foreach statement is used to traverse the elements of a collection whether it is a Hashtable,a SortedList, or a custom collection. The only requirement is that the class implements the IEnumerable interface. Table 4-2 summarizes the most important interfaces inherited by the collection classes. IComparer provides a uniform way of comparing elements for the purpose of sorting; IDictionary defines the special members required by the Hashtable and Dictionary objects; similarly, IList is the base interface for the ArrayList collection.
The UML-like diagram in Figure 4-7 shows how these interfaces are related. Recall that interfaces may inherit from multiple interfaces. Here, for example, IDictionary and IList inherit from IEnumerable and ICollection. Also of special interest is the GetEnumerator method that is used by interfaces to return the IEnumerator interface. Figure 4-7. System.Collections Interface diagram
Of these interfaces, IDictionary and IList are the most important when considering the built-in collections provided by the FCL. For this reason, we'll discuss them later in the context of the collection classes. ICollection InterfaceThis interface provides the minimal information that a collection must implement. All classes in the System.Collections namespace inherit it (see Table 4-3).
The IsSynchronized and SyncRoot properties require explanation if you are not yet familiar with threading (discussed in Chapter 13, "Asynchronous Programming and Multithreading"). Briefly, their purpose is to ensure the integrity of data in a collection while it is being accessed by multiple clients. It's analogous to locking records in a database to prevent conflicting updates by multiple users. IHashCodeProvider InterfaceThis interface has one member梩he GetHashCode method梩hat uses a custom hash function to return a hash code value for an object. The Hashtable class uses this interface as a parameter type in one of its overloaded constructors, but other than that you will rarely see it. Using the IEnumerable and IEnumerator Interfaces to List the Contents of a CollectionFor a class to support iteration using the foreach construct, it must implement the IEnumerable and IEnumerator interfaces. IEnumerator defines the methods and properties used to implement the enumerator pattern; IEnumerable serves only to return an IEnumerator object. Table 4-4 summarizes the member(s) provided by each interface.
These members are implemented in a custom collection class as a way to enable users to traverse the objects in the collection. To understand how to use these members, let's look at the underlying code that implements the foreach construct. The foreach loop offers a simple syntax:
foreach ( ElementType element in collection)
{
Console.WriteLine(element.Name);
}
The compiler expands the foreach construct into a while loop that employs IEnumerable and IEnumerator members:
// Get enumerator object using collection's GetEnumerator method
IEnumerator enumerator =
((IEnumerable) (collection)).GetEnumerator();
try
{
while (enumerator.MoveNext())
{
ElementType element = (ElementType)enumerator.Current;
Console.WriteLine(element.Name);
}
}
finally
// Determine if enumerator implements IDisposable interface
// If so, execute Dispose method to release resources
{
IDisposable disposable = enumerator as System.IDisposable;
If( disposable !=null) disposable.Dispose();
}
When a client wants to iterate across the members of a collection (enumerable), it obtains an enumerator object using the IEnumerable.GetEnumerator method. The client then uses the members of the enumerator to traverse the collection: MoveNext() moves to the next element in the collection, and the Current property returns the object referenced by the current index of the enumerator. Formally, this is an implementation of the iteration design pattern. Core Note IteratorsThe foreach construct provides a simple and uniform way to iterate across members of a collection. For this reason, it is a good practice梐lmost a de facto requirement梩hat any custom collection support foreach. Because this requires that the collection class support the IEnumerable and IEnumerator interfaces, the traditional approach is to explicitly implement each member of these interfaces inside the collection class. Referencing Table 4-4, this means writing code to support the GetEnumerator method of the IEnumerable interface, and the MoveNext, Current, and Reset members of IEnumerator. In essence, it is necessary to build a state machine that keeps track of the most recently accessed item in a collection and knows how to move to the next item. C# 2.0 introduced a new syntax referred to as iterators that greatly simplifies the task of implementing an iterator pattern. It includes a yield return (also a yield break) statement that causes the compiler to automatically generate code to implement the IEnumerable and IEnumerator interfaces. To illustrate, let's add iterators to the GenStack collection class that was introduced in the generics discussion in Chapter 3. (Note that iterators work identically in a non-generics collection.) Listing 4-7 shows part of the original GenStack class with two new members that implement iterators: a GetEnumerator method that returns an enumerator to traverse the collection in the order items are stored, and a Reverse property that returns an enumerator to traverse the collection in reverse order. Both use yield return to generate the underlying code that supports foreach iteration. Listing 4-7. Using Iterators to Implement Enumeration
using System;
using System.Collections.Generic;
public class GenStack<T>: IEnumerable<T>
{
// Use generics type parameter to specify array type
private T[] stackCollection;
private int count = 0;
// Constructor
public GenStack(int size)
{
stackCollection = new T[size];
}
// (1) Iterator
public IEnumerator<T> GetEnumerator()
{
for (int i = 0; i < count; i++)
{
yield return stackCollection[i];
}
}
// (2) Property to return the collection in reverse order
public IEnumerable<T> Reverse
{
get
{
for (int i = count - 1; i >= 0; i--)
{
yield return stackCollection[i];
}
}
}
public void Add(T item)
{
stackCollection[count] = item;
count += 1;
}
// other class methods go here ...
This code should raise some obvious questions about iterators: Where is the implementation of IEnumerator? And how can a method with an IEnumerator return type or a property with an IEnumerable return type seemingly return a string value? The answer to these questions is that the compiler generates the code to take care of the details. If the member containing the yield return statement is an IEnumerable type, the compiler implements the necessary generics or non-generics version of both IEnumerable and IEnumerator; if the member is an IEnumerator type, it implements only the two enumerator interfaces. The developer's responsibility is limited to providing the logic that defines how the collection is traversed and what items are returned. The compiler uses this logic to implement the IEnumerator.MoveNext method. The client code to access the GenStack collection is straightforward. An instance of the GenStack class is created to hold ten string elements. Three items are added to the collection and are then displayed in original and reverse sequence.
GenStack<string> myStack = new GenStack<string>(10);
myStack.Add("Aida");
myStack.Add("La Boheme");
myStack.Add("Carmen");
// uses enumerator from GetEnumerator()
foreach (string s in myStack)
Console.WriteLine(s);
// uses enumerator from Reverse property
foreach (string s in myStack.Reverse)
Console.WriteLine(s);
The Reverse property demonstrates how easy it is to create multiple iterators for a collection. You simply implement a property that traverses the collection in some order and uses tbe yield return statement(s) to return an item in the collection. Core Note
There are some restrictions on using yield return or yield break:
Using the IComparable and IComparer Interfaces to Perform SortingChapter 2, "C# Language Fundamentals," included a discussion of the System.Array object and its associated Sort method. That method is designed for primitive types such as strings and numeric values. However, it can be extended to work with more complex objects by implementing the IComparable and IComparer interfaces on the objects to be sorted. IComparableUnlike the other interfaces in this section, IComparable is a member of the System namespace. It has only one member, the method CompareTo: int CompareTo(Object obj)
The object in parentheses is compared to the current instance of the object implementing CompareTo, and the returned value indicates the results of the comparison. Let's use this method to extend the Chair class so that it can be sorted on its myPrice field. This requires adding the IComparable inheritance and implementing the CompareTo method.
public class Chair : ICloneable, IComparable
{
private double myPrice;
private string myVendor, myID;
public Upholstery myUpholstery;
//... Constructor and other code
// Add implementation of CompareTo to sort in ascending
int IComparable.CompareTo(Object obj)
{
if (obj is Chair) {
Chair castObj = (Chair)obj;
if (this.myPrice > castObj.myPrice)
return 1;
if (this.myPrice < castObj.myPrice)
return -1;
else return 0;
// Reverse 1 and ? to sort in descending order
}
throw new ArgumentException("object in not a Chair");
}
The code to sort an array of Chair objects is straightforward because all the work is done inside the Chair class: Chair[]chairsOrdered = new Chair[4]; chairsOrdered[0] = new Chair(150.0, "Lane","99-88"); chairsOrdered[1] = new Chair(250.0, "Lane","99-00"); chairsOrdered[2] = new Chair(100.0, "Lane","98-88"); chairsOrdered[3] = new Chair(120.0, "Harris","93-9"); Array.Sort(chairsOrdered); // Lists in ascending order of price foreach(Chair c in chairsOrdered) MessageBox.Show(c.ToString()); IComparerThe previous example allows you to sort items on one field. A more flexible and realistic approach is to permit sorting on multiple fields. This can be done using an overloaded form of Array.Sort that takes an object that implements IComparer as its second parameter. IComparer is similar to IComparable in that it exposes only one member, Compare, that receives two objects. It returns a value of ?, 0, or 1 based on whether the first object is less than, equal to, or greater than the second. The first object is usually the array to be sorted, and the second object is a class implementing a custom Compare method for a specific object field. This class can be implemented as a separate helper class or as a nested class within the class you are trying to sort (Chair). This code creates a helper class that sorts the Chair objects by the myVendor field:
public class CompareByVen : IComparer
{
public CompareByVen() { }
int IComparer.Compare(object obj1, object obj2)
{
// obj1 contains array being sorted
// obj2 is instance of helper sort class
Chair castObj1 = (Chair)obj1;
Chair castObj2 = (Chair)obj2;
return String.Compare
(castObj1.myVendor,castObj2.myVendor);
}
}
If you refer back to the Chair class definition (refer to Figure 4-6 on page 166), you will notice that there is a problem with this code: myVendor is a private member and not accessible in this outside class. To make the example work, change it to public. A better solution, of course, is to add a property to expose the value of the field. In order to sort, pass both the array to be sorted and an instance of the helper class to Sort: Array.Sort(chairsOrdered,new CompareByVen()); In summary, sorting by more than one field is accomplished by adding classes that implement Compare for each sortable field. System.Collections NamespaceThe classes in this namespace provide a variety of data containers for managing collections of data. As shown in Figure 4-8, it is useful to categorize them based on the primary interface they implement: ICollection, IList, or IDictionary. Figure 4-8. Selected classes in System.Collections
The purpose of interfaces is to provide a common set of behaviors for classes. Thus, rather than look at the details of all the classes, we will look at the interfaces themselves as well as some representative classes that illustrate how the members of the interfaces are implemented. We've already looked at ICollection, so let's begin with two basic collections that inherit from it. Stack and QueueThe Stack and the Queue are the simplest of the collection classes. Because they do not inherit from IList or IDictionary, they do not provide indexed or keyed access. The order of insertion controls how objects are retrieved from them. In a Stack, all insertions and deletions occur at one end of the list; in a Queue, insertions are made at one end and deletions at the other. Table 4-5 compares the two.
Stacks play a useful role for an application that needs to maintain state information in order to hold tasks to be "performed later." The call stack associated with exception handling is a classic example; stacks are also used widely in text parsing operations. Listing 4-8 provides an example of some of the basic stack operations. Listing 4-8. Using the Stack Container
public class ShowStack {
public static void Main()
{
Stack myStack = new Stack();
myStack.Push(new Chair(250.0, "Adams Bros.", "87-00" ));
myStack.Push(new Chair(100.0, "Broyhill","87-04" ));
myStack.Push(new Chair(100.0, "Lane","86-09" ));
PrintValues( myStack ); // Adams ?Broyhill - Lane
// Pop top object and push a new one on stack
myStack.Pop();
myStack.Push(new Chair(300.0, "American Chair"));
Console.WriteLine(myStack.Peek().ToString()); // American
}
public static void PrintValues( IEnumerable myCollection )
{
System.Collections.IEnumerator myEnumerator =
myCollection.GetEnumerator();
while ( myEnumerator.MoveNext() )
Consle.WriteLine(myEnumerator.Current.ToString());
// Could list specific chair fields with
// myChair = (Chair) myEnumerator.Current;
}
}
Three objects are added to the stack. PrintValues enumerates the stack and lists the objects in the reverse order they were added. The Pop method removes "Lane" from the top of the stack. A new object is pushed onto the stack and the Peek method lists it. Note that the foreach statement could also be used to list the contents of the Stack. ArrayListThe ArrayList includes all the features of the System.Array, but also extends it to include dynamic sizing and insertion/deletion of items at a specific location in the list. These additional features are defined by the IList interface from which ArrayList inherits. IList InterfaceThis interface, whose members are listed in Table 4-6, is used to retrieve the contents of a collection via a zero-based numeric index. This permits insertion and removal at random location within the list.
The most important thing to observe about this interface is that it operates on object types. This means that an ArrayList梠r any collection implementing IList梞ay contain types of any kind. However, this flexibility comes at a cost: Casting must be widely used in order to access the object's contents, and value types must be converted to objects (boxed) in order to be stored in the collection. As we see shortly, C# 2.0 offers a new feature梒alled generics梩hat addresses both issues. However, the basic functionality of the ArrayList, as illustrated in this code segment, remains the same. ArrayList chairList = new ArrayList( ); // alternative: ArrayList chairList = new ArrayList(5); chairList.Add(new Chair(350.0, "Adams", "88-00")); chairList.Add(new Chair(380.0, "Lane", "99-33")); chairList.Add(new Chair(250.0, "Broyhill", "89-01")); PrintValues(chairList); // Adams ?Lane - Broyhill // chairList.Insert(1,new Chair(100,"Kincaid")); chairList.RemoveAt(2); Console.WriteLine("Object Count: {0}",chairList.Count); // PrintValues(chairList); // Adams ?Kincaid - Broyhill // Copy objects to an array Object chairArray = chairList.ToArray(); PrintValues((IEnumerable) chairArray); This parameterless declaration of ArrayList causes a default amount of memory to be initially allocated. You can control the initial allocation by passing a size parameter to the constructor that specifies the number of elements you expect it to hold. In both cases, the allocated space is automatically doubled if the capacity is exceeded. HashtableThe Hashtable is a .NET version of a dictionary for storing key-value pairs. It associates data with a key and uses the key (a transformation algorithm is applied) to determine a location where the data is stored in the table. When data is requested, the same steps are followed except that the calculated memory location is used to retrieve data rather than store it. Syntax: public class Hashtable : IDictionary, ICollection, IEnumerable, ISerializable, IDeserializationCallback, ICloneable As shown here, the Hashtable inherits from many interfaces; of these, IDictionary is of the most interest because it provides the properties and methods used to store and retrieve data. IDictionary InterfaceCollections implementing the IDictionary interface contain items that can be retrieved by an associated key value. Table 4-7 summarizes the most important members for working with such a collection.
IDictionaryEnumerator InterfaceAs shown in Figure 4-7 on page 169, IDictionaryEnumerator inherits from IEnumerator. It adds properties to enumerate through a dictionary by retrieving keys, values, or both.
All classes derived from IDictionary maintain two internal lists of data: one for keys and one for the associated value, which may be an object. The values are stored in a location based on the hash code of the key. This code is provided by the key's System.Object.GetHashCode method, although it is possible to override this with your own hash algorithm. This structure is efficient for searching, but less so for insertion. Because keys may generate the same hash code, a collision occurs that requires the code be recalculated until a free bucket is found. For this reason, the Hashtable is recommended for situations where a large amount of relatively static data is to be searched by key values. Create a HashtableA parameterless constructor creates a Hashtable with a default number of buckets allocated and an implicit load factor of 1. The load factor is the ratio of values to buckets the storage should maintain. For example, a load factor of .5 means that a hash table should maintain twice as many buckets as there are values in the table. The alternate syntax to specify the initial number of buckets and load factor is Hashtable chairHash = new Hashtable(1000, .6) The following code creates a hash table and adds objects to it:
// Create HashTable
Hashtable chairHash = new Hashtable();
// Add key - value pair to Hashtable
chairHash.Add ("88-00", new Chair(350.0, "Adams", "88-00");
chairHash.Add ("99-03", new Chair(380.0, "Lane", "99-03");
// or this syntax
chairHash["89-01"] = new Chair(250.0, "Broyhill", "89-01");
There are many ways to add values to a Hashtable, including loading them from another collection. The preceding example shows the most straightforward approach. Note that a System.Argument exception is thrown if you attempt to add a value using a key that already exists in the table. To check for a key, use the ContainsKey method:
// Check for existence of a key
bool keyFound;
if (chairHash.ContainsKey("88-00"))
{ keyFound = true;}
else
{keyFound = false;}
List Keys in a HashtableThe following iterates through the Keys property collection:
// List Keys
foreach (string invenKey in chairHash.Keys)
{ MessageBox.Show(invenKey); }
List Values in a HashtableThese statements iterate through the Values in a hash table:
// List Values
foreach (Chair chairVal in chairHash.Values)
{ MessageBox.Show(chairVal.myVendor);}
List Keys and Values in a HashtableThis code lists the keys and values in a hash table:
foreach ( DictionaryEntry deChair in chairHash)
{
Chair obj = (Chair) deChair.Value;
MessageBox.Show(deChair.Key+" "+ obj.myVendor);
}
The entry in a Hashtable is stored as a DictionaryEntry type. It has a Value and Key property that expose the actual value and key. Note that the value is returned as an object that must be cast to a Chair type in order to access its fields. Core Note
This section has given you a flavor of working with System.Collections interfaces and classes. The classes presented are designed to meet most general-purpose programming needs. There are numerous other useful classes in the namespace as well as in the System.Collections.Specialized namespace. You should have little trouble working with either, because all of their classes inherit from the same interfaces presented in this section. System.Collections.Generic NamespaceRecall from Chapter 3 that generics are used to implement type-safe classes, structures, and interfaces. The declaration of a generic type includes one (or more) type parameters in brackets (<>) that serve(s) as a placeholder for the actual type to be used. When an instance of this type is created, the client uses these parameters to pass the specific type of data to be used in the generic type. Thus, a single generic class can handle multiple types of data in a type-specific manner. No classes benefit more from generics than the collections classes, which stored any type of data as an object in .NET 1.x. The effect of this was to place the burden of casting and type verification on the developer. Without such verification, a single ArrayList instance could be used to store a string, an integer, or a custom object. Only at runtime would the error be detected. The System.Collections.Generic namespace provides the generic versions of the classes in the System.Collections namespace. If you are familiar with the non-generic classes, switching to the generic type is straightforward. For example, this code segment using the ArrayList:
ArrayList primes = new ArrayList();
primes.Add(1);
primes.Add(3);
int pSum = (int)primes[0] + (int)primes[1];
primes.Add("test");
can be replaced with the generics version: List<int> primes = new List<int>(); primes.Add(1); primes.Add(3); int pSum = primes[0] + primes[1]; primes.Add("text"); // will not compile The declaration of List includes a type parameter that tells the compiler what type of data the object may contain?tt>int in this case. The compiler then generates code that expects the specified type. For the developer, this eliminates the need for casting and type verification at runtime. From a memory usage and efficiency standpoint, it also eliminates boxing (conversion to objects) when primitives are stored in the collection. Comparison of System.Collections and System.Collections.Generic NamespacesAs the following side-by-side comparison shows, the classes in the two namespaces share the same name with three exceptions: Hashtable becomes Dictionary<>, ArrayList becomes List<>, and SortedList is renamed SortedDictionary<>.
The only other points to note regard IEnumerator. Unlike the original version, the generics version inherits from IDisposable and does not support the Reset method. An Example Using a Generics Collections ClassSwitching to the generics versions of the collection classes is primarily a matter of getting used to a new syntax, because the functionality provided by the generics and non-generics classes is virtually identical. To demonstrate, here are two examples. The first uses the Hashtable to store and retrieve instances of the Chair class (defined in Listing 4-5); the second example performs the same functions but uses the Dictionary class梩he generics version of the Hashtable. This segment consists of a Hashtable declaration and two methods: one to store a Chair object in the table and the other to retrieve an object based on a given key value.
// Example 1: Using Hashtable
public Hashtable ht = new Hashtable();
// Store Chair object in table using a unique product identifier
private void saveHT(double price, string ven, string sku)
{
if (!ht.ContainsKey(sku))
{
ht.Add(sku, new Chair(price,ven,sku));
}
}
// Display vendor and price for a product identifier
private void showChairHT(string sku)
{
if (ht.ContainsKey(key))
{
if (ht[key] is Chair) // Prevent casting exception
{
Chair ch = (Chair)ht[sku];
Console.WriteLine(ch.MyVen + " " + ch.MyPr);
}
else
{ Console.WriteLine("Invalid Type: " +
(ht[key].GetType().ToString()));
}
}
}
Observe how data is retrieved from the Hashtable. Because data is stored as an object, verification is required to ensure that the object being retrieved is a Chair type; casting is then used to access the members of the object. These steps are unnecessary when the type-safe Dictionary class is used in place of the Hashtable. The Dictionary<K,V> class accepts two type parameters that allow it to be strongly typed: K is the key type and V is the type of the value stored in the collection. In this example, the key is a string representing the unique product identifier, and the value stored in the Dictionary is a Chair type. // Example 2: Using Generics Dictionary to replace Hashtable // Dictionary accepts string as key and Chair as data type Dictionary<string,Chair> htgen = new Dictionary<string,Chair>(); // private void saveGen(double price, string ven, string sku) { if (!htgen.ContainsKey(sku)) { htgen.Add(sku, new Chair(price,ven,sku)); } } private void showChairGen(string sku) { if (htgen.ContainsKey(key)) { Chair ch = htgen[sku]; // No casting required Console.WriteLine(ch.MyVen + " " + ch.MyPr); } } The important advantage of generics is illustrated in the showChairGen method. It has no need to check the type of the stored object or perform casting. In the long run, the new generic collection classes will render the classes in the System.Collections namespace obsolete. For that reason, new code development should use the generic classes where possible. |
|
|
< Day Day Up > |
|
