What’s in This Chapter
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.
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 string
s, then the statement Array.Sort(values)
sorts the strings in the array.
The following sections provide more details about arrays and the Array
class.
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);
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.
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.
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.
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/Method | Purpose |
BinarySearch | Returns the index of an item in the previously sorted array. The items must implement the IComparable interface, or you must provide an IComparer object. |
Clear | Removes all the items from the array. |
ConvertAll | Converts an array of one type into an array of another type. |
Copy | Copies some or all the items from a position in one array to a position in another. |
Exists | Determines whether the array contains a particular item. |
IndexOf | Returns the index of the first item with a given value. |
LastIndexOf | Returns the index of the last item with a given value. |
Resize | Resizes the array. |
Reverse | Reverses the order of the items in the array. |
Sort | Sorts the items in the array. The items must implement the IComparable interface, or you must provide an IComparer object. |
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.
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/Method | Purpose |
Add | Adds an item at the end of the list. |
AddRange | Adds the items in an object that implements the ICollection interface to the end of the list. |
BinarySearch | Returns 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. |
Capacity | Gets or sets the number of items that the list can hold. |
Clear | Removes all the items from the list. |
Contains | Returns true if a specified item is in the list. |
CopyTo | Copies some of the list or the entire list into a one-dimensional Array object. |
Count | Returns the number of items currently in the list. This is always less than or equal to Capacity . |
GetRange | Returns an ArrayList containing the items in part of the list. |
IndexOf | Returns the zero-based index of the first occurrence of a specified item in the list. |
Insert | Adds an item at a particular position in the list. |
InsertRange | Adds the items in an object that implements the ICollection interface to a particular position in the list. |
Item | Returns the item at a particular position in the list. |
LastIndexOf | Returns the zero-based index of the last occurrence of a specified item in the list. |
Remove | Removes the first occurrence of a specified item from the list. |
RemoveAt | Removes the item at the specified position in the list. |
RemoveRange | Removes the items in the specified positions from the list. |
Reverse | Reverses the order of the items in the list. |
SetRange | Replaces the items in part of the list with new items taken from an ICollection object. |
Sort | Sorts the items in the list. The items must implement the IComparable interface, or you must provide the method with an IComparer object. |
ToArray | Copies 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 ). |
TrimToSize | Reduces 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
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.
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 string
s 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 TextBox
es 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/Method | Description |
Add | Adds 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. |
AllKeys | Returns a string array holding all the key values. |
Clear | Removes all names and values from the collection. |
CopyTo | Copies items starting at a particular index into a one-dimensional Array object. This copies only the items, not the keys. |
Count | Returns the number of keys in the collection. |
Get | Gets the items for a particular index or name as a comma-separated list of values. |
GetKey | Returns the key for a specific index. |
GetValues | Returns a string array containing the values for a specific name or index. |
HasKeys | Returns true if the collection contains any non-null keys. |
Keys | Returns a collection containing the keys. |
Remove | Removes a particular name and all its values. |
Set | Sets 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.
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 string
s, 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/Method | Description |
Add | Adds a key/value pair to the dictionary. |
Clear | Removes all key/value pairs from the dictionary. |
Contains | Returns true if the dictionary contains a specific key. |
CopyTo | Copies 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. |
Count | Returns the number of key/value pairs in the dictionary. |
Item | Gets or sets the value associated with a key. |
Keys | Returns a collection containing all the dictionary’s keys. |
Remove | Removes the key/value pair with a specific key. |
Values | Returns 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 object
s, 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.
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.
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.
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.
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.
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.
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.
Normally, Hashtable
s and SortedList
s are case-sensitive. The CollectionsUtil
class provides two shared methods, CreateCaseInsensitiveHashtable
and CreateCaseInsensitiveSortedList
, which create Hashtable
s and SortedList
s that are case-insensitive.
If you can use case-insensitive Hashtable
s and SortedList
s, 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 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.
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.
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/Method | Purpose |
Clear | Removes all the items. |
Contains | Returns true if the Stack contains a particular object. |
CopyTo | Copies some or all of the Stack ’s objects into a one-dimensional array. |
Count | Returns the number of items in the Stack . |
Peek | Returns a reference to the Stack class’s top item without removing it from the Stack . |
Pop | Returns the Stack class’s top item and removes it from the Stack . |
Push | Adds an item to the top of the Stack . |
ToArray | Returns 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.
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.
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/Method | Purpose |
Clear | Removes all the items. |
Contains | Returns true if the Queue contains a particular object. |
CopyTo | Copies some or all of the Queue ’s objects into a one-dimensional array. |
Count | Returns the number of items in the Queue . |
Dequeue | Returns and removes the item at the front of the Queue . |
Enqueue | Adds an item to the back of the Queue . |
Peek | Returns a reference to the item at the front of the Queue without removing it. |
ToArray | Returns 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. |
TrimToSize | Frees any empty space in the Queue . |
Like Stack
s, Queue
s must resize themselves if they become full and that slows things down. Also like Stack
s, Queue
s 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.
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 string
s and values that are int
s. 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.
Collection | Purpose |
Comparer | Compares 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 |
Dictionary | A strongly typed dictionary |
LinkedList | A strongly typed linked list |
LinkedListNode | A strongly typed node in a linked list |
List | A strongly typed list |
Queue | A strongly typed queue |
SortedDictionary | A strongly typed sorted dictionary |
SortedList | A strongly typed sorted list |
Stack | A strongly typed stack |
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"),
}
);
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
.
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.
IEnumerable<char>
.IEnumerable
provides a Reverse
method.IEnumerable
provides a ToArray
method.string
class’s constructor has a version that takes a char[]
as a parameter.ListBox
’s DataSource
property to an array.)NameValueCollection
instead of a dictionary of lists. (Hint: You may find the string class’s Split
method useful.)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.ListBox
.RadioButton
s 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.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.RadioButton
s, 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.
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:
string
constructor to make a string holding the list’s characters.)Reverse
method. (Hint: Pass the original list into a constructor to make the list copy.)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?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.
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!)