This chapter discusses one of the most important parts of the .NET Framework: collections. In C#, a collection is a group of objects. The .NET Framework contains a large number of interfaces and classes that define and implement various types of collections. Collections simplify many programming tasks because they provide off-the-shelf solutions to several common, but sometimes tedious-to-develop, data structures. For example, there are built-in collections that support dynamic arrays, linked lists, stacks, queues, and hash tables. Collections are a state-of-the-art technology that merits close attention by all C# programmers.
Originally, there were only non-generic collection classes. However, the addition of generics in C# 2.0 coincided with the addition of many new generic classes and interfaces to the .NET Framework. The inclusion of the generic collections essentially doubled the number of collection classes and interfaces. With the advent of the Task Parallel Library in .NET Framework 4.0, several new thread-safe collection classes were added that are designed for use in situations in which multiple threads access a collection. As you can surmise, the Collections API is a very large part of the .NET Framework.
Also described in this chapter are two features that relate to collections: enumerators and iterators. Both enumerators and iterators enable the contents of a class to be cycled through via a foreach loop.
The principal benefit of collections is that they standardize the way groups of objects are handled by your programs. All collections are designed around a set of cleanly defined interfaces. Several built-in implementations of these interfaces, such as ArrayList, Hashtable, Stack, and Queue, are provided, which you can use as-is. You can also implement your own collection, but you will seldom need to.
The .NET Framework supports five general types of collections: non-generic, specialized, bit-based, generic, and concurrent. The non-generic collections implement several fundamental data structures, including a dynamic array, stack, and queue. They also include dictionaries, in which you can store key/value pairs. An essential point to understand about the non-generic collections is that they operate on data of type object. Thus, they can be used to store any type of data, and different types of data can be mixed within the same collection. Of course, because they store object references, they are not type-safe. The non-generic collection classes and interfaces are in System.Collections.
The specialized collections operate on a specific type of data or operate in a unique way. For example, there are specialized collections for strings. There are also specialized collections that use a singly linked list. The specialized collections are declared in System.Collections.Specialized.
The Collections API defines one bit-based collection called BitArray. BitArray supports bitwise operations on bits, such as AND and XOR. As such, it differs significantly in its capabilities from the other collections. BitArray is declared in System.Collections.
The generic collections provide generic implementations of several standard data structures, such as linked lists, stacks, queues, and dictionaries. Because these collections are generic, they are type-safe. This means that only items that are type-compatible with the type of the collection can be stored in a generic collection, thus eliminating accidental type mismatches. Generic collections are declared in System.Collections.Generic.
The concurrent collections support multithreaded access to a collection. These are generic collections that are defined in System.Collections.Concurrent.
There are also several classes in the System.Collections.ObjectModel namespace that support programmers who want to create their own generic collections.
Fundamental to all collections is the concept of an enumerator, which is supported by the non-generic interfaces IEnumerator and IEnumerable, and the generic interfaces IEnumerator<T> and IEnumerable<T>. An enumerator provides a standardized way of accessing the elements within a collection, one at a time. Thus, it enumerates the contents of a collection. Because each collection must implement either a generic or non-generic form of IEnumerable, the elements of any collection class can be accessed through the methods defined by IEnumerator or IEnumerator<T>. Therefore, with only small changes, the code that cycles through one type of collection can be used to cycle through another. As a point of interest, the foreach loop uses the enumerator to cycle through the contents of a collection.
A feature related to an enumerator is the iterator. It simplifies the process of creating classes, such as custom collections, that can be cycled through by a foreach loop. Iterators are also described in this chapter.
One last thing: If you are familiar with C++, then you will find it helpful to know that the collection classes are similar in spirit to the Standard Template Library (STL) classes defined by C++. What a C++ programmer calls a container, a C# programmer calls a collection. The same is true of Java. If you are familiar with Java’s Collections Framework, then you will have no trouble learning to use C# collections.
Because of the differences among the five types of collections—non-generic, bit-based, specialized, generic, and concurrent—this chapter discusses each separately.
The non-generic collections have been part of the .NET Framework since version 1.0. They are defined in the System.Collections namespace. The non-generic collections are generalpurpose 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 types of objects or when the type of objects being stored are 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 the classes that implement those interfaces. Each is described by the following sections.
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 25-1. The following sections examine each interface in detail.
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.
TABLE 25-1 The Non-Generic Collection Interfaces
ICollection defines the following properties:
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 array, int index)
CopyTo( ) copies the contents of a collection to the array specified by array, beginning at the index specified by index. Thus, CopyTo( ) provides a pathway from a collection to a standard C# array.
Because ICollection inherits IEnumerable, it also includes the sole method defined by IEnumerable: GetEnumerator( ), which is shown here:
IEnumerator GetEnumerator( )
It returns the enumerator for the collection.
Because ICollection implements IEnumerable, four extension methods are defined for it. They are AsParallel( ), AsQueryable( ), Cast( ), and OfType( ). AsParallel( ) is declared in System.Linq.ParallelEnumerable. AsQueryable( ) is declared in System.Linq.Queryable. Both Cast( ) and OfType( ) are declared in System.Linq.Enumerable. These methods are designed primarily to support LINQ, but may be useful in other contexts.
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 25-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.
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 called IndexOf( ). You can insert an element at a specific index by calling Insert( ).
TABLE 25-2 The Methods Defined by IList
IList defines the following properties:
bool IsFixedSize { get; }
bool IsReadOnly { get; }
If the collection is of fixed size, IsFixedSize is true. This means 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 index] { 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 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 25-3. Several methods throw an ArgumentNullException if an attempt is made to specify a null key and null keys are not allowed.
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( ).
TABLE 25-3 The Methods Defined by IDictionary
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:
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 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.
IEnumerator defines the methods MoveNext( ) and Reset( ) and the Current property. These methods and the techniques needed to use them are described in detail later in this chapter. Briefly, Current obtains the element currently being obtained. MoveNext( ) moves to the next element. Reset( ) restarts the enumeration from the start.
The IComparer interface defines a method called Compare( ), which defines the way two objects are compared. It is shown here:
int Compare(object x, object y)
It must return greater than zero if x is greater than y, less than zero if x is less than y, 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.
IEqualityComparer defines these two methods:
bool Equals(object x, object y)
int GetHashCode(object obj)
Equals( ) must return true if x and y are equal. GetHashCode( ) must return the hash code for obj.
The IStructuralComparable and IStructuralEquatable interfaces were added by .NET 4.0. The IStructuralComparable interface defines a method called CompareTo( ), which defines the way two objects are structurally compared for purposes of sorting. (In other words, CompareTo( ) compares the contents of the object, not the references.) It is shown here:
int CompareTo(object other, IComparer comparer)
It must return –1 if the invoking object precedes other, 1 if the invoking object follows other, and zero if the two values are the same for the purposes of sorting. The object passed to comparer provides the comparison.
IStructuralEquatable is used to determine structural equality. Thus, it compares the contents of two objects. It defines the following methods.
bool Equals(object other, IEqualityComparer comparer)
int GetHashCode(IEqualityComparer comparer)
Equals( ) must return true if the invoking object and other are equal. GetHashCode( ) must return the hash code for the invoking object. The results of these two methods must be compatible. The object passed to comparer provides the comparison.
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 key, object value)
Here, key is the key and value is the value.
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:
The following sections examine these collection classes and illustrate their use.
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 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 this reason, 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 zero. 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 25-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( ).
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( ).
TABLE 25-4 Several Commonly Used Methods Defined by ArrayList
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 less 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 {
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 rs 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 rs 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 {
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 {
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[ ]. (Recall that Array is the base type of all C# arrays.) Finally, the values are summed.
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 near 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 d)
public Hashtable(int capacity)
public Hashtable(int capacity, float loadFactor)
The first form constructs a default Hashtable. The second form initializes the Hashtable by using the elements of d. 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 25-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.
TABLE 25-5 Several Commonly Used Methods Defined by Hashtable
The public properties available in Hashtable are those defined by the interfaces that it implements. Two especially important ones are Keys and Values because they let you obtain a collection of a Hashtable’s keys or values. They are specified by IDictionary and are 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: EqualityComparer. Two other properties called hcp and comparer are flagged 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 {
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 the Keys property. Each key was then used to index 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 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 d)
public SortedList(int initialCapacity)
public SortedList(IComparer comparer)
The first constructor builds an empty collection with an initial capacity of zero. The second constructor builds a SortedList that is initialized with the elements of d 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 initialCapacity. 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 objects contained in the list. This form creates an empty collection with an initial capacity of zero.
The capacity of a SortedList grows automatically as needed when elements are added to the list. When the current capacity is exceeded, the capacity is increased. The advantage of specifying a capacity when creating a SortedList is 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 25-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( ).
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.
The public properties available in SortedList are those defined by the interfaces that it implements. As is the case with Hashtable, two especially important properties are Keys and Values because they let you obtain a read-only collection of a SortedList’s keys or values. They are specified by IDictionary and are shown here:
TABLE 25-6 Several Commonly Used Methods Defined by SortedList
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 {
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
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 examples.
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 initialCapacity)
public Stack(ICollection col)
The first form creates an empty stack. The second form creates an empty stack with the initial capacity specified by initialCapacity. The third form creates a stack that contains the elements of the collection specified by col 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 25-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( ). You can use Peek( ) to return, but not remove, the top object. An InvalidOperationException is thrown if you call Pop( ) or Peek( ) when the invoking stack is empty.
TABLE 25-7 The Methods Defined by Stack
Here is an example that creates a stack, pushes several integers onto it, and 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();
}
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.
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 growFactor)
public Queue (ICollection col)
The first form creates an empty queue with a default capacity and 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 growFactor (which must be between 1.0 and 10.0). The fourth form creates a queue that contains the elements of the collection specified by col, 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 25-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( ). You can use Peek( ) to return, but not remove, the next object. An InvalidOperationException is thrown if you call Dequeue( ) or Peek( ) when the invoking queue is empty.
TABLE 25-8 The Methods De. ned by Queue
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();
}
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.
The BitArray class supports a collection of bits. Because it stores bits rather than objects, BitArray has capabilities different from those of the other collections. However, it still supports the basic collection underpinning by implementing ICollection and IEnumerable. It also implements ICloneable.
BitArray defines several constructors. You can construct a BitArray from an array of Boolean values using this constructor:
public BitArray(bool[ ] values)
In this case, each element of values becomes a bit in the collection. Thus, each bit in the collection corresponds to an element of values. Furthermore, the ordering of the elements of values and the bits in the collection are the same.
You can create a BitArray from an array of bytes using this constructor:
public BitArray(byte[ ] bytes)
Here, the bit pattern in bytes becomes the bits in the collection, with bytes[0] specifying the first 8 bits, bytes[1] specifying the second 8 bits, and so on. In similar fashion, you can construct a BitArray from an array of ints using this constructor:
public BitArray(int[ ] values)
In this case, values[0] specifies the first 32 bits, values[1] specifies the second 32 bits, and so on.
You can create a BitArray of a specific size using this constructor:
public BitArray(int length)
Here, length specifies the number of bits. The bits in the collection are initialized to false. To specify a size and initial value of the bits, use the following constructor:
public BitArray(int length, bool defaultValue)
In this case, all bits in the collection will be set to the value passed in defaultValue.
Finally, you can create a new BitArray from an existing one by using this constructor:
public BitArray(BitArray bits)
The new object will contain the same collection of bits as bits, but the two collections will be otherwise separate.
BitArrays can be indexed. Each index specifies an individual bit, with an index of zero indicating the low-order bit.
In addition to the methods specified by the interfaces that it implements, BitArray defines the methods shown in Table 25-9. Notice that BitArray does not supply a Synchronized( ) method. Thus, a synchronized wrapper is not available, and the IsSynchronized property is always false. However, you can control access to a BitArray by synchronizing on the object provided by SyncRoot.
TABLE 25-9 The Methods Defined by BitArray
To the properties specified by the interfaces that it implements, BitArray adds Length, which is shown here:
public int Length { get; set; }
Length sets or obtains the number of bits in the collection. Thus, Length gives the same value as does the standard Count property, which is defined for all collections. However, Count is read-only, but Length is not. Thus, Length can be used to change the size of a BitArray. If you shorten a BitArray, bits are truncated from the high-order end. If you lengthen a BitArray, false bits are added to the high-order end.
BitArray defines the following indexer:
public bool this[int index] { get; set; }
You can use this indexer to get or set the value of an element.
Here is an example that demonstrates BitArray:
// Demonstrate BitArray.
using System;
using System.Collections;
class BADemo {
public static void ShowBits(string rem,
BitArray bits) {
Console.WriteLine(rem);
for(int i=0; i < bits.Count; i++)
Console.Write("{0, -6} ", bits[i]);
Console.WriteLine("\n");
}
static void Main() {
BitArray ba = new BitArray(8);
byte[] b = { 67 };
BitArray ba2 = new BitArray(b);
ShowBits("Original contents of ba:", ba);
ba = ba.Not();
ShowBits("Contents of ba after Not:", ba);
ShowBits("Contents of ba2:", ba2);
BitArray ba3 = ba.Xor(ba2);
ShowBits("Result of ba XOR ba2:", ba3);
}
}
The output is shown here:
Original contents of ba:
False False False False False False False False
Contents of ba after Not:
True True True True True True True True
Contents of ba2:
True True False False False False True False
Result of ba XOR ba2:
False False True True True True False True
The .NET Framework provides some specialized collections that are optimized to work on a specific type of data or in a specific way. These non-generic collection classes are defined inside the System.Collections.Specialized namespace. They are synopsized in the following table:
System.Collections also defines three abstract base classes, CollectionBase, ReadOnlyCollectionBase, and DictionaryBase, which can be inherited and used as a starting point for developing custom specialized collections.
The addition of generics greatly expanded the Collections API, essentially doubling the amount of collection classes and interfaces. The generic collections are declared in the System.Collections.Generic namespace. In many cases, the generic collection classes are simply generic equivalents of the non-generic classes discussed earlier. However, the correspondence is not one-to-one. For example, there is a generic collection called LinkedList that implements a doubly linked list, but no non-generic equivalent. In some cases, parallel functionality exists between the generic and non-generic classes, but the names differ. For example, the generic version of ArrayList is called List, and the generic version of Hashtable is called Dictionary. Also, the specific contents of the various interfaces and classes contain minor reorganizations, with some functionality shifting from one interface to another, for example. However, overall, if you understand the non-generic collections, then you can easily use the generic collections.
In general, the generic collections work in the same way as the non-generic collections with the exception that a generic collection is type-safe. Thus, a generic collection can store only items that are compatible with its type argument. Therefore, if you want a collection that is capable of storing unrelated, mixed types, you should use one of the non-generic classes. However, for all cases in which a collection is storing only one type of object, then a generic collection is your best choice.
The generic collections are defined by a set of interfaces and the classes that implement those interfaces. Each is described by the following sections.
System.Collections.Generic defines a number of generic interfaces, all of which parallel their corresponding non-generic counterparts. The generic interfaces are summarized in Table 25-10.
The ICollection<T> interface defines those features that all generic collections have in common. It inherits the IEnumerable and IEnumerable<T> interfaces. ICollection<T> is the generic version of the non-generic ICollection interface. However, there are some differences between the two.
ICollection<T> defines the following properties:
int Count { get; }
bool IsReadOnly { get; }
Count contains the number of items currently held in the collection. IsReadOnly is true if the collection is read-only. It is false if the collection is read/write.
TABLE 25-10 The Generic Collection Interfaces
ICollection<T> defines the following methods. Notice it defines a few more methods than does its non-generic counterpart.
Several of these methods will throw NotSupportedException if the collection is read-only. Because ICollection<T> inherits IEnumerable and IEnumerable<T>, it also includes both the generic and non-generic forms of the method GetEnumerator( ).
Because ICollection<T> implements IEnumerable<T>, it supports the extension methods defined by Enumerable. Although the extension methods were designed mostly for LINQ, they are available for other uses, including collections.
The IList<T> interface defines the behavior of a generic collection that allows elements to be accessed via a zero-based index. It inherits IEnumerable, IEnumerable<T>, and ICollection<T> and is the generic version of the non-generic IList interface. IList<T> defines the methods shown in Table 25-11. Two of these methods imply the modification of a collection. If the collection is read-only or of fixed size, then the Insert( ) and RemoveAt( ) methods will throw a NotSupportedException.
IList<T> defines the following indexer:
T this[int index] { get; set; }
This indexer sets or gets the value of the element at the index specified by index.
TABLE 25-11 The Methods Defined by IList<T>
The IDictionary<TKey, TValue> interface defines the behavior of a generic collection that maps unique keys to values. That is, it defines a collection that stores key/value pairs. IDictionary<TKey, TValue> inherits IEnumerable, IEnumerable<KeyValuePair<TKey, TValue>>, and ICollection<KeyValuePair<TKey, TValue>> and is the generic version of the non-generic IDictionary. The methods declared by IDictionary<TKey, TValue> are summarized in Table 25-12. All throw an ArgumentNullException if an attempt is made to specify a null key.
IDictionary<TKey, TValue> defines the following properties:
Notice that the keys and values contained within the collection are available as separate lists through the Keys and Values properties.
IDictionary<TKey, TValue> defines the following indexer:
TValue this[TKey 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<T> and IEnumerator<T> are the generic equivalents of the non-generic IEnumerable and IEnumerator interfaces described earlier. They declare the same methods and properties, and work in the same way. Of course, the generic versions operate on data of the type specified by the type argument.
TABLE 25-12 The Methods Defined by IDictionary<TKey, TValue>
IEnumerable<T> declares the GetEnumerator( ) method as shown here:
IEnumerator<T> GetEnumerator( )
It returns an enumerator of type T for the collection. Thus, it returns a type-safe enumerator.
IEnumerator<T> has the same two methods as does the non-generic IEnumerator: MoveNext( ) and Reset( ). It also declares a generic version of the Current property, as shown here:
T Current { get; }
It returns a T reference to the next object. Thus, the generic version of Current is type-safe.
There is one other difference between IEnumerator and IEnumerator<T>: IEnumerator<T> inherits the IDisposable interface, but IEnumerator does not. IDisposable defines the Dispose( ) method, which is used to free unmanaged resources.
NOTE IEnumerable<T> also implements the non-generic IEnumerable interface. Thus, it supports the non-generic version of GetEnumerator( ). IEnumerator<T> also implements the non-generic IEnumerator interface, thus supporting the non-generic versions of Current.
The IComparer<T> interface is the generic version of IComparer described earlier. The main difference between the two is that IComparer<T> is type-safe, declaring the generic version of Compare( ) shown here:
int Compare(T x, T y)
This method compares x with y and returns greater than zero if x is greater than y, zero if the two objects are the same, and less than zero if x is less that y.
The IEqualityComparer<T> interface is the equivalent of its non-generic relative IEqualityComparer. It defines these two methods:
bool Equals(T x, T y)
int GetHashCode(T obj)
Equals( ) must return true if x and y are equal. GetHashCode( ) must return the hash code for obj. If two objects compare as equal, then their hash codes must also be the same.
The ISet<T> interface was added by version 4.0 of the .NET Framework. It defines the behavior of a generic collection that implements a set of unique elements. It inherits IEnumerable, IEnumerable<T>, and ICollection<T>. ISet<T> defines the set of methods shown in Table 25-13. Notice that the parameters to these methods are specified as IEnumerable<T>. This means you can pass something other than another ISet<T> as the second set. Most often, however, both arguments will be instances of ISet<T>.
TABLE 25-13 The Set Operations Defined by ISet<T>
System.Collections.Generic defines a structure called KeyValuePair<TKey, TValue>, which is used to store a key and its value. It is used by the generic collection classes that store key/value pairs, such as Dictionary<TKey, TValue>. This structure defines the following two properties:
public TKey Key { get; };
public TValue Value { get; };
These properties hold the key or value associated with an entry. You can construct a KeyValuePair<TKey, TValue> object by using the following constructor:
public KeyValuePair(TKey key, TValue value)
Here, key is the key and value is the value.
As mentioned at the start of this section, the generic collection classes largely parallel their non-generic relatives, although in some cases the names have been changed. Also, some differences in organization and functionality exist. The generic collections are defined in System.Collections.Generic. The ones described in this chapter are shown in Table 25-14. These classes form the core of the generic collections.
NOTE System.Collections.Generic also includes the following classes: SynchronizedCollection<T> is a synchronized collection based on IList<T>. SynchronizedReadOnlyCollection<T> is a read-only synchronized collection based on IList<T>. SynchronizedKeyedCollection<K, T> is an abstract class used as a base class by System.ServiceModel.UriSchemeKeyedCollection. KeyedByTypeCollection<T> is a collection that uses types as keys.
The List<T> class implements a generic dynamic array and is conceptually similar to the non-generic ArrayList class. List<T> implements the ICollection, ICollection<T>, IList, IList<T>, IEnumerable, and IEnumerable<T> interfaces. List<T> has the constructors shown here:
public List( )
public List(IEnumerable<T> collection)
public List(int capacity)
The first constructor builds an empty List with a default initial capacity. The second constructor builds a List that is initialized with the elements of the collection specified by collection and with an initial capacity at least 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 a List<T>. Each time the list must be enlarged, its capacity is increased.
TABLE 25-14 The Core Generic Collection Classes
In addition to the methods defined by the interfaces that it implements, List<T> defines several methods of its own. A sampling is shown in Table 25-15.
TABLE 25-15 A Sampling of Methods Defined by List<T>
In addition to the properties defined by the interfaces that it implements, List<T> adds Capacity, shown here:
public int Capacity { get; set; }
Capacity gets or sets the capacity of the invoking list. The capacity is the number of elements that can be held before the list must be enlarged. Because a list grows automatically, 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.
The following indexer, defined by IList<T>, is implemented by List<T>, as shown here:
public T this[int index] { get; set; }
It sets or gets the value of the element at the index specified by index.
Here is a program that demonstrates List<T>. It reworks the first ArrayList program shown earlier in this chapter. The only changes necessary are to substitute the name List for ArrayList and to use the generic type parameters.
// Demonstrate List<T>.
using System;
using System.Collections.Generic;
class GenListDemo {
static void Main() {
// Create a list.
List<char> lst = new List<char>();
Console.WriteLine("Initial number of elements: " +
lst.Count);
Console.WriteLine();
Console.WriteLine("Adding 6 elements");
// Add elements to the array list
lst.Add('C');
lst.Add('A');
lst.Add('E');
lst.Add('B');
lst.Add('D');
lst.Add('F');
Console.WriteLine("Number of elements: " +
lst.Count);
// Display the list using array indexing.
Console.Write("Current contents: ");
for(int i=0; i < lst.Count; i++)
Console.Write(lst[i] + " ");
Console.WriteLine("\n");
Console.WriteLine("Removing 2 elements");
// Remove elements from the list.
lst.Remove('F');
lst.Remove('A');
Console.WriteLine("Number of elements: " +
lst.Count);
// Use foreach loop to display the list.
Console.Write("Contents: ");
foreach(char c in lst)
Console.Write(c + " ");
Console.WriteLine("\n");
Console.WriteLine("Adding 20 more elements");
// Add enough elements to force lst to grow.
for(int i=0; i < 20; i++)
lst.Add((char)('a' + i));
Console.WriteLine("Current capacity: " +
lst.Capacity);
Console.WriteLine("Number of elements after adding
lst.Count);
Console.Write("Contents: ");
foreach(char c in lst)
Console.Write(c + " ");
Console.WriteLine("\n");
// Change contents using array indexing.
Console.WriteLine("Change first three elements");
lst[0] = 'X';
lst[1] = 'Y';
lst[2] = 'Z';
Console.Write("Contents: ");
foreach(char c in lst)
Console.Write(c + " ");
Console.WriteLine();
// Because of generic type-safety,
// the following line is illegal.
// lst.Add(99); // Error, not a char!
}
}
The output, shown here, is the same as that produced by the non-generic version of the program:
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 rs 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 rs t
The LinkedList<T> class implements a generic doubly linked list. It implements ICollection, ICollection<T>, IEnumerable, IEnumerable<T>, ISerializable, and IDeserializationCallback. (The last two interfaces support the serialization of the list.) LinkedList<T> defines two public constructors, shown here:
public LinkedList( )
public LinkedList(IEnumerable<T> collection)
The first creates an empty linked list. The second creates a list initialized with the elements in collection.
Like most linked list implementations, LinkedList<T> encapsulates the values stored in the list in nodes that contain links to the previous and next element in the list. These nodes are objects of type LinkedListNode<T>. LinkedListNode<T> provides the four properties shown here:
public LinkedListNode<T> Next { get; }
public LinkedListNode<T> Previous { get; }
public LinkedList<T> List { get; }
public T Value { get; set; }
Next and Previous obtain a reference to the next or previous node in the list, respectively. You can use these properties to traverse the list in either direction. A null reference is returned if no next or previous node exists. You can obtain a reference to the list itself via List. You can get or set the value within a node by using Value.
LinkedList<T> defines many methods. A sampling is shown in Table 25-16. In addition to the properties defined by the interfaces that it implements, LinkedList<T> defines these properties:
public LinkedListNode<T> First { get; }
public LinkedListNode<T> Last { get; }
First obtains the first node in the list. Last obtains the last node in the list.
TABLE 25-16 A Sampling of Methods Defined by LinkedList<T>
Here is an example that demonstrates the LinkedList<T> class:
// Demonstrate LinkedList<T>.
using System;
using System.Collections.Generic;
class GenLinkedListDemo {
static void Main() {
// Create a linked list.
LinkedList<char> ll = new LinkedList<char>();
Console.WriteLine("Initial number of elements: " +
ll.Count);
Console.WriteLine();
Console.WriteLine("Adding 5 elements.");
// Add elements to the linked list
ll.AddFirst('A');
ll.AddFirst('B');
ll.AddFirst('C');
ll.AddFirst('D');
ll.AddFirst('E');
Console.WriteLine("Number of elements: " +
ll.Count);
// Display the linked list by manually walking
// through the list.
LinkedListNode<char> node;
Console.Write("Display contents by following links: ");
for(node = ll.First; node != null; node = node.Next)
Console.Write(node.Value + " ");
Console.WriteLine("\n");
//Display the linked list by use of a foreach loop.
Console.Write("Display contents with foreach loop: ");
foreach(char ch in ll)
Console.Write(ch + " ");
Console.WriteLine("\n");
// Display the list backward by manually walking
// from last to first.
Console.Write("Follow links backwards: ");
for(node = ll.Last; node != null; node = node.Previous)
Console.Write(node.Value + " ");
Console.WriteLine("\n");
// Remove two elements.
Console.WriteLine("Removing 2 elements.");
// Remove elements from the linked list.
ll.Remove('C');
ll.Remove('A');
Console.WriteLine("Number of elements: " +
ll.Count);
// Use foreach loop to display the modified list.
Console.Write("Contents after deletion: ");
foreach(char ch in ll)
Console.Write(ch + " ");
Console.WriteLine("\n");
// Add three elements to the end of the list.
ll.AddLast('X');
ll.AddLast('Y');
ll.AddLast('Z');
Console.Write("Contents after addition to end: ");
foreach(char ch in ll)
Console.Write(ch + " ");
Console.WriteLine("\n");
}
}
Here is the output:
Initial number of elements: 0
Adding 5 elements.
Number of elements: 5
Display contents by following links: E D C B A
Display contents with foreach loop: E D C B A
Follow links backwards: A B C D E
Removing 2 elements.
Number of elements: 3
Contents after deletion: E D B
Contents after addition to end: E D B X Y Z
Perhaps the most important thing to notice in this program is that the list is traversed in both the forward and backward direction by following the links provided by the Next and Previous properties. The bidirectional property of doubly linked lists is especially important in applications such as databases in which the ability to move efficiently through the list in both directions is often necessary.
The Dictionary<TKey, TValue> class stores key/value pairs. In a dictionary, values are accessed through their keys. In this regard, it is similar to the non-generic Hashtable class. Dictionary<TKey, TValue> implements IDictionary, IDictionary<TKey, TValue>, ICollection, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable, IEnumerable<KeyValuePair<TKey, TValue>>, ISerializable, and IDeserializationCallback. (The last two interfaces support the serialization of the list.) Dictionaries are dynamic, growing as needed.
Dictionary<TKey, TValue> provides many constructors. Here is a sampling:
public Dictionary( )
public Dictionary(IDictionary<TKey, TValue> dictionary)
public Dictionary(int capacity)
The first constructor creates an empty dictionary with a default capacity. The second creates a dictionary that contains the same elements as those in dictionary. The third lets you specify an initial capacity. If you know in advance that you will need a dictionary of a certain size, then specifying that capacity will prevent the resizing of the dictionary at runtime, which is a costly process.
Dictionary<TKey, TValue> defines several methods. Some commonly used ones are shown in Table 25-17.
TABLE 25-17 Several Commonly Used Methods Defined by Dictionary<TKey, TValue>
In addition to the properties defined by the interfaces that it implements, Dictionary<TKey, TValue> defines these properties:
Notice that the keys and values contained within the collection are available as separate lists through the Keys and Values properties. The types Dictionary<TKey, TValue>.KeyCollection and Dictionary<TKey, TValue>.ValueCollection are collections that implement both the generic and non-generic forms of ICollection and IEnumerable.
The following indexer, defined by IDictionary<TKey, TValue>, is implemented by Dictionary<TKey, TValue> as shown here:
public TValue this[TKey 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.
When enumerating the collection, Dictionary<TKey, TValue> returns key/value pairs in the form of a KeyValuePair<TKey, TValue> structure. Recall that this structure defines the following two properties:
public TKey Key { get; }
public TValue Value { get; }
These properties obtain the key or value associated with an entry. However, most of the time you won’t need to use KeyValuePair<TKey, TValue> directly because Dictionary<TKey, TValue> allows you to work the keys and values individually. However, when enumerating a Dictionary<TKey, TValue>, such as in a foreach loop, the objects being enumerated are KeyValuePairs.
In a Dictionary<TKey, TValue>, all keys must be unique, and a key must not change while it is in use as a key. Values need not be unique. The objects in a Dictionary<TKey, TValue> are not stored in sorted order.
Here is an example that demonstrates Dictionary<TKey, TValue>:
// Demonstrate the generic Dictionary<TKey, TValue> class.
using System;
using System.Collections.Generic;
class GenDictionaryDemo {
static void Main() {
// Create a Dictionary that holds employee
// names and their corresponding salary.
Dictionary<string, double> dict =
new Dictionary<string, double>();
// Add elements to the collection.
dict.Add("Butler, John", 73000);
dict.Add("Swartz, Sarah", 59000);
dict.Add("Pyke, Thomas", 45000);
dict.Add("Frank, Ed", 99000);
// Get a collection of the keys (names).
ICollection<string> c = dict.Keys;
// Use the keys to obtain the values (salaries).
foreach(string str in c)
Console.WriteLine("{0}, Salary: {1:C}", str, dict[str]);
}
}
Here is the output:
Butler, John, Salary: $73,000.00
Swartz, Sarah, Salary: $59,000.00
Pyke, Thomas, Salary: $45,000.00
Frank, Ed, Salary: $99,000.00
The SortedDictionary<TKey, TValue> class stores key/value pairs and is similar to Dictionary<TKey, TValue> except that it is sorted by key. SortedDictionary<TKey, TValue> implements IDictionary, IDictionary<TKey, TValue>, ICollection, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable, and IEnumerable<KeyValuePair<TKey, TValue>>.SortedDictionary<TKey, TValue> provides the following constructors:
public SortedDictionary( )
public SortedDictionary(IDictionary<TKey, TValue> dictionary)
public SortedDictionary(IComparer<TKey> comparer)
public SortedDictionary(IDictionary<TKey, TValue> dictionary,
IComparer<TKey> comparer)
The first constructor creates an empty dictionary. The second creates a dictionary that contains the same elements as those in dictionary. The third lets you specify the IComparer that the dictionary will use for sorting, and the fourth lets you initialize the dictionary and specify the IComparer.
SortedDictionary<TKey, TValue> defines several methods. A sampling is shown in Table 25-18.
TABLE 25-18 A Sampling of Methods Defined by SortedDictionary<TKey, TValue>
In addition to the properties defined by the interfaces that it implements, SortedDictionary<TKey, TValue> defines the following properties:
Notice that the keys and values contained within the collection are available as separate lists through the Keys and Values properties. The types
SortedDictionary<TKey, TValue>.KeyCollection
SortedDictionary<TKey, TValue>.ValueCollection
are collections that implement both the generic and non-generic forms of ICollection and IEnumerable.
SortedDictionary<TKey, TValue> defines the following indexer (which is specified by IDictionary<TKey, TValue>):
public TValue this[TKey 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.
When enumerated, SortedDictionary<TKey, TValue> returns key/value pairs in the form of a KeyValuePair<TKey, TValue> structure. Recall that this structure defines the following two properties:
public TKey Key { get; }
public TValue Value { get; }
These properties obtain the key or value associated with an entry. However, most of the time you won’t need to use KeyValuePair<TKey, TValue> directly because SortedDictionary<TKey, TValue> allows you to work with the keys and values individually. However, when enumerating a SortedDictionary<TKey, TValue>, such as in a foreach loop, the objects being enumerated are KeyValuePairs.
In a SortedDictionary<TKey, TValue>, all keys must be unique, and a key must not change while it is in use as a key. Values need not be unique.
Here is an example that demonstrates SortedDictionary<TKey, TValue>. It reworks the Dictionary<TKey, TValue> example shown in the preceding section. In this version, the database of employees and salaries is sorted based on name (which is the key).
// Demonstrate the generic SortedDictionary<TKey, TValue> class.
using System;
using System.Collections.Generic;
class GenSortedDictionaryDemo {
static void Main() {
// Create a SortedDictionary that holds employee
// names and their corresponding salary.
SortedDictionary<string, double> dict =
new SortedDictionary<string, double>();
// Add elements to the collection.
dict.Add("Butler, John", 73000);
dict.Add("Swartz, Sarah", 59000);
dict.Add("Pyke, Thomas", 45000);
dict.Add("Frank, Ed", 99000);
// Get a collection of the keys (names).
ICollection<string> c = dict.Keys;
// Use the keys to obtain the values (salaries).
foreach(string str in c)
Console.WriteLine("{0}, Salary: {1:C}", str, dict[str]);
}
}
The output is shown here:
Butler, John, Salary: $73,000.00
Frank, Ed, Salary: $99,000.00
Pyke, Thomas, Salary: $45,000.00
Swartz, Sarah, Salary: $59,000.00
As you can see, the list is now sorted based on the key, which is the employee’s name.
The SortedList<TKey, TValue> class stores a sorted list of key/value pairs. It is the generic equivalent of the non-generic SortedList class. SortedList<TKey, TValue> implements IDictionary, IDictionary<TKey, TValue>, ICollection, ICollection< KeyValuePair<TKey, TValue>>, IEnumerable, and IEnumerable< KeyValuePair<TKey, TValue>>. The size of a SortedList<TKey, TValue> is dynamic and will automatically grow as needed. SortedList<TValue, TKey> is similar to SortedDictionary<TKey, TValue> but has different performance characteristics. For example, a SortedList<TKey, TValue> uses less memory, but a SortedDictionary<TKey, TValue> is faster when inserting out-of-order elements.
SortedList<TKey, TValue> provides many constructors. Here is a sampling:
public SortedList( )
public SortedList(IDictionary<TKey, TValue> dictionary)
public SortedList(int capacity)
public SortedList(IComparer<TKey> comparer)
The first constructor creates an empty list with a default capacity. The second creates a list that contains the same elements as those in dictionary. The third lets you specify an initial capacity. If you know in advance that you will need a list of a certain size, then specifying that capacity will prevent the resizing of the list at runtime, which is a costly process. The fourth form lets you specify a comparison method that will be used to compare the objects contained in the list.
The capacity of a SortedList<TKey, TValue> list grows automatically as needed when elements are added to the list. When the current capacity is exceeded, the capacity is increased. The advantage of specifying a capacity is 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<TKey, TValue> also defines several methods of its own. A sampling is shown in Table 25-19. Notice the enumerator returned by GetEnumerator( ) enumerates the key/value pairs stored in the list as objects of type KeyValuePair.
In addition to the properties defined by the interfaces that it implements, SortedList<TKey, TValue> defines the following properties:
SortedList<TKey, TValue> defines the following indexer (which is defined by IDictionary<TKey, TValue>):
public TValue this[TKey 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.
TABLE 25-19 Several Commonly Used Methods Defined by SortedList<TKey, TValue>
Here is an example that demonstrates SortedList<TKey, TValue>. It reworks the employee database example one more time. In this version, the database is stored in a SortedList.
// Demonstrate a SortedList<TKey, TValue>.
using System;
using System.Collections.Generic;
class GenSLDemo {
static void Main() {
// Create a SortedList for
// employee names and salary.
SortedList<string, double> sl =
new SortedList<string, double>();
// Add elements to the collection.
sl.Add("Butler, John", 73000);
sl.Add("Swartz, Sarah", 59000);
sl.Add("Pyke, Thomas", 45000);
sl.Add("Frank, Ed", 99000);
// Get a collection of the keys.
ICollection<string> c = sl.Keys;
// Use the keys to obtain the values.
foreach(string str in c)
Console.WriteLine("{0}, Salary: {1:C}", str, sl[str]);
Console.WriteLine();
}
}
The output is shown here:
Butler, John, Salary: $73,000.00
Frank, Ed, Salary: $99,000.00
Pyke, Thomas, Salary: $45,000.00
Swartz, Sarah, Salary: $59,000.00
As the output shows, the list is sorted based on employee name, which is the key.
Stack<T> is the generic equivalent of the non-generic Stack class. Stack<T> supports a first-in, last-out stack. It implements the ICollection, IEnumerable, and IEnumerable<T> interfaces. Stack<T> directly implements the Clear( ), Contains( ), and CopyTo( ) methods defined by ICollection<T>. (The Add( ) and Remove( ) methods are not supported, nor is the IsReadOnly property.) Stack<T> is a dynamic collection that grows as needed to accommodate the elements it must store. It defines the following constructors:
public Stack( )
public Stack(int capacity)
public Stack(IEnumerable<T> collection)
The first form creates an empty stack with a default initial capacity. 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 collection.
In addition to the methods defined by the interfaces that it implements (and those methods defined by ICollection<T> that it implements on its own), Stack<T> defines the methods shown in Table 25-20. Stack<T> works just like its non-generic counterpart. To put an object on the top of the stack, call Push( ). To remove and return the top element, call Pop( ). You can use Peek( ) to return, but not remove, the top object. An InvalidOperationException is thrown if you call Pop( ) or Peek( ) when the invoking stack is empty.
TABLE 25-20 The Methods De. ned by Stack<T>
The following program demonstrates Stack<T>:
// Demonstrate the Stack<T> class.
using System;
using System.Collections.Generic;
class GenStackDemo {
static void Main() {
Stack<string> st = new Stack<string>();
st.Push("One");
st.Push("Two");
st.Push("Three");
st.Push("Four");
st.Push("Five");
while(st.Count > 0) {
string str = st.Pop();
Console.Write(str + " ");
}
Console.WriteLine();
}
}
The output is shown here:
Five Four Three Two One
Queue<T> is the generic equivalent of the non-generic Queue class. It supports a first-in, first-out list. Queue<T> implements the ICollection, IEnumerable, and IEnumerable<T> interfaces. Queue<T> directly implements the Clear( ), Contains( ), and CopyTo( ) methods defined by ICollection<T>. (The Add( ) and Remove( ) methods are not supported, nor is the IsReadOnly property.) Queue <T> is a dynamic collection that grows as needed to accommodate the elements it must store. It defines the following constructors:
public Queue( )
public Queue(int capacity)
public Queue(IEnumerable<T> collection)
The first form creates an empty queue with an initial default capacity. The second form creates an empty queue with the initial capacity specified by capacity. The third form creates a queue that contains the elements of the collection specified by collection.
In addition to the methods defined by the interfaces that it implements (and those methods defined by ICollection<T> that it implements on its own), Queue<T> defines the methods shown in Table 25-21. Queue<T> works just like its non-generic counterpart. To put an object in the queue, call Enqueue( ). To remove and return the object at the front of the queue, call Dequeue( ). You can use Peek( ) to return, but not remove, the next object. An InvalidOperationException is thrown if you call Dequeue( ) or Peek( ) when the invoking queue is empty.
TABLE 25-21 The Methods Defined by Queue<T>
Here is an example that demonstrates Queue<T>:
// Demonstrate the Queue<T> class.
using System;
using System.Collections.Generic;
class GenQueueDemo {
static void Main() {
Queue<double> q = new Queue<double>();
q.Enqueue(98.6);
q.Enqueue(212.0);
q.Enqueue(32.0);
q.Enqueue(3.1416);
double sum = 0.0;
Console.Write("Queue contents: ");
while(q.Count > 0) {
double val = q.Dequeue();
Console.Write(val + " ");
sum += val;
}
Console.WriteLine("\nTotal is " + sum);
}
}
The output is shown here:
Queue contents: 98.6 212 32 3.1416
Total is 345.7416
HashSet<T> supports a collection that implements a set. It uses a hash table for storage. HashSet<T> implements the ICollection<T>, ISet<T>, IEnumerable, IEnumerable<T>, ISerializable, and IDeserializationCallback interfaces. HashSet<T> implements a set in which all elements are unique. In other words, duplicates are not allowed. The order of the elements is not specified. HashSet<T> implements the full complement of set operations defined by ISet<T>, such as intersection, union, and symmetric difference. This makes HashSet<T> the perfect choice for working with sets of objects when order does not matter. HashSet<T> is a dynamic collection that grows as needed to accommodate the elements it must store.
Here are four commonly used constructors defined by HashSet<T>:
public HashSet( )
public HashSet(IEnumerable<T> collection)
public HashSet(IEqualityComparer comparer)
public HashSet(IEnumerable<T> collection, IEqualityComparer comparer)
The first form creates an empty set. The second creates a set that contains the elements of the collection specified by collection. The third lets you specify the comparer. The fourth creates a set that contains the elements in the collection specified by collection and uses the comparer specified by comparer. There is also a fifth constructor that lets you initialize a set from serialized data.
Because HashSet<T> implements ISet<T>, it provides a complete assortment of set operations. Another set-related method that it provides is RemoveWhere( ), which removes elements that satisfy a specified predicate.
In addition to the properties defined by the interfaces that it implements, HashSet<T> adds Comparer, shown here:
public IEqualityComparer<T> Comparer { get; }
It obtains the comparer for the invoking hash set.
Here is an example that shows HashSet<T> in action:
// Demonstrate the HashSet<T> class.
using System;
using System.Collections.Generic;
class HashSetDemo {
static void Show(string msg, HashSet<char> set) {
Console.Write(msg);
foreach(char ch in set)
Console.Write(ch + " ");
Console.WriteLine();
}
static void Main() {
HashSet<char> setA = new HashSet<char>();
HashSet<char> setB = new HashSet<char>();
setA.Add('A');
setA.Add('B');
setA.Add('C');
setB.Add('C');
setB.Add('D');
setB.Add('E');
Show("Initial content of setA: ", setA);
Show("Initial content of setB: ", setB);
setA.SymmetricExceptWith(setB);
Show("setA after Symmetric difference with SetB: ", setA);
setA.UnionWith(setB);
Show("setA after union with setB: ", setA);
setA.ExceptWith(setB);
Show("setA after subtracting setB: ", setA);
Console.WriteLine();
}
}
The output is shown here:
Initial content of setA: A B C
Initial content of setB: C D E
setA after Symmetric difference with SetB: A B D E
setA after union with setB: A B D E C
setA after subtracting setB: A B
SortedSet<T> is a new collection added to the .NET Framework by version 4.0. It supports a collection that implements a sorted set. SortedSet<T> implements the ISet<T>, ICollection, ICollection<T>, IEnumerable, IEnumerable<T>, ISerializable, and IDeserializationCallback interfaces. SortedSet<T> implements a set in which all elements are unique. In other words, duplicates are not allowed. SortedSet<T> implements the full complement of set operations defined by ISet<T>, such as intersection, union, and symmetric difference. Because SortedSet<T> maintains its elements in sorted order, it is the collection of choice when working with sorted sets. SortedSet<T> is a dynamic collection that grows as needed to accommodate the elements it must store.
Here are four commonly used constructors defined by SortedSet<T>:
public SortedSet( )
public SortedSet(IEnumerable<T> collection)
public SortedSet(IComparer comparer)
public SortedSet(IEnumerable<T> collection, IComparer comparer)
The first form creates an empty set. The second creates a set that contains the elements of the collection specified by collection. The third lets you specify the comparer. The fourth creates a set that contains the elements in the collection specified by collection and uses the comparer specified by comparer. There is also a fifth constructor that lets you initialize a set from serialized data.
Because SortedSet<T> implements ISet<T>, it provides a compete assortment of set operations. Other set-related methods provided by SortedSet<T> include GetViewBetween( ), which returns a portion of a set in the form of a SortedSet<T>, RemoveWhere( ), which removes elements from a set that satisfy a specified predicate, and Reverse( ), which returns an IEnumerable<T> that cycles through the set in reverse order.
In addition to the properties defined by the interfaces that it implements, SortedSet<T> adds those shown here:
public IComparer<T> Comparer { get; }
public T Max { get; }
public T Min { get; }
Comparer obtains the comparer for the invoking set. The Max property obtains the largest value in the set, and Min obtains the smallest value.
To see an example of SortedSet<T> in action, simply substitute SortedSet for HashSet in the program in the preceding section.
The .NET Framework version 4.0 adds a new namespace called System.Collections.Concurrent. It contains collections that are thread-safe and designed to be used for parallel programming. This means they are safe to use in a multithreaded program in which two or more concurrently executing threads might access a collection simultaneously. The concurrent collections are shown here.
Notice that several of the collections implement the IProducerConsumerCollection interface. This interface is also defined in System.Collections.Concurrent. It extends IEnumerable, IEnumerable<T>, and ICollection. It also specifies the TryAdd( ) and TryTake( ) methods that support the producer/consumer pattern. (The classic producer/consumer pattern is characterized by two tasks. One task creates items and the other consumes them.) TryAdd( ) attempts to add an item to the collection, and TryTake( ) attempts to remove an item from the collection. These methods are shown here:
bool TryAdd(T item)
bool TryTake(out T item)
TryAdd( ) returns true if item was added to the collection, and TryTake( ) returns true if an object was removed from the collection. If TryTake( ) is successful, then item will contain the object. (IProducerConsumerCollection also specifies an overload to CopyTo( ) defined by ICollection and ToArray( ) that copies a collection to an array.)
The concurrent collections are often used in conjunction with the Task Parallel Library or PLINQ. Because of the specialized nature of these collections, not every class is examined in detail. However, a brief overview with examples of BlockingCollection<T> will be given. Once you know the basics related to BlockingCollection<T>, the other classes will be easy to understand.
BlockingCollection<T> implements what is essentially a blocking queue. This means that it will automatically wait if an attempt is made to insert an item when the collection is full, and it will automatically wait if an attempt is made to remove an item if the collection is empty. Because of this, it is a perfect solution for those situations that correspond to the producer/consumer pattern. BlockingCollection<T> implements the ICollection, IEnumerable, IEnumerable<T>, and IDisposable interfaces.
BlockingCollection<T> defines the following constructors:
public BlockingCollection( )
public BlockingCollection(int boundedCapacity)
public BlockingCollection(IProducerConsumerCollection<T> collection)
public BlockingCollection(IProducerConsumerCollection<T> collection, int boundedCapacity)
In the first two, the collection that is wrapped by BlockingCollection<T> is an instance of ConcurrentQueue<T>. In the second two, you can specify the collection that you want to underlie the BlockingCollection<T>. If the boundedCapacity parameter is used, it will contain the maximum number of objects that the collection can hold before it blocks. If boundedCapacity is not specified, then the collection is unbounded.
In addition to TryAdd( ) and TryTake( ), which parallel those specified by IProducerConsumerCollection<T>, BlockingCollection<T> defines several methods of its own. The ones we will use are shown here:
public void Add(T item)
public T Take( )
When called on an unbounded collection, Add( ) adds item to the collection and then returns. When called on a bounded collection, Add( ) will block if the collection is full. After one or more items have been removed from the collection, the item will be added and Add( ) will return. Take( ) removes an item from the collection and returns it. If called on an empty collection, Take( ) will block until an item is available. (There are also versions of these methods that take a CancellationToken.)
Using Add( ) and Take( ), you can implement a simple producer/consumer pattern, as demonstrated by the following program. It creates a producer that generates the characters A through Z and a consumer that receives them. Notice that it creates a BlockingCollection<T> that has a bound of 4.
// A simple example of BlockingCollection.
using System;
using System.Threading.Tasks;
using System.Threading;
using System.Collections.Concurrent;
class BlockingDemo {
static BlockingCollection<char> bc;
// Produce the characters A to Z.
static void Producer() {
for(char ch = 'A'; ch <= 'Z'; ch++) {
bc.Add(ch);
Console.WriteLine("Producing " + ch);
}
}
// Consume 26 characters.
static void Consumer() {
for(int i=0; i < 26; i++)
Console.WriteLine("Consuming " + bc.Take());
}
static void Main() {
// Use a blocking collection that has a bound of 4.
bc = new BlockingCollection<char>(4);
// Create the producer and consumer tasks.
Task Prod = new Task(Producer);
Task Con = new Task(Consumer);
// Start the tasks.
Con.Start();
Prod.Start();
// Wait for both to finish.
try {
Task.WaitAll(Con, Prod);
} catch(AggregateException exc) {
Console.WriteLine(exc);
} finally {
Con.Dispose();
Prod.Dispose();
bc.Dispose();
}
}
}
If you run this program, you will see a mix of producer and consumer output. Part of the reason for this is that bc has a bound of 4, which means that only four items can be added to bc before one must be taken off. As an experiment try making bc an unbounded collection and observe the results. In some environments, this will result in all items being produced before any are consumed. Also, try using a bound of 1. In this case, only one item at a time can be produced.
Another method that you may find helpful when working with BlockingCollection<T> is CompleteAdding( ), shown here:
public void CompleteAdding( )
Calling this method indicates that no further items will be added to the collection. This causes the IsAddingComplete property to be true. If the collection is also empty, then the property IsCompleted is true. If IsCompleted is true, then calls to Take( ) will not block.
The IsAddingComplete and IsCompleted properties are shown here:
public bool IsCompleted { get; }
public bool IsAddingComplete { get; }
When a BlockingCollection<T> begins, these properties are false. They become true only after CompleteAdding( ) is called.
The following program reworks the previous example so it uses CompleteAdding( ), IsCompleted, and the TryTake( ) method:
// Using CompleteAdding(), IsCompleted, and TryTake().
using System;
using System.Threading.Tasks;
using System.Threading;
using System.Collections.Concurrent;
class BlockingDemo {
static BlockingCollection<char> bc;
// Produce the characters A to Z.
static void Producer() {
for(char ch = 'A'; ch <= 'Z'; ch++) {
bc.Add(ch);
Console.WriteLine("Producing " + ch);
}
bc.CompleteAdding();
}
// Consume characters until producer is done.
static void Consumer() {
char ch;
while(!bc.IsCompleted) {
if(bc.TryTake(out ch))
Console.WriteLine("Consuming " + ch);
}
}
static void Main() {
// Use a blocking collection that has a bound of 4.
bc = new BlockingCollection<char>(4);
// Create the producer and consumer tasks.
Task Prod = new Task(Producer);
Task Con = new Task(Consumer);
// Start the tasks.
Con.Start();
Prod.Start();
// Wait for both to finish.
try {
Task.WaitAll(Con, Prod);
} catch(AggregateException exc) {
Console.WriteLine(exc);
} finally {
Con.Dispose();
Prod.Dispose();
bc.Dispose();
}
}
}
The output from this version will be similar to that of the previous version. The main difference between the programs is that now Producer( ) can produce as many items as it wants. It simply calls CompleteAdding( ) when it is finished. Consumer( ) simply consumes items until IsCompleted is true.
Although the concurrent collections are somewhat specialized, being designed for concurrent programming situations, they still have much in common with the non-concurrent collections described by the preceding sections. If you are working in a parallel programming environment, you will want to make use of the concurrent collections when access by multiple threads will occur.
For the sake of simplicity, the foregoing examples have stored built-in types, such as int, string, or char, in a collection. Of course, collections are not limited to the storage of built-in objects. Quite the contrary. The power of collections is that they can store any type of object, including objects of classes that you create.
Let’s begin with an example that uses the non-generic class ArrayList to store inventory information that is encapsulated by the Inventory class:
// A simple inventory example.
using System;
using System.Collections;
class Inventory {
string name;
double cost;
int onhand;
public Inventory(string n, double c, int h) {
name = n;
cost = c;
onhand = h;
}
public override string ToString() {
return
String.Format("{0,-10}Cost: {1,6:C} On hand: {2}",
name, cost, onhand);
}
}
class InventoryList {
static void Main() {
ArrayList inv = new ArrayList();
// Add elements to the list
inv.Add(new Inventory("Pliers", 5.95, 3));
inv.Add(new Inventory("Wrenches", 8.29, 2));
inv.Add(new Inventory("Hammers", 3.50, 4));
inv.Add(new Inventory("Drills", 19.88, 8));
Console.WriteLine("Inventory list:");
foreach(Inventory i in inv) {
Console.WriteLine(" " + i);
}
}
}
The output from the program is shown here:
Inventory list:
Pliers Cost: $5.95 On hand: 3
Wrenches Cost: $8.29 On hand: 2
Hammers Cost: $3.50 On hand: 4
Drills Cost: $19.88 On hand: 8
In the program, notice that no special actions were required to store objects of type Inventory in a collection. Because all types inherit object, any type of object can be stored in any non-generic collection. Thus, using a non-generic collection, it is trivially easy to store objects of classes that you create. Of course, it also means the collection is not type-safe.
To store objects of classes that you create in a type-safe collection, you must use one of the generic collection classes. For example, here is a version of the preceding program rewritten to use List<T>. The output is the same as before.
// Store Inventory Objects in a List<T> collection.
using System;
using System.Collections.Generic;
class Inventory {
string name;
double cost;
int onhand;
public Inventory(string n, double c, int h) {
name = n;
cost = c;
onhand = h;
}
public override string ToString() {
return
String.Format("{0,-10}Cost: {1,6:C} On hand: {2}",
name, cost, onhand);
}
}
class TypeSafeInventoryList {
static void Main() {
List<Inventory> inv = new List<Inventory>();
// Add elements to the list
inv.Add(new Inventory("Pliers", 5.95, 3));
inv.Add(new Inventory("Wrenches", 8.29, 2));
inv.Add(new Inventory("Hammers", 3.50, 4));
inv.Add(new Inventory("Drills", 19.88, 8));
Console.WriteLine("Inventory list:");
foreach(Inventory i in inv) {
Console.WriteLine(" " + i);
}
}
}
In this version, notice the only real difference is the passing of the type Inventory as a type argument to List<T>. Other than that, the two programs are nearly identical. The fact that the use of a generic collection requires virtually no additional effort and adds type safety argues strongly for its use when storing a specific type of object within a collection.
In general, there is one other thing to notice about the preceding programs: Both are quite short. When you consider that each sets up a dynamic array that can store, retrieve, and process inventory information in less than 40 lines of code, the power of collections begins to become apparent. As most readers will know, if all of this functionality had to be coded by hand, the program would have been several times longer. Collections offer ready-to-use solutions to a wide variety of programming problems. You should use them whenever the situation warrants.
There is one limitation to the preceding programs that may not be immediately apparent: The collection can’t be sorted. The reason for this is that neither ArrayList nor List<T> has a way to compare two Inventory objects. There are two ways to remedy this situation. First, Inventory can implement the IComparable interface. This interface defines how two objects of a class are compared. Second, an IComparer object can be specified when comparisons are required. The following sections illustrate both approaches.
If you want to sort a collection that contains user-defined objects (or if you want to store those objects in a collection such as SortedList, which maintains its elements in sorted order), then the collection must know how to compare those objects. One way to do this is for the object being stored to implement the IComparable interface. The IComparable interface comes in two forms: generic and non-generic. Although the way each is used is similar, there are some small differences. Each is examined here.
If you want to sort objects that are stored in a non-generic collection, then you will implement the non-generic version of IComparable. This version defines only one method, CompareTo( ), which determines how comparisons are performed. The general form of CompareTo( ) is shown here:
int CompareTo(object obj)
CompareTo( ) compares the invoking object to obj. To sort in ascending order, your implementation must return zero if the objects are equal, a positive value if the invoking object is greater than obj, and a negative value if the invoking object is less than obj. You can sort in descending order by reversing the outcome of the comparison. The method can throw an ArgumentException if the type of obj is not compatible for comparison with the invoking object.
Here is an example that shows how to implement IComparable. It adds IComparable to the Inventory class developed in the preceding section. It implements CompareTo( ) so that it compares the name field, thus enabling the inventory to be sorted by name. By implementing IComparable, it allows a collection of Inventory objects to be sorted, as the program illustrates.
// Implement IComparable.
using System;
using System.Collections;
// Implement the non-generic IComparable interface.
class Inventory : IComparable {
string name;
double cost;
int onhand;
public Inventory(string n, double c, int h) {
name = n;
cost = c;
onhand = h;
}
public override string ToString() {
return
String.Format("{0,-10}Cost: {1,6:C} On hand: {2}",
name, cost, onhand);
}
// Implement the IComparable interface.
public int CompareTo(object obj) {
Inventory b;
b = (Inventory) obj;
return string.Compare(name, b.name, StringComparison.Ordinal);
}
}
class IComparableDemo {
static void Main() {
ArrayList inv = new ArrayList();
// Add elements to the list
inv.Add(new Inventory("Pliers", 5.95, 3));
inv.Add(new Inventory("Wrenches", 8.29, 2));
inv.Add(new Inventory("Hammers", 3.50, 4));
inv.Add(new Inventory("Drills", 19.88, 8));
Console.WriteLine("Inventory list before sorting:");
foreach(Inventory i in inv) {
Console.WriteLine(" " + i);
}
Console.WriteLine();
// Sort the list.
inv.Sort();
Console.WriteLine("Inventory list after sorting:");
foreach(Inventory i in inv) {
Console.WriteLine(" " + i);
}
}
}
Here is the output. Notice after the call to Sort( ), the inventory is sorted by name.
Inventory list before sorting:
Pliers Cost: $5.95 On hand: 3
Wrenches Cost: $8.29 On hand: 2
Hammers Cost: $3.50 On hand: 4
Drills Cost: $19.88 On hand: 8
Inventory list after sorting:
Drills Cost: $19.88 On hand: 8
Hammers Cost: $3.50 On hand: 4
Pliers Cost: $5.95 On hand: 3
Wrenches Cost: $8.29 On hand: 2
If you want to sort objects that are stored in a generic collection, then you will implement IComparable<T>. This version defines the generic form of CompareTo( ) shown here:
int CompareTo(T other)
CompareTo( ) compares the invoking object to other. To sort in ascending order, your implementation must return zero if the objects are equal, a positive value if the invoking object is greater than other, and a negative value if the invoking object is less than other. To sort in descending order, reverse the outcome of the comparison. When implementing IComparable<T>, you will usually pass the type name of the implementing class as a type argument.
The following example reworks the preceding program so that it uses IComparable<T>. Notice it uses the generic List<T> collection rather than the non-generic ArrayList.
// Implement IComparable<T>.
using System;
using System.Collections.Generic;
// Implement the generic IComparable<T> interface
class Inventory : IComparable<Inventory> {
string name;
double cost;
int onhand;
public Inventory(string n, double c, int h) {
name = n;
cost = c;
onhand = h;
}
public override string ToString() {
return
String.Format("{0,-10}Cost: {1,6:C} On hand: {2}",
name, cost, onhand);
}
// Implement the IComparable<T> interface.
public int CompareTo(Inventory other) {
return string.Compare(name, other.name, StringComparison.Ordinal);
}
}
class GenericIComparableDemo {
static void Main() {
List<Inventory> inv = new List<Inventory>();
// Add elements to the list.
inv.Add(new Inventory("Pliers", 5.95, 3));
inv.Add(new Inventory("Wrenches", 8.29, 2));
inv.Add(new Inventory("Hammers", 3.50, 4));
inv.Add(new Inventory("Drills", 19.88, 8));
Console.WriteLine("Inventory list before sorting:");
foreach(Inventory i in inv) {
Console.WriteLine(" " + i);
}
Console.WriteLine();
// Sort the list.
inv.Sort();
Console.WriteLine("Inventory list after sorting:");
foreach(Inventory i in inv) {
Console.WriteLine(" " + i);
}
}
}
This program produces the same output as the previous, non-generic version.
Although implementing IComparable for classes that you create is often the easiest way to allow objects of those classes to be sorted, you can approach the problem in a different way by using IComparer. To use IComparer, first create a class that implements IComparer, and then specify an object of that class when comparisons are required.
There are two versions of IComparer: generic and non-generic. Although the way each is used is similar, there are some small differences, and each approach is examined here.
The non-generic IComparer defines only one method, Compare( ), which is shown here:
int Compare(object x, object y)
Compare( ) compares x to y. To sort in ascending order, your implementation must return zero if the objects are equal, a positive value if x is greater than y, and a negative value if x is less than y. You can sort in descending order by reversing the outcome of the comparison. The method can throw an ArgumentException if the objects are not compatible for comparison.
An IComparer can be specified when constructing a SortedList, when calling ArrayList.Sort(IComparer), and at various other places throughout the collection classes. The main advantage of using IComparer is that you can sort objects of classes that do not implement IComparable.
The following program reworks the non-generic inventory program so that it uses an IComparer to sort the inventory list. It first creates a class called CompInv that implements IComparer and compares two Inventory objects. An object of this class is then used in a call to Sort( ) to sort the inventory list.
// Use IComparer.
using System;
using System.Collections;
// Create an IComparer for Inventory objects.
class CompInv : IComparer {
// Implement the IComparer interface.
public int Compare(object x, object y) {
Inventory a, b;
a = (Inventory) x;
b = (Inventory) y;
return string.Compare(a.name, b.name, StringComparison.Ordinal);
}
}
class Inventory {
public string name;
double cost;
int onhand;
public Inventory(string n, double c, int h) {
name = n;
cost = c;
onhand = h;
}
public override string ToString() {
return
String.Format("{0,-10}Cost: {1,6:C} On hand: {2}",
name, cost, onhand);
}
}
class IComparerDemo {
static void Main() {
CompInv comp = new CompInv();
ArrayList inv = new ArrayList();
// Add elements to the list
inv.Add(new Inventory("Pliers", 5.95, 3));
inv.Add(new Inventory("Wrenches", 8.29, 2));
inv.Add(new Inventory("Hammers", 3.50, 4));
inv.Add(new Inventory("Drills", 19.88, 8));
Console.WriteLine("Inventory list before sorting:");
foreach(Inventory i in inv) {
Console.WriteLine(" " + i);
}
Console.WriteLine();
// Sort the list using an IComparer.
inv.Sort(comp);
Console.WriteLine("Inventory list after sorting:");
foreach(Inventory i in inv) {
Console.WriteLine(" " + i);
}
}
}
The output is the same as the previous version of the program.
The IComparer<T> interface is the generic version of IComparer. It defines the generic version of Compare( ), shown here:
int Compare(T x, T y)
This method compares x with y and returns greater than zero if x is greater than y, zero if the two objects are the same, and less than zero if x is less that y.
Here is a generic version of the preceding program that uses IComparer<T>. It produces the same output as the previous versions of the program.
// Use IComparer<T>.
using System;
using System.Collections.Generic;
// Create an IComparer<T> for Inventory objects.
class CompInv<T> : IComparer<T> where T : Inventory {
// Implement the IComparer<T> interface.
public int Compare(T x, T y) {
return string.Compare(x.name, y.name, StringComparison.Ordinal);
}
}
class Inventory {
public string name;
double cost;
int onhand;
public Inventory(string n, double c, int h) {
name = n;
cost = c;
onhand = h;
}
public override string ToString() {
return
String.Format("{0,-10}Cost: {1,6:C} On hand: {2}",
name, cost, onhand);
}
}
class GenericIComparerDemo {
static void Main() {
CompInv<Inventory> comp = new CompInv<Inventory>();
List<Inventory> inv = new List<Inventory>();
// Add elements to the list.
inv.Add(new Inventory("Pliers", 5.95, 3));
inv.Add(new Inventory("Wrenches", 8.29, 2));
inv.Add(new Inventory("Hammers", 3.50, 4));
inv.Add(new Inventory("Drills", 19.88, 8));
Console.WriteLine("Inventory list before sorting:");
foreach(Inventory i in inv) {
Console.WriteLine(" " + i);
}
Console.WriteLine();
// Sort the list using an IComparer.
inv.Sort(comp);
Console.WriteLine("Inventory list after sorting:");
foreach(Inventory i in inv) {
Console.WriteLine(" " + i);
}
}
}
Although not necessary for the simple examples in this chapter, you may encounter situations when storing strings in a sorted collection, or when sorting or searching strings in a collection, in which you need to explicitly specify how those strings are compared. For example, if strings will be sorted using one cultural setting and searched under another, then explicitly specifying the comparison method may be necessary to avoid errors. A similar situation can exist when a collection uses hashing. To handle these (and other) types of situations, several of the collection class constructors and methods support an IComparer parameter. To explicitly specify the string comparison method, you will pass this parameter an instance of StringComparer.
StringComparer was described in Chapter 21, in the discussion of sorting and searching arrays. It implements the IComparer, IComparer<String>, IEqualityComparer, and IEqualityComparer<String> interfaces. Thus, an instance of StringComparer can be passed to an IComparer parameter as an argument. StringComparer defines several read-only properties that return an instance of StringComparer that supports various types of string comparisons. As described in Chapter 21, they are CurrentCulture, CurrentCultureIgnoreCase, InvariantCulture, InvariantCultureIgnoreCase, Ordinal, and OrdinalIgnoreCase. You can use these properties to explicitly specify the comparison.
For example, here is how to construct a SortedList<TKey, TValue> for strings that use ordinal comparisons for their keys:
SortedList<string, int> users =
new SortedList<string, int>(StringComparer.Ordinal);
Often you will want to cycle through the elements in a collection. For example, you might want to display each element. One way to do this is to use a foreach loop, as the preceding examples have done. Another way is to use an enumerator. An enumerator is an object that implements either the non-generic IEnumerator or the generic IEnumerator<T> interface.
IEnumerator defines one property called Current. The non-generic version is shown here:
object Current { get; }
For IEnumerator<T>, Current is declared like this:
T Current { get; }
In both cases, Current obtains the current element being enumerated. Since Current is a read-only property, an enumerator can only be used to retrieve, but not modify, the objects in a collection.
IEnumerator defines two methods. The first is MoveNext( ):
bool MoveNext( )
Each call to MoveNext( ) moves the current position of the enumerator to the next element in the collection. It returns true if the next element is available, or false if the end of the collection has been reached. Prior to the first call to MoveNext( ), the value of Current is undefined. (Conceptually, prior to the first call to MoveNext( ), the enumerator refers to the nonexistent element that is just before the first element. Thus, you must call MoveNext( ) to move to the first element.)
You can reset the enumerator to the start of the collection by calling Reset( ), shown here:
void Reset( )
After calling Reset( ), enumeration will again begin at the start of the collection. Thus, you must call MoveNext( ) before obtaining the first element.
In IEnumerator<T>, the methods MoveNext( ) and Reset( ) work in the same way.
Two other points: First, you cannot use an enumerator to change the collection that is being enumerated. Thus, enumerators are read-only relative to the collection. Second, any change to the collection under enumeration invalidates the enumerator.
Before you can access a collection through an enumerator, you must obtain one. Each of the collection classes provides a GetEnumerator( ) method that returns an enumerator to the start of the collection. Using this enumerator, you can access each element in the collection, one element at a time. In general, to use an enumerator to cycle through the contents of a collection, follow these steps:
1. Obtain an enumerator to the start of the collection by calling the collection’s GetEnumerator( ) method.
2. Set up a loop that makes a call to MoveNext( ). Have the loop iterate as long as MoveNext( ) returns true.
3. Within the loop, obtain each element through Current.
Here is an example that implements these steps. It uses an ArrayList, but the general principles apply to any type of collection, including the generic collections.
// Demonstrate an enumerator.
using System;
using System.Collections;
class EnumeratorDemo {
static void Main() {
ArrayList list = new ArrayList(1);
for(int i=0; i < 10; i++)
list.Add(i);
// Use enumerator to access list.
IEnumerator etr = list.GetEnumerator();
while(etr.MoveNext())
Console.Write(etr.Current + " ");
Console.WriteLine();
// Re–enumerate the list.
etr.Reset();
while(etr.MoveNext())
Console.Write(etr.Current + " ");
Console.WriteLine();
}
}
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
In general, when you need to cycle through a collection, a foreach loop is more convenient to use than an enumerator. However, an enumerator gives you a little extra control by allowing you to reset the enumerator at will.
When using a non-generic IDictionary, such as Hashtable, you will use an IDictionaryEnumerator instead of an IEnumerator when cycling through the collection. The IDictionaryEnumerator inherits IEnumerator and adds three properties. The first is
DictionaryEntry Entry { get; }
Entry obtains the next key/value pair from the enumerator in the form of a DictionaryEntry structure. Recall that DictionaryEntry defines two properties, called Key and Value, which can be used to access the key or value contained within the entry. The other two properties defined by IDictionaryEnumerator are shown here:
object Key { get; }
object Value { get; }
These allow you to access the key or value directly.
An IDictionaryEnumerator is used just like a regular enumerator, except that you will obtain the current value through the Entry, Key, or Value properties rather than Current. Thus, after obtaining an IDictionaryEnumerator, you must call MoveNext( ) to obtain the first element. Continue to call MoveNext( ) to obtain the rest of the elements in the collection. MoveNext( ) returns false when there are no more elements.
Here is an example that enumerates the elements in a Hashtable through an IDictionaryEnumerator:
// Demonstrate IDictionaryEnumerator.
using System;
using System.Collections;
class IDicEnumDemo {
static void Main() {
// Create a hash table.
Hashtable ht = new Hashtable();
// Add elements to the table.
ht.Add("Tom", "555–3456");
ht.Add("Mary", "555–9876");
ht.Add("Todd", "555–3452");
ht.Add("Ken", "555–7756");
// Demonstrate enumerator.
IDictionaryEnumerator etr = ht.GetEnumerator();
Console.WriteLine("Display info using Entry.");
while(etr.MoveNext())
Console.WriteLine(etr.Entry.Key + ": " +
etr.Entry.Value);
Console.WriteLine();
Console.WriteLine("Display info using Key and Value directly.");
etr.Reset();
while(etr.MoveNext())
Console.WriteLine(etr.Key + ": " +
etr.Value);
}
}
The output is shown here:
Display info using Entry.
Ken: 555–7756
Mary: 555–9876
Tom: 555–3456
Todd: 555–3452
Display info using Key and Value directly.
Ken: 555–7756
Mary: 555–9876
Tom: 555–3456
Todd: 555–3452
As mentioned earlier, normally it is easier (and better) to use a foreach loop to cycle through a collection than it is to explicitly use IEnumerator methods. However, understanding the operation of this interface is important for another reason: If you want to create a class that contains objects that can be enumerated via a foreach loop, then that class must implement IEnumerator. It must also implement IEnumerable. In other words, to enable an object of a class that you create to be used in a foreach loop, you must implement IEnumerator and IEnumerable, using either their generic or non-generic form. Fortunately, because these interfaces are so small, they are easy to implement.
Here is an example that implements the non-generic versions of IEnumerable and IEnumerator so that the contents of the array encapsulated within MyClass can be enumerated:
// Implement IEnumerable and IEnumerator.
using System;
using System.Collections;
class MyClass : IEnumerator, IEnumerable {
char[] chrs = { 'A', 'B', 'C', 'D' };
int idx = -1;
// Implement IEnumerable.
public IEnumerator GetEnumerator() {
return this;
}
// The following methods implement IEnumerator.
// Return the current object.
public object Current {
get {
return chrs[idx];
}
}
// Advance to the next object.
public bool MoveNext() {
if(idx == chrs.Length-1) {
Reset(); // reset enumerator at the end
return false;
}
idx++;
return true;
}
// Reset the enumerator to the start.
public void Reset() { idx = -1; }
}
class EnumeratorImplDemo {
static void Main() {
MyClass mc = new MyClass();
// Display the contents of mc.
foreach(char ch in mc)
Console.Write(ch + " ");
Console.WriteLine();
// Display the contents of mc, again.
foreach(char ch in mc)
Console.Write(ch + " ");
Console.WriteLine();
}
}
Here is the output:
A B C D
A B C D
In the program, first examine MyClass. It encapsulates a small char array that contains the characters A through D. An index into this array is stored in idx, which is initialized to –1. MyClass then implements both IEnumerator and IEnumerable.GetEnumerator( ) returns a reference to the enumerator, which in this case is the current object. The Current property returns the next character in the array, which is the object at idx. The MoveNext( ) method advances idx to the next location. It returns false if the end of the collection has been reached and true otherwise. Reset( ) sets idx to –1. Recall that an enumerator is undefined until after the first call to MoveNext( ). Thus, in a foreach loop, MoveNext( ) is automatically called before Current. This is why idx must initially be –1; it is advanced to zero when the foreach loop begins. A generic implementation would work in a similar fashion.
Inside Main( ), an object of type MyClass called mc is created and the contents of the object are twice displayed by use of a foreach loop.
As the preceding example shows, it is not difficult to implement IEnumerator and IEnumerable. However, it can be made even easier through the use of an iterator. An iterator is a method, operator, or accessor that returns the members of a set of objects, one member at a time, from start to finish. For example, assuming some array that has five elements, then an iterator for that array will return those five elements, one at a time. Implementing an iterator is another way to make it possible for an object of a class to be used in a foreach loop.
Let’s begin with an example of a simple iterator. The following program is a modified version of the preceding program that uses an iterator rather than explicitly implementing IEnumerator and IEnumerable.
// A simple example of an iterator.
using System;
using System.Collections;
class MyClass {
char[] chrs = { 'A', 'B', 'C', 'D' };
// This iterator returns the characters
// in the chrs array.
public IEnumerator GetEnumerator() {
foreach(char ch in chrs)
yield return ch;
}
}
class ItrDemo {
static void Main() {
MyClass mc = new MyClass();
foreach(char ch in mc)
Console.Write(ch + " ");
Console.WriteLine();
}
}
A B C D
As you can see, the contents of mc.chrs was enumerated.
Let’s examine this program carefully. First, notice that MyClass does not specify IEnumerator as an implemented interface. When creating an iterator, the compiler automatically implements this interface for you. Second, pay special attention to the GetEnumerator( ) method, which is shown again here for your convenience:
// This iterator returns the characters
// in the chrs array.
public IEnumerator GetEnumerator() {
foreach(char ch in chrs)
yield return ch;
}
This is the iterator for MyClass. Notice that it implicitly implements the GetEnumerator( ) method defined by IEnumerable. Now, look at the body of the method. It contains a foreach loop that returns the elements in chrs. It does this through the use of a yield return statement. The yield return statement returns the next object in the collection, which in this case is the next character in chrs. This feature enables mc (a MyClass object) to be used within the foreach loop inside Main( ).
The term yield is a contextual keyword in the C# language. This means that it has special meaning only inside an iterator block. Outside of an iterator, yield can be used like any other identifier.
One important point to understand is that an iterator does not need to be backed by an array or other type of collection. It simply must return the next element in a group of elements. This means the elements can be dynamically constructed using an algorithm. For example, here is a version of the previous program that returns all uppercase letters in the alphabet. Instead of using an array, it generates the letters using a for loop.
// Iterated values can be dynamically constructed.
using System;
using System.Collections;
class MyClass {
char ch = 'A';
// This iterator returns the letters of the alphabet.
public IEnumerator GetEnumerator() {
for(int i=0; i < 26; i++)
yield return (char) (ch + i);
}
}
class ItrDemo2 {
static void Main() {
MyClass mc = new MyClass();
foreach(char ch in mc)
Console.Write(ch + " ");
Console.WriteLine();
}
}
The output is shown here:
A B C D E F G H I J K L M N O P Q Rs T U V W X Y Z
You can stop an iterator early by using this form of the yield statement:
yield break;
When this statement executes, the iterator signals that the end of the collection has been reached, which effectively stops the iterator.
The following program modifies the preceding program so that it displays only the first ten letters in the alphabet.
// Use yield break.
using System;
using System.Collections;
class MyClass {
char ch = 'A';
// This iterator returns the first 10
// letters of the alphabet.
public IEnumerator GetEnumerator() {
for(int i=0; i < 26; i++) {
if(i == 10) yield break; // stop iterator early
yield return (char) (ch + i);
}
}
}
class ItrDemo3 {
static void Main() {
MyClass mc = new MyClass();
foreach(char ch in mc)
Console.Write(ch + " ");
Console.WriteLine();
}
}
The output is shown here:
A B C D E F G H I J
You can have more than one yield statement in an iterator. However, each yield must return the next element in the collection. For example, consider this program:
// Multiple yield statements are allowed.
using System;
using System.Collections;
class MyClass {
// This iterator returns the letters
// A, B, C, D, and E.
public IEnumerator GetEnumerator() {
yield return 'A';
yield return 'B';
yield return 'C';
yield return 'D';
yield return 'E';
}
}
class ItrDemo5 {
static void Main() {
MyClass mc = new MyClass();
foreach(char ch in mc)
Console.Write(ch + " ");
Console.WriteLine();
}
}
The output is shown here:
A B C D E
Inside GetEnumerator( ), five yield statements occur. The important thing to understand is that they are executed one at a time, in order, each time another element in the collection is obtained. Thus, each time through the foreach loop in Main( ), one character is returned.
Although the preceding examples have shown the easiest way to implement an iterator, there is an alternative: the named iterator. In this approach, you create a method, operator, or accessor that returns a reference to an IEnumerable object. Your code will use this object to supply the iterator. A named iterator is a method with the following general form:
public IEnumerable itr-name(param-list) {
// ...
yield return obj;
}
Here, itr-name is the name of the method, param-list specifies zero or more parameters that will be passed to the iterator method, and obj is the next object returned by the iterator. Once you have created a named iterator, you can use it anywhere that an iterator is needed. For example, you can use the named iterator to control a foreach loop.
Named iterators are very useful in some circumstances because they allow you to pass arguments to the iterator that control what elements are obtained. For example, you might pass the iterator the beginning and ending points of a range of elements to iterate. This form of iterator can also be overloaded, further adding to its flexibility. The following program illustrates two ways that a named iterator can be used to obtain elements. The first enumerates a range of elements given the endpoints. The second enumerates the elements beginning at the start of the sequence and ending at the specified stopping point.
// Use named iterators.
using System;
using System.Collections;
class MyClass {
char ch = 'A';
// This iterator returns the letters
// of the alphabet, beginning at A and
// stopping at the specified stopping point.
public IEnumerable MyItr(int end) {
for(int i=0; i < end; i++)
yield return (char) (ch + i);
}
// This iterator returns the specified
// range of letters.
public IEnumerable MyItr(int begin, int end) {
for(int i=begin; i < end; i++)
yield return (char) (ch + i);
}
}
class ItrDemo4 {
static void Main() {
MyClass mc = new MyClass();
Console.WriteLine("Iterate the first 7 letters:");
foreach(char ch in mc.MyItr(7))
Console.Write(ch + " ");
Console.WriteLine("\n");
Console.WriteLine("Iterate letters from F to L:");
foreach(char ch in mc.MyItr(5, 12))
Console.Write(ch + " ");
Console.WriteLine();
}
}
Iterate the first 7 letters:
A B C D E F G
Iterate letters from F to L:
F G H I J K L
The preceding examples of iterators have been non-generic, but it is, of course, also possible to create generic iterators. Doing so is quite easy: Simply return an object of the generic IEnumerator<T> or IEnumerable<T> type. Here is an example that creates a generic iterator:
// A simple example of a generic iterator.
using System;
using System.Collections.Generic;
class MyClass<T> {
T[] array;
public MyClass(T[] a) {
array = a;
}
// This iterator returns the characters
// in the chrs array.
public IEnumerator<T> GetEnumerator() {
foreach(T obj in array)
yield return obj;
}
}
class GenericItrDemo {
static void Main() {
int[] nums = { 4, 3, 6, 4, 7, 9 };
MyClass<int> mc = new MyClass<int>(nums);
foreach(int x in mc)
Console.Write(x + " ");
Console.WriteLine();
bool[] bVals = { true, true, false, true };
MyClass<bool> mc2 = new MyClass<bool>(bVals);
foreach(bool b in mc2)
Console.Write(b + " ");
Console.WriteLine();
}
}
4 3 6 4 7 9
True True False True
In this example, the array containing the objects to be iterated is passed to MyClass through its constructor. The type of the array is specified as a type argument to MyClass. The GetEnumerator( ) method operates on data of type T and returns an IEnumerator<T> enumerator. Thus, the iterator defined by MyClass can enumerate any type of data.
C# includes a feature called the collection initializer, which makes it easier to initialize certain collections. Instead of having to explicitly call Add( ), you can specify a list of initializers when a collection is created. When this is done, the compiler automatically calls Add( ) for you, using these values. The syntax is similar to an array initialization. Here is an example. It creates a List<char> that is initialized with the characters C, A, E, B, D, and F.
List<char> lst = new List<char>() { 'C', 'A', 'E', 'B', 'D', 'F' };
After this statement executes, lst.Count will equal 6, because there are six initializers, and this foreach loop
foreach(ch in lst)
Console.Write(ch + " ");
will display
C A E B D F
When using a collection such as LinkedList<TKey, TValue> that stores key/value pairs, you will need to supply pairs of initializers, as shown here:
SortedList<int, string> lst =
new SortedList<int, string>() { {1, "One"}, {2, "Two" }, {3, "Three"} };
The compiler passes each group of values as arguments to Add( ). Thus, the first pair of initializers is translated into a call to Add(1, “One”) by the compiler.
Because the compiler automatically calls Add( ) to add initializers to a collection, collection initializers can be used only with collections that support a public implementation of Add( ). Therefore, collection initializers cannot be used with the Stack, Stack<T>, Queue, or Queue<T> collections because they don't support Add( ). You also can’t use a collection initializer with a collection such as LinkedList<T>, which provides Add( ) as an explicit interface implementation.
