200
LESSON 16 Using ArrAys And ColleCtions
TABLE 161
METHOD PURPOSE
BinarySearch
Uses binary search to find an item in a sorted array.
Clear
Resets a range of items in the array to the default value for the array’s
data type (0, false, or null).
Copy
Copies a range of items from one array to another.
IndexOf
Returns the index of a particular item in the array.
LastIndexOf
Returns the index of the last occurrence of a particular item in the array.
Resize
Resizes the array, preserving any items that fit in the new size.
Reverse
Reverses the order of the items in the array.
Sort
Sorts the array’s items.
COLLECTION CLASSES
An array holds a group of items and lets you refer to them by index. The .NET Framework used by
C# also provides an assortment of collection classes that you can use to store and manipulate items
in other ways. For example, a
Dictionary stores items with keys and lets you very quickly locate an
item from its key. You could use a
Dictionary to make an employee phone book and very quickly
look up a phone number given someone’s name.
Generic Classes
The following sections describe some particular kinds of classes that come pre-built by the .NET
Framework. These are generic classes so before you learn about them you should know a little about
what a generic class is.
A generic class is one that is not tied to a particular data type. For example, suppose you built
a
StringList class that can store a list if strings. Now suppose you decided you wanted an
IntegerList class to store lists of integers. The two classes would be practically identical, just
for different data types.
I’ve mentioned several times that duplicated code is a bad thing. Having two nearly identical classes
means debugging and maintaining two different sets of code that are practically the same.
One solution to this situation is to make a more general
AnythingList class that uses the general
object data type to store items. An object can hold any kind of data, so this class could hold lists
of integers, strings, or
Customer objects. Unfortunately that has two big problems.
First, you would also do a lot of work converting the items with the general
object data type stored
in the list into the
int, string, or Customer type of the items that you put in there. This is annoying
because it gives you more work to do and makes your code more complicated and harder to read.
596906book.indd 200 4/8/10 7:40:04 AM
Collection Classes
201
A bigger problem is that a list that can hold anything can hold anything. If you make a list to hold
customer data, it could still hold
ints, strings, and PurchaseOrder objects. Your code would need
to do a lot of work guarding against accidentally putting the wrong kind of item in the list.
A much better approach is to use generic classes. These classes take data types in their declarations
so they know what kind of data they will manipulate. Using this kind of class, you can build a list of
integers, strings, or what have you.
The following code declares and initializes a generic
List class.
List<string> names = new List<string>();
The <string> part of the declaration indicates that the class will work with strings. You can put
strings into the list and take strings out of it. You cannot add an integer to the list, just as you can’t
set a string variable equal to an integer. Visual Studio knows that the list works with strings and
won’t let you use anything else.
Note that IntelliSense knows about generic classes and provides help. If you begin a declaration with
List, IntelliSense displays List<> to let you know that it is a generic class.
Now if you type the opening pointy bracket, IntelliSense displays a list of the class’s type parameters
and even describes them as you type. (The
List class has only one type parameter but some such
as
Dictionary have more.) After you finish the declaration, the class knows what data types it will
manipulate, and it can behave as if it were designed with that data type in mind.
Now, with some understanding of generic classes, you’re ready to look at some generic
collection classes.
Lists
A List is a simple ordered list of items. You can declare and initialize a List as in the following code.
List<string> names = new List<string>();
The List class provides several methods for manipulating the items it contains. The three most
important are
Add, Remove, and RemoveAt.
The
Add method adds a new item to the end of the list, automatically resizing the List if neces-
sary. This is easier than adding an item to an array, which requires you to resize the array first.
The
Remove method removes a particular item from the list. Note that you pass the target item to
Remove, not the index of the item that you want to remove. If you know that the string “Zaphod”
is in the list
names, the following code removes the first instance of that name from the list:
names.Remove(“Zaphod”);
The Remove method removes only the first occurrence of an item from the List.
596906book.indd 201 4/8/10 7:40:04 AM
202
LESSON 16 Using ArrAys And ColleCtions
The
RemoveAt method removes an item from a particular position in the list. It then com-
pacts the list to remove the hole where the item was. This is much easier than removing an
item from an array, which requires you to shuffle items from one part of the array to another
and then resize the array to reduce its size.
In addition to these methods, you can use square brackets to get and set a
List’s entries much as
you can with an array. For example, the following code sets and then displays the value of the first
entry in a list:
names[0] = “Mickey”;
MessageBox.Show(“The first name is “ + names[0]);
Note that this works only if the index you use exists in the list. If the list holds 10 names and you try
to set the 14th, the program crashes.
SortedLists
A SortedList stores a list of key/value pairs, keeping the list sorted by the keys. The types of the
keys and values are generic parameters, so for example, you could make a list that uses numbers
(such as employee IDs) for keys and strings (such as names) for values.
Note that the list will not allow you to add two items with the same key. Multiple items can have the
same value, but if you try to add two with the same key, the program crashes.
Table 16-2 summarizes useful methods provided by the
SortedList class.
TABLE 162
METHOD PURPOSE
Add
Adds a key and value to the list.
Clear
Empties the list.
Contains
Returns true if the list contains a given value.
ContainsKey
Returns true if the list contains a given key.
ContainsValue
Returns true if the list contains a given value.
GetKeyList
Returns a list holding the keys.
GetValueList
Returns a list holding the values.
Remove
Removes the item with a specific key from the list.
In addition to these methods, you can use square brackets to index into the list, using the items’ keys
as indexes.
The following code demonstrates a
SortedList:
SortedList<string, string> addresses =
new SortedList<string, string>();
596906book.indd 202 4/8/10 7:40:04 AM
Collection Classes
203
addresses.Add(“Dan”, “4 Deer Dr, Bugville VT, 01929”);
addresses.Add(“Bob”, “8273 Birch Blvd, Bugville VT, 01928”);
addresses[“Cindy”] = “32878 Carpet Ct, Bugville VT, 01929”;
addresses[“Alice”] = “162 Ash Ave, Bugville VT, 01928”;
addresses[“Bob”] = “8273 Bash Blvd, Bugville VT, 01928”;
MessageBox.Show(“Bob’s address is “ + addresses[“Bob”]);
The code starts by declaring and initializing the list. It uses the Add method to add some entries and
then uses square brackets to add some more.
Next the code uses the square bracket syntax to update Bob’s address. Finally the code displays
Bob’s new address.
You can’t see it from this example, but unlike the
List class, SortedList actually stores its items
ordered by key. For example, you could use the
GetKeyList and GetValueList methods to get the
list’s keys and values in that order.
Dictionaries
The Dictionary and SortedDictionary classes provide features similar to the SortedList class,
manipulating key/value pairs. The difference is in the data structures the three classes use to store
their items.
Without getting into technical details, the results are that the three classes use different amounts
of memory and work at different speeds. In general,
SortedList is the slowest but takes the least
memory, while
Dictionary is the fastest but takes the most memory.
For small programs, the difference is insignificant. For big programs that work with thousands of
entries, you might need to be more careful about picking a class. (Personally I like
Dictionary for
most purposes because speed is nice, memory is relatively cheap, and the name is suggestive of the
way you use the class: to look up something by key.)
Queues
A Queue is a collection that lets you add items at one end and remove them from the other. It’s like
the line at a bank where you stand at the back of the line and the teller helps the person at the front
of the line until eventually it’s your turn.
Because a queue retrieves items in first-in-first-out order, queues are sometimes
called FIFO lists or FIFOs. (“FIFO” is pronounced fife-o.)
Table 16-3 summarizes the Queue’s most important methods.
596906book.indd 203 4/8/10 7:40:05 AM
204
LESSON 16 Using ArrAys And ColleCtions
TABLE 163
METHOD PURPOSE
Clear
Removes all items from the Queue.
Dequeue
Returns the item at the front of the Queue and removes it.
Enqueue
Adds an item to the back of the Queue.
Peek
Returns the item at the front of the Queue without removing it.
Stacks
A Stack is a collection that lets you add items at one end and remove them from the same end. It’s
like a stack of books on the floor: you can add a book to the top of the stack and remove a book
from the top, but you can’t pull one out of the middle or bottom without risking a collapse.
Because a stack retrieves items in last-in-first-out order, stacks are sometimes
called LIFO lists or LIFOs. (“LIFO” is pronounced life-o.)
The top of a stack is also sometimes called its head. The bottom is sometimes
called its tail.
Table 16-4 summarizes the Stack’s most important methods.
TABLE 164
METHOD PURPOSE
Clear
Removes all items from the Stack.
Peek
Returns the item at the top of the Stack without removing it.
Pop
Returns the item at the top of the Stack and removes it.
Push
Adds an item to the top of the Stack.
TRY IT
In this Try It, you use a Dictionary to build the
order lookup system shown in Figure 16-4. When the
user clicks the Add button, the program adds a new
item with the given order ID and items. If the user
enters an order ID and clicks Find, the program
FIGURE 164
596906book.indd 204 4/8/10 7:40:08 AM
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.