Chapter 14
Collection Classes

What’s in This Chapter

  • Arrays and array objects
  • Collection classes
  • Generic collections
  • Collection initialization
  • Iterators

Wrox.com Downloads for This Chapter

Please note that all the code examples for this chapter are available as a part of this chapter’s code download on the book’s website at www.wrox.com/go/csharp5programmersref on the Download Code tab.

Many applications must store and manipulate groups of objects. For example, an application might need to manage a group of Customers, Orders, Students, or Invoices.

An array lets you store a group of objects. Unfortunately, arrays don’t let you easily rearrange the objects. For example, to add an object at the end of an array in C#, you need to create a new array that’s one position bigger than the old array, copy the existing items into the new array, add the new item, and then set the reference to the old array equal to the new one. Adding or removing an item from the beginning or middle of an array is even more time-consuming.

Because these sorts of operations are common, many algorithms have been devised over the years to make them easier. The .NET Framework includes an assortment of collection classes that implement those algorithms, so you don’t have to do it yourself.

This chapter describes collection classes provided by the Framework. It explains how you can use them to store and manipulate groups of objects and provides tips for selecting the right collection for different purposes. The following section starts by describing the simplest kind of collection: the array.

Arrays

C# provides two basic kinds of arrays. First, it provides the normal arrays that you get when you use the new keyword and brackets surrounding the number of items the array should hold. For example, the following code declares an array of int named squares and initializes it to contain 10 entries.

int[] squares = new int[10];

The C# Array class provides another kind of array. This kind is actually an object that provides methods for managing the items stored in the array.

The following code shows the previous version of the code rewritten to use an Array object:

Array squares = Array.CreateInstance(typeof(int), 10); 

This version creates the array by passing to the static Array.CreateInstance method the data type the array should contain and the number of items that it should hold.

One of the nice features of the Array class is that it provides methods that also work on normal arrays. For example, if values is an ordinary array of strings, then the statement Array.Sort(values) sorts the strings in the array.

The following sections provide more details about arrays and the Array class.

Dimensions

Both normal arrays and Array objects can support multiple dimensions. The following statement declares a three-dimensional array with 10 items in the first dimension, 5 in the second, and 20 in the third. It then sets the value for the item in position (1, 2, 3).

int[, ,] values = new int[10, 5, 20];
values[1, 2, 3] = 123;

The following code does the same thing with an Array object.

Array values = Array.CreateInstance(typeof(int), 10, 5, 20);
values.SetValue(123, 1, 2, 3);

Lower Bounds

A normal array always has lower bound 0 in every dimension. For example, the previous array had dimensions 0 through 9, 0 through 4, and 0 through 19.

You can pretend an array has nonzero lower bounds, but it requires extra work on your part. You must add or subtract an appropriate amount from each index to map the indexes you want to use to the underlying zero-based indexes.

Array objects can handle nonzero lower bounds for you. Pass the CreateInstance method the array’s data type, an array giving the lengths of each dimension, and an array giving each dimension’s lower bounds.

For example, suppose you want to store quarterly sales data for the years 2001 through 2010. The following code creates a two-dimensional array with indexes ranging from 2001 to 2010 in the first dimension and 1 to 4 in the second dimension.

int[] lengths = {10, 4};
int[] lowerBounds = {2001, 1};
Array sales = Array.CreateInstance(typeof(decimal), lengths, lowerBounds);
sales.SetValue(10000m, 2005, 3);

The code first defines an array containing the number of elements for each dimension (10 in the first dimension and 4 in the second). Next, it creates an array containing the lower bounds for each dimension. (The first dimension starts with index 2001 and the second starts with index 1.)

The code then calls Array.CreateInstance, passing it the int data type, the array of lengths, and the array of lower bounds. The code finishes by setting the value for the third quarter in the year 2005 to 10,000.

Resizing

To resize an array, you need to allocate a new array, copy any items that you want to preserve into it, and then set the reference to the original array equal to the new one. For example, the following code adds the value 5 to the end of an array.

// Create the initial array.
int[] values = { 0, 1, 2, 3, 4 };

// Add the value 5 at the end.
int[] newValues = new int[6];
for (int i = 0; i < values.Length; i++)
    newValues[i] = values[i];
newValues[5] = 5;
values = newValues;

Like a normal array, an Array object cannot resize. However, the Array class’s CopyTo method makes it relatively easy to copy items from one Array to another. For example, the following code is similar to the preceding code except it uses Array objects instead of ordinary arrays.

// Create the initial array.
Array values = Array.CreateInstance(typeof(int), 5);
for (int i = 0; i < values.Length; i++) values.SetValue(i, i);

// Add the value 5 at the end.
Array newValues = Array.CreateInstance(typeof(int), 6);
values.CopyTo(newValues, 0);
newValues.SetValue(5, 5);
values = newValues;

The Array class’s static Copy method allows you even greater control. It lets you specify the index in the source array where the copy should start, the index in the destination array where the items should be copied, and the number of items to be copied.

One of the nice things about the Array class’s methods is that many of them also work with normal arrays. For example, the following code shows the earlier code for extending a normal array, but this version uses the Array.Copy method (highlighted in bold) instead of copying items with a for loop.

// Create the initial array.
int[] values = { 0, 1, 2, 3, 4 };

// Add the value 5 at the end.
int[] newValues = new int[6];
Array.Copy(values, newValues, 5);
newValues[5] = 5;
values = newValues;

This code is still rather long, but the Array.Copy method is quite fast, so the code is fairly efficient.

Speed

There’s no doubt that arrays of variables are much faster than Array objects. In one test, setting and getting values in an Array object took more than 20 times as long as performing the same operations in a variable array.

Microsoft has also optimized one-dimensional arrays, so they are faster than multidimensional arrays. The difference is much less dramatic than the difference between arrays and the Array class, however.

If your application performs only a few hundred array operations, the difference is unimportant. If your application must access array values many millions of times, you may need to consider using an array of variables even if the Array class would be more convenient for other reasons (such as nonzero lower bounds).

Example program ArraySpeeds, which is available for download on this book’s website, compares the speeds of variable arrays and Array objects. Enter the number of items that you want to use in the arrays, and click Go. The program builds one- and two-dimensional arrays and Array objects holding the same number of integers. It then fills the arrays for a large number of trials and displays the elapsed time.

Figure 14-1 shows the results. Variable arrays are much faster than Array objects, and one-dimensional variable arrays generally seem to be slightly faster than two-dimensional arrays.

c14f001.tif

Figure 14-1: Variable arrays are faster than Array objects.

Other Array Class Features

The Array class provides several other useful static methods that work with both arrays and Arrays. For example, the IndexOf and LastIndexOf methods return the position of a particular item in an Array.

The following table summarizes some of the most useful Array class methods.

Property/MethodPurpose
BinarySearchReturns the index of an item in the previously sorted array. The items must implement the IComparable interface, or you must provide an IComparer object.
ClearRemoves all the items from the array.
ConvertAllConverts an array of one type into an array of another type.
CopyCopies some or all the items from a position in one array to a position in another.
ExistsDetermines whether the array contains a particular item.
IndexOfReturns the index of the first item with a given value.
LastIndexOfReturns the index of the last item with a given value.
ResizeResizes the array.
ReverseReverses the order of the items in the array.
SortSorts the items in the array. The items must implement the IComparable interface, or you must provide an IComparer object.

System.Collections

The collection classes in the System.Collections namespace basically hold items and don’t provide a lot of extra functionality. Other classes described later in this chapter are more powerful, so you should generally use them.

The following sections describe the ArrayList, StringCollection, and NameValueCollection classes.

ArrayList

The System.Collections.ArrayList class represents a resizable array implemented internally as a list. You can add and remove items from any position in the list and it resizes itself accordingly. The following table describes some of the class’s more useful properties and methods.

Property/MethodPurpose
AddAdds an item at the end of the list.
AddRangeAdds the items in an object that implements the ICollection interface to the end of the list.
BinarySearchReturns the index of an item in the previously sorted list. The items must implement the IComparable interface, or you must provide the method with an IComparer object.
CapacityGets or sets the number of items that the list can hold.
ClearRemoves all the items from the list.
ContainsReturns true if a specified item is in the list.
CopyToCopies some of the list or the entire list into a one-dimensional Array object.
CountReturns the number of items currently in the list. This is always less than or equal to Capacity.
GetRangeReturns an ArrayList containing the items in part of the list.
IndexOfReturns the zero-based index of the first occurrence of a specified item in the list.
InsertAdds an item at a particular position in the list.
InsertRangeAdds the items in an object that implements the ICollection interface to a particular position in the list.
ItemReturns the item at a particular position in the list.
LastIndexOfReturns the zero-based index of the last occurrence of a specified item in the list.
RemoveRemoves the first occurrence of a specified item from the list.
RemoveAtRemoves the item at the specified position in the list.
RemoveRangeRemoves the items in the specified positions from the list.
ReverseReverses the order of the items in the list.
SetRangeReplaces the items in part of the list with new items taken from an ICollection object.
SortSorts the items in the list. The items must implement the IComparable interface, or you must provide the method with an IComparer object.
ToArrayCopies the list’s items into a one-dimensional array. The array can be an array of objects, an array of a specific type, or an Array object (holding objects).
TrimToSizeReduces the list’s allocated space so that it is just big enough to hold its items. This sets Capacity = Count.

A single ArrayList object can hold objects of many different kinds. For example, the following code creates an ArrayList, adds several items of different types to it, and then loops through the list displaying the values.

ArrayList list = new ArrayList();
list.Add("What?");
list.Add(this);
list.Add(7331);
list.Add(new Bitmap(32, 32));
foreach (object obj in list)
    Console.WriteLine(obj.ToString());

The following text shows the result.

What?
WindowsFormsApplication1.Form1, Text: Form1
7331
System.Drawing.Bitmap

StringCollection

The System.Collections.Specialized namespace’s StringCollection class is similar to ArrayList, except that it can hold only strings. Because it works only with strings, this class provides some extra type checking that the ArrayList does not. For example, if your program tries to add an Employee object or Bitmap to a StringCollection, the collection throws an exception.

A StringCollection can hold duplicate values and null values.

The following code shows how the UseStringCollection example program, which is available for download on the book’s website, demonstrates a StringCollection.

// The values.
private StringCollection Values = new StringCollection();

// Add a value to the collection.
private void addButton_Click(object sender, EventArgs e)
{
    Values.Add(valueTextBox.Text);
    valueTextBox.Clear();
    valueTextBox.Focus();
    ListValues();
}

// Display the name/values groups.
private void ListValues()
{
    valueListBox.Items.Clear();
    foreach (string value in Values)
    {
        valueListBox.Items.Add(value);
    }
}

The code starts by creating a new StringCollection. When you enter a string in the TextBox and click Add, the button’s Click event handler adds the value to the StringCollection and calls the ListValues method to display the collection’s values. The ListValues method loops through the collection’s values and displays them in the program’s ListBox.

To take advantage of this extra error checking, you should always use a StringCollection instead of an ArrayList if you are working with strings. Of course, if you need other features (such as the fast lookups provided by a Dictionary), you should use one of the classes described in the following sections.

NameValueCollection

The System.Collections.Specialized namespace’s NameValueCollection class is a collection that can hold more than one string value for a particular key (the value’s “name”). For example, you might use people’s names as keys. The strings associated with a particular key could include the postal address, phone number, e-mail address, and so forth.

Of course, you could also store the same information by putting the postal address, phone number, e-mail address, and other fields in an object or structure, and then storing the objects or structures in some sort of collection class such as an ArrayList. A NameValueCollection, however, is useful if you don’t know ahead of time how many strings will be associated with each key.

The following code shows how the UseNameValueCollection example program, which is available for download on the book’s website, demonstrates a NameValueCollection.

// The NameValueCollection.
private NameValueCollection Values = new NameValueCollection();

// Add a new name/value.
private void addButton_Click(object sender, EventArgs e)
{
    Values.Add(nameTextBox.Text, valueTextBox.Text);
    valueTextBox.Clear();
    valueTextBox.Focus();
    ListValues();
}

// Display the name/values groups.
private void ListValues()
{
    valueListBox.Items.Clear();
    foreach (string key in Values.AllKeys)
    {
        valueListBox.Items.Add(key + ": " + Values[key]);
    }
}

The code starts by declaring a NameValueCollection. If you enter name and value in the program’s TextBoxes and click Add, the program’s Click event handler adds the name/value pair to the collection. It then calls the ListValues method to display the current list of names and values.

The ListValues method loops through the keys in the collection and displays them together with their values. The values are shown separated by commas. For example, if you add the values Eggs, Toast, and Juice to the name Breakfast, then the ListBox displays the text “Breakfast: Eggs,Toast,Juice.”

The following table describes some of the NameValueCollection class’s most useful properties and methods.

Property/MethodDescription
AddAdds a new name/value pair to the collection. If the collection already holds an entry for the name, it adds the new value to that name’s values.
AllKeysReturns a string array holding all the key values.
ClearRemoves all names and values from the collection.
CopyToCopies items starting at a particular index into a one-dimensional Array object. This copies only the items, not the keys.
CountReturns the number of keys in the collection.
GetGets the items for a particular index or name as a comma-separated list of values.
GetKeyReturns the key for a specific index.
GetValuesReturns a string array containing the values for a specific name or index.
HasKeysReturns true if the collection contains any non-null keys.
KeysReturns a collection containing the keys.
RemoveRemoves a particular name and all its values.
SetSets the item for a particular name.

Note that there is no easy way to remove a particular value from a name. For example, if a person’s name is associated with a postal address, phone number, and e-mail address, it is not easy to remove only the phone number. Instead you must remove the name and add it again omitting the value you want to remove.

Dictionaries

A dictionary is a collection that associates keys with values. You look up a key, and the dictionary provides you with the corresponding value. This is similar to the way a NameValueCollection works, except a dictionary’s keys and values need not be strings, and a dictionary associates each key with a single value.

The System.Collections.Specialized namespace contains several different kinds of dictionary classes that are optimized for different uses. Their differences come largely from the ways in which they store data internally. Although you don’t need to understand the details of how the dictionaries work internally, you do need to know how they behave so that you can pick the best one for a particular purpose.

Because all the dictionary classes provide the same service (associating keys with values), they have roughly the same properties and methods. The following table describes the most useful.

Property/MethodDescription
AddAdds a key/value pair to the dictionary.
ClearRemoves all key/value pairs from the dictionary.
ContainsReturns true if the dictionary contains a specific key.
CopyToCopies the dictionary’s data starting at a particular position into a one-dimensional array of DictionaryEntry objects. The DictionaryEntry class has Key and Value properties.
CountReturns the number of key/value pairs in the dictionary.
ItemGets or sets the value associated with a key.
KeysReturns a collection containing all the dictionary’s keys.
RemoveRemoves the key/value pair with a specific key.
ValuesReturns a collection containing all the dictionary’s values.

You can index a dictionary much as you can index an array. For example, the following code creates a ListDictionary, adds the value Apple pie with the key dessert, and then displays that value in a message box.

ListDictionary dict = new ListDictionary();
dict["dessert"] = "Apple pie";
MessageBox.Show((string)dict["dessert"]);

Notice how the code uses ["dessert"] as the index for the dictionary.

The dictionary treats all its keys and values as plain objects, so the code must convert the result into a string before displaying it in the message box.

The following sections describe different dictionary classes in more detail.

ListDictionary

A ListDictionary is a dictionary that stores its data in a linked list. In a linked list, each item is held in an object that contains its data plus a reference (or link) to the next item in the list.

Figure 14-3 illustrates a linked list. This list contains the key/value pairs Appetizer/Salad, Entrée/Sandwich, Drink/Water, and Dessert/Cupcake. The link out of the Dessert/Cupcake item is set to null, so the program can tell when it has reached the end of the list. A reference variable inside the ListDictionary class, labeled Top in Figure 14-3, points to the first item in the list.

c14f003.eps

Figure 14-3: Each item in a linked list holds a reference to the next item in the list.

The links in a linked list make adding and removing items relatively easy. The ListDictionary simply rearranges the links to add or remove objects. For example, to add a new item at the top of the list, you create the new item, set its link to point to the item that is currently at the top, and then make the list’s Top variable point to the new item. Other rearrangements are almost as easy. (For more information on how linked lists work, see a book on algorithms and data structures such as my book Essential Algorithms: A Practical Approach to Computer Algorithms, Wiley, 2013.)

Unfortunately, if the list grows long, finding items in it can take a long time. To find an item in the list, the program starts at the top and works its way down, following the links between items, until it finds the one it wants. If the list is short, that doesn’t take long. If the list holds 100,000 items, this means potentially a 100,000-item crawl from top to bottom. That means a ListDictionary object’s performance degrades if it contains too many items.

If you need to store only a few hundred items in the dictionary and you don’t need to access them frequently, a ListDictionary is fine. If you need to store a huge number of entries, or if you need to access the dictionary’s entries an enormous number of times, you may get better performance using a fancier class such as a Hashtable. A Hashtable has more overhead than a ListDictionary but is faster at accessing its entries.

Hashtable

A Hashtable looks a lot like a ListDictionary on the outside, but internally it stores its data in a different way. Rather than using a linked list, this class uses a hash table to hold data.

A hash table is a data structure that allows extremely fast access to items using their keys. Exactly how hash tables work is interesting but outside the scope of this book. (For more information, see a book on algorithms and data structures such as my book Essential Algorithms.)

You don’t need to know how to create your own hash table to use one, but to use hash tables effectively, you do need to know a little bit about how they work. Hash tables provide extremely fast lookup but they require a fair amount of extra space. If a hash table becomes too full, it starts to slow down, taking longer than normal to store and retrieve values. To improve performance, the hash table must resize itself and rearrange the items it contains. Resizing a hash table can take some time, so the Hashtable class provides some extra tools to help you avoid resizing.

One overloaded version of the Hashtable’s constructor takes a parameter that tells how many items the table should initially be able to hold. If you know you are going to load 1,000 items into the Hashtable, you might initially give it enough room to hold 1,500 items. Then the program could add all 1,000 items without filling the table too much, so it would still give good performance. If you don’t set an initial size, the hash table might start out too small and need to resize itself many times before it could hold 1,000 items, and that will slow it down.

Another version of the constructor lets you specify the hash table’s load factor. The load factor is a number between 0.1 and 1.0 that gives the largest fraction of the table that can be used before the Hashtable enlarges itself. For example, if the load factor is 0.8, then the Hashtable will resize itself if it is more than 80 percent full.

The following code creates a Hashtable, adds the value Apple pie with the key dessert, and then displays that value in a message box.

Hashtable dict = new Hashtable();
dict["dessert"] = "Apple pie";
MessageBox.Show((string)dict["dessert"]);

This code is the same as the code shown earlier that demonstrates a ListDictionary except it uses a Hashtable.

For high-performance lookups, the Hashtable class is a great solution as long as it doesn’t resize too often and doesn’t become too full.

HybridDictionary

A HybridDictionary is a cross between a ListDictionary and a Hashtable. If the dictionary is small, the HybridDictionary stores its data in a ListDictionary. If the dictionary grows too large, the HybridDictionary switches to a Hashtable.

If you know that you will need only a few items, use a ListDictionary. If you know you will need to use lots of items, use a Hashtable. If you are unsure whether you will have few or many items, you can hedge your bet with a HybridDictionary. It’ll take a bit of extra time to switch from a list to a Hashtable if you add a lot of items, but you’ll save time in the long run if the list does turn out to be enormous.

StringDictionary

The StringDictionary class uses a hash table to manage keys and values that are strings. Its methods are strongly typed to require strings, so they provide extra type checking that can make finding potential bugs a lot easier. For that reason, you should use a StringDictionary instead of a generic ListDictionary or Hashtable if you are working with strings.

SortedList

The SortedList class acts as a combination of a Hashtable and an Array. When you access a value by a key, it acts as a hash table. When you access a value by an index, it acts as an array containing items sorted by key value.

For example, suppose you add a number of Job objects to a SortedList named jobs using their priorities as keys. Then jobs.GetByIndex(0) always returns the job with the smallest priority value.

The following code shows how the SortedJobs example program, which is available for download on the book’s website, demonstrates a SortedList.

// The list of jobs.
private SortedList Jobs = new SortedList();

// Add a job.
private void addButton_Click(object sender, EventArgs e)
{
    Jobs.Add(priorityNumericUpDown.Value, jobTextBox.Text);
    ListJobs();
}

// List the jobs in priority order.
private void ListJobs()
{
    jobsListBox.Items.Clear();
    for (int i = 0; i < Jobs.Count; i++)
    {
        jobsListBox.Items.Add(Jobs.GetKey(i) + ": " + Jobs.GetByIndex(i));
    }
}

Enter a job name, select a priority, and click Add. The program adds the new job to the SortedList and calls the ListJobs method to list the jobs in their sorted order.

The ListJobs method loops through the indices of the items in the list and displays their keys and values.

A SortedList is more complicated (and hence slower) than a Hashtable or an array, so you should use it only if you need its special properties.

CollectionsUtil

Normally, Hashtables and SortedLists are case-sensitive. The CollectionsUtil class provides two shared methods, CreateCaseInsensitiveHashtable and CreateCaseInsensitiveSortedList, which create Hashtables and SortedLists that are case-insensitive.

If you can use case-insensitive Hashtables and SortedLists, you may be better off using them because they will prevent the program from accidentally adding the same item twice with different capitalization.

Stacks and Queues

Stacks and queues are specialized data structures that are useful in many programming applications that need to add and remove items in a particular order. The .NET Framework Stack and Queue classes implement stacks and queues.

The difference between a stack and a queue is the order in which they return the items stored in them. The following two sections describe stacks and queues and explain the ways in which they return items.

Stack

A stack returns items in last-in-first-out (LIFO, pronounced life-o) order. Because of its LIFO behavior, a stack is sometimes called a LIFO list or simply a LIFO.

Adding an item to the stack is called pushing the item onto the stack and removing an item is called popping the item off the stack. These operations have the names push and pop because a stack is like a spring-loaded stack of plates in a cafeteria or buffet. You push new plates down onto the top of the stack and the plates sink into the counter. You pop the top plate off and the stack rises to give you the next plate. Figure 14-4 illustrates this kind of stack.

c14f004.eps

Figure 14-4: A Stack lets you remove items in last-in-first-out (LIFO) order.

You can also think of a stack as a stack of papers on a desk. You can add things on the top and take them off of the top, but you can’t pull papers out of the middle or the bottom of the stack without the whole thing toppling over.

Normally, you use the Stack class’s Push and Pop methods to add and remove items from a stack, but the class also provides a few methods that let you cheat by peeking at the top item without removing it or by converting the Stack into an array.

The following table describes the Stack class’s most useful properties and methods.

Property/MethodPurpose
ClearRemoves all the items.
ContainsReturns true if the Stack contains a particular object.
CopyToCopies some or all of the Stack’s objects into a one-dimensional array.
CountReturns the number of items in the Stack.
PeekReturns a reference to the Stack class’s top item without removing it from the Stack.
PopReturns the Stack class’s top item and removes it from the Stack.
PushAdds an item to the top of the Stack.
ToArrayReturns a one-dimensional array containing references to the objects in the Stack. The Stack class’s top item is placed first in the array.

A Stack allocates memory to store its items. If you Push an object onto a Stack that is completely full, the Stack must resize itself to make more room and that slows things down.

Like the Hashtable class, the Stack class provides overloaded constructors that let you determine how much memory should initially be allocated. The first constructor takes no parameters and allocates a default amount of memory.

The second constructor takes as a parameter the number of items the Stack should initially hold. If you know that you will add 10,000 items to the Stack, you can avoid a lot of resizing by initially allocating room for 10,000 items.

The third version of the constructor takes as a parameter an object that implements the ICollection interface. The constructor allocates enough room to hold the items in the ICollection and copies them into the Stack.

The following short example demonstrates a Stack.

Stack stack = new Stack();
stack.Push("Apple");
stack.Push("Banana");
stack.Push("Cherry");
Console.WriteLine(stack.Pop());
Console.WriteLine(stack.Pop());
Console.WriteLine(stack.Pop());

This code creates a Stack and pushes three strings onto it. It then pops the three values back off the Stack, displaying the results in the Console window. The following text shows the results.

Cherry
Banana
Apple

Notice that the items are popped off the Stack in last-in-first-out order.

The UseStack example program enables you push and pop items interactively. Download the example to see how it works.

Queue

A queue returns items in the opposite of the order used by a stack. A queue returns its items in first-in-first-out (FIFO, pronounced fife-o) order. Because of its FIFO behavior, a queue is sometimes called a FIFO list or simply a FIFO.

A queue is similar to a line at a customer service desk. The first person in line is the first person to leave it when the service desk is free. Figure 14-5 shows the idea graphically.

c14f005.eps

Figure 14-5: Customers leave a queue in first-in-first-out (FIFO) order.

Queues are particularly useful for processing items in the order in which they were created. For example, an order-processing application might keep orders in a queue so that orders placed first are fulfilled first.

Historically, the routines that add and remove items from a queue are called enqueue and dequeue. The following table describes the most useful properties and methods provided by the Queue class.

Property/MethodPurpose
ClearRemoves all the items.
ContainsReturns true if the Queue contains a particular object.
CopyToCopies some or all of the Queue’s objects into a one-dimensional array.
CountReturns the number of items in the Queue.
DequeueReturns and removes the item at the front of the Queue.
EnqueueAdds an item to the back of the Queue.
PeekReturns a reference to the item at the front of the Queue without removing it.
ToArrayReturns a one-dimensional array containing references to the objects in the Queue. The item at the front of the Queue is placed first in the array.
TrimToSizeFrees any empty space in the Queue.

Like Stacks, Queues must resize themselves if they become full and that slows things down. Also like Stacks, Queues provide overloaded constructors that let you determine how big the Queue is initially.

The first constructor takes no parameters and allocates a default initial capacity. If the Queue is full, it enlarges itself by a default growth factor.

The second constructor takes as a parameter the Queue’s initial capacity. If you know that you will add 1,000 items to the Queue, you can save some time by initially allocating room for 1,000 items. With this constructor, the Queue also uses a default growth factor.

The third constructor takes as a parameter an object that implements the ICollection interface. The constructor allocates enough room to hold the items in the ICollection and copies them into the Queue. This version also uses a default growth factor.

The final version of the constructor takes as parameters an initial capacity and a growth factor between 1.0 and 10.0. A larger growth factor means the Queue resizes itself less often, but also means it may contain a lot of unused space.

The following short example demonstrates a Queue.

Queue queue = new Queue();
queue.Enqueue("Apple");
queue.Enqueue("Banana");
queue.Enqueue("Cherry");
Console.WriteLine(queue.Dequeue());
Console.WriteLine(queue.Dequeue());
Console.WriteLine(queue.Dequeue());

This code creates a Queue and adds three strings to it. It then dequeues the three values, displaying the results in the Console window. The following text shows the results.

Apple
Banana
Cherry

Notice that the items are removed from the Queue in first-in-first-out order.

The UseQueue example program enables you enqueue and dequeue items interactively. Download the example to see how it works.

Generic Collections

A generic class or method is one that takes a data type as a parameter. The class or method can then use that type as if it were any other type.

For example, the Dictionary class is a generic collection class. It takes two type parameters giving the types of the dictionary’s keys and values.

In C# you specify a class’s generic parameters after the class name and enclosed in pointy brackets. The following code declares and instantiates a Dictionary that uses keys that are strings and values that are ints. It then sets the value for the key “Mark” equal to 23. It finishes by getting the value for the key “Mark” from the Dictionary and storing it in an int variable.

Dictionary<string, int> ages = new Dictionary<string, int>();
ages["Mark"] = 23;
int age = ages["Mark"];

The System.Collections.Generic namespace includes several generic collection classes that you can use to build strongly typed collections. These collections work with one or more specific data types that you supply in a variable’s declaration (as shown in the preceding code).

You cannot directly modify a generic collection class, but you can add extension methods to it. For example, suppose you have defined a Person class. Then the following code creates an AddPerson extension method for the generic List<Person> class. This method takes as parameters a first and last name, uses those values to make a Person object, adds it to the list, and returns the new Person.

static class GenericExtensions
{
    public static Person AddPerson(this List<Person> list,
        string firstName, string lastName)
    {
        Person person = new Person()
            { FirstName = firstName, LastName = lastName };
        list.Add(person);
        return person;
    }
}

The following code shows how a program could use this extension method.

List<Person> people = new List<Person>();
people.AddPerson("Rod", "Stephens");

(For more information on extension methods, see the section “Extension Methods” in Chapter 6, “Methods.”)

You can also derive a class from a generic class. For example, the following code defines an EmployeeList class that inherits from the generic List<Employee> class. The code adds an overloaded version of the Add method that takes first and last names as parameters.

public class EmployeeList : List<Employee>
{
    public Employee Add(string firstName, string lastName)
    {
        Employee employee = new Employee()
            { FirstName = firstName, LastName = lastName};
        base.Add(employee);
        return employee;
    }
}

The following table lists some of the most useful collection classes defined by the System.Collections.Generic namespace.

CollectionPurpose
ComparerCompares two objects of a specific type and returns –1, 0, or 1 to indicate whether the first is less than, equal to, or greater than the second
DictionaryA strongly typed dictionary
LinkedListA strongly typed linked list
LinkedListNodeA strongly typed node in a linked list
ListA strongly typed list
QueueA strongly typed queue
SortedDictionaryA strongly typed sorted dictionary
SortedListA strongly typed sorted list
StackA strongly typed stack

Collection Initializers

Initializers allow you to easily add items to collection classes that have an Add method. To initialize a collection, follow the variable’s instantiation with the items you want to add to it surrounded by braces.

For example, suppose you have defined an Author class that has a constructor that takes first and last names as parameters. Then the following code creates and initializes a List<Author>.

List<Author> authors = new List<Author>()
{
    new Author("Terry", "Pratchett"),
    new Author("Jasper", "Fforde"),
    new Author("Tom", "Holt"),
};

If a collection’s Add method takes more than one parameter, simply include the appropriate values for each item inside its own sets of braces. For example, each of the Dictionary class’s entries includes a key and a value. The following code initializes a Dictionary that matches names with phone numbers.

Dictionary<string, string> phoneNumbers = new Dictionary<string, string>()
{
    {"Arthur", "808-567-1543"},
    {"Betty", "808-291-9838"},
    {"Charles", "808-521-0129"},
    {"Debbie", "808-317-3918"},
};

The same technique works for other collections that need two values such as ListDictionary, Hashtable, HybridDictionary, StringDictionary, and SortedList.

Unfortunately, you cannot use this method to initialize the Stack and Queue classes because this kind of initialization requires the class to have an Add method. For historical reasons, the methods in those classes that add new items are called Push and Enqueue instead of Add.

Fortunately, those classes have constructors that can take IEnumerable objects as parameters. That means, for example, that you can pass the constructors an array holding the objects that should be added to the collection. The following code uses that technique to initialize a Stack and Queue of Author objects.

Stack<Author> authorStack = new Stack<Author>(
    new Author[]
    {
        new Author("Terry", "Pratchett"),
        new Author("Jasper", "Fforde"),
        new Author("Tom", "Holt"),
    }
);

Queue<Author> authorQueue = new Queue<Author>(
    new Author[]
    {
        new Author("Terry", "Pratchett"),
        new Author("Jasper", "Fforde"),
        new Author("Tom", "Holt"),
    }
);

Iterators

One advantage of collection classes is that you can use a foreach loop to enumerate over their items.

C# also allows you to write iterators. An iterator is a method that yields a sequence of results. The program can use a foreach loop to enumerate the values the iterator yields. In that sense iterators resemble collections; although they don’t need to store items in some sort of data structure.

The easiest way to make an iterator is to create a method that returns IEnumerable or a generic type such as IEnumerable<String>. The method should generate its values and use a yield return statement to return them to the code that is looping over the enumeration.

For example, the following iterator yields a list of prime numbers between startNumber and stopNumber.

// Enumerate prime numbers between startNumber and stopNumber.
public IEnumerable Primes(int startNumber, int stopNumber)
{
    // Define a lambda expression that tests primality.
    Func<int, bool> isPrime = x =>
    {
        if (x == 1) return false;       // 1 is not prime.
        if (x == 2) return true;        // 2 is prime.
        if (x % 2 == 0) return false;   // Even numbers are not prime.
        for (int i = 3; i * i <= x; i += 2)
            if (x % i == 0) return false;
        return true;
    };

    for (int i = startNumber; i <= stopNumber; i++)
    {
        // If this number is prime, enumerate it.
        if (isPrime(i)) yield return i;
    }
}

This code makes a delegate variable named isPrime to hold a lambda expression that returns true if a number is prime. The iterator then loops through the numbers between startNumber and stopNumber, calls the isPrime for each, and uses yield return to return the values that are prime.

The following code shows how a program could use the iterator to display prime numbers.

foreach (int i in Primes(1, 100)) primesListBox.Items.Add(i);

This code iterates over the sequence generated by calling Primes(1, 100). That call invokes the iterator and makes it produce the sequence of prime numbers between 1 and 100. The program adds each value in the sequence to the primesListBox control’s items.

For more information on iterators, see “Iterators (C# and Visual Basic)” at msdn.microsoft.com/library/dscyy5s0.aspx.

Summary

This chapter explained several types of collection classes. Even the simplest of these, an array of variables, can be extremely useful. An array itself doesn’t provide many features, but the Array class has a lot of useful methods, such as Reverse and Sort, that can manipulate arrays.

The Array class also lets you build multidimensional arrays with nonzero lower bounds. The performance isn’t as good as that of arrays of values, but in some applications the convenience may be worth reduced performance.

Other collection classes store data in different ways. A StringCollection is a simple collection of strings. A NameValueCollection associates string keys with multiple string values. A Dictionary associates keys (of any type) with a single value each (also of any type).

A Stack provides access to items in last-in-first-out (LIFO) order. A Queue gives access to items in first-in-first-out (FIFO) order.

Although these classes have different features for adding, removing, finding, and ordering objects, they share some common traits. For example, those that provide an Add method support collection initialization and all of them support enumeration by foreach statements. They also support the methods used by LINQ to make queries possible.

This chapter explained how you can use the generic collection classes provided by the System.Collections.Generic namespace. The next chapter explains how you can build generic classes of your own. Generics let you build strongly typed classes that manipulate objects of any data type.

Exercises

  1. A palindrome is a string that is the same forward as backward, ignoring capitalization and punctuation: “Taco cat” and “nurses run.” Write a program that indicates whether a string entered by the user is a palindrome. (Hint: Don’t use loops. Instead use the following facts.)
    • You can treat a string as an IEnumerable<char>.
    • IEnumerable provides a Reverse method.
    • IEnumerable provides a ToArray method.
    • The string class’s constructor has a version that takes a char[] as a parameter.
    • Convert to lowercase and remove spaces, but assume the user won’t type any other punctuation characters.
  2. Write a program that uses a dictionary of lists to store book titles grouped by author. (The dictionary’s keys should be author names. Its values should be lists of book titles.) Use initialization code to create data for at least three authors with two books each. When the user enters or selects an author, display that author’s books. (Hint: Use LINQ to get the values you need. In a Windows Forms application, you can set a ListBox’s DataSource property to an array.)
  3. Modify the program you wrote for Exercise 2 so that it uses a NameValueCollection instead of a dictionary of lists. (Hint: You may find the string class’s Split method useful.)
  4. Write a program similar to the one shown in Figure 14-6 that lists information about cars.
    1. First, create a Car class with the properties Name, Price, Horsepower, and SixtyTime (the time in seconds to go from 0 to 60 mph). Create and initialize an array of Car objects. (Look up data on the Internet or just make some up if you prefer.) Override the class’s ToString method so that it returns an object’s concatenated values.
    2. Display the car data in a ListBox.
    3. Place four RadioButtons on the form labeled Name, Price, Horsepower, and 0–60 Time. When the user clicks one of the buttons, the program should sort the car data based on the selected criterion and redisplay the list.
    4. To sort the data, create a CarComparer class that implements IComparer<Car>. Give the class a ComparisonTypes enumeration that defines the possible comparison types. Give the class a ComparisonType property of the type ComparisonTypes to tell which type a comparer object should use. Make the Compare method required by the IComparer interface use the ComparisonType property to decide how to compare two Car objects.
    5. Finally, to put it all together, when the user clicks one of the RadioButtons, make the program create a CarComparer, set its ComparisonType property, and use the comparer to sort the car data. Then make the ListBox display the sorted data.
      c14f006.tif

      Figure 14-6: The CarList example program sorts car data by name, price, horsepower, or 0–60 time.

  5. Write a program that initializes a List<char> to hold the characters A, B, C, D, and E. Reverse the items to create a new List<char> by using these methods:
    1. Use LINQ. (Hint: Convert the result into an array and pass it to the string constructor to make a string holding the list’s characters.)
    2. Copy the list and use the copy’s Reverse method. (Hint: Pass the original list into a constructor to make the list copy.)
    3. Use a stack.
  6. How is an iterator different from a method that returns a collection such as an array or List? In other words, couldn’t you make a method that returns the items in a List and use a foreach loop to enumerate them instead of using an iterator?
  7. Make the Primes iterator shown in the section “Iterators” more efficient by making it handle the value 2 and other even numbers outside of its loop. Make a program similar to the one shown in Figure 14-7 to test the iterator.
    c14f007.tif

    Figure 14-7: The ListPrimes example program uses an iterator to enumerate prime numbers.

  8. Make an AllPrimes iterator that yields prime numbers starting at 2 and continuing indefinitely. Modify the program you wrote for Exercise 1 so that it uses this new iterator. It also won’t need the start number because the iterator starts at 2. (Hint: Make the foreach loop end when it has enumerated the required values. Don’t make it run forever!)
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.143.237.115