Arrays and Collections

Overview

Arrays and collections are a key part of any programmer's toolkit. They allow you to aggregate large amounts of information into a structured pattern and often allow you to perform searches, sorting, and key-based lookup. In this chapter, we'll consider all of these basics, beginning with the canonical System.Array class, where you'll learn how to quickly populate and resize an array (recipes 3.1 and 3.2) and create nonrectangular arrays or irregular arrays with non-zero lower bounds (recipes 3.3 and 3.4). Next, we'll consider specialized collection types such as the Hashtable, ArrayList, SortedList, Queue, and Stack, all of which provide higher-level functionality that's indispensable for some tasks.

Before reading the recipes in this chapter, it helps to understand two fundamentals that apply to arrays and all other collection types.

• Arrays and collections are reference types. That means that if you pass an array or collection to a method, the array and all its items can be modified. Marking the parameter with ByVal will prevent the function code from replacing the array with a different array, but it won't stop the code from modifying the items that are in the array.
• If you are storing a reference type inside an array or collection, you are storing an object reference, not the object content. This has implications when considering array size, and it also means that a single object can be a part of multiple collections or arrays at the same time. Recipe 3.16 examines this possibility.

Note

Several of the recipes in this chapter assume you have imported the System.Collections namespace, where most collection types are defined. This namespace is imported by default in Microsoft Visual Studio .NET

Create and Populate an Array in One Step

Problem

You want to create an array and fill it with initial values in one step.

Solution

Use an initializer, and specify the values in curly braces.

Discussion

Microsoft Visual Basic .NET introduces a new initializer syntax that allows you to create a variable and set it in one step. This syntax can be used with arrays. You simply need to specify a comma-delimited list of all values, in order, inside curly braces. You can't specify the bounds of the array, because it will be inferred by the number of items you specify.

Here are two simple examples with one-dimensional arrays:

' Creates an array from index 0 to 9, with ten elements.
Dim MyIntegers() As Integer = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
 
' Creates an array from index 0 to 3, with four elements.
Dim MyColors() As String = {"blue", "green", "pink", "yellow"}

You can use the same approach with complex objects that need to be instantiated using a constructor. Just specify the New keyword inside the curly braces each time you want to create an object.

' Create and initialize an array with three point objects.
Dim Points() As Point = _
 {New Point(0, 0), New Point(10, -3), New Point(3, 0)}

Finally, it's also possible to use this approach to fill multidimensional arrays. In this case, when defining the array you must add a comma for every additional dimension. You use multiple sets of braces to group the subdimensions, as shown here:

' Create a two-dimensional (2x3) integer array.
' Same as Dim Integers2(1, 2) As Integer
Dim Integers2(,) As Integer = {{3, 2, 6}, {9, 4, 6}}
 
' This displays "2"
Console.WriteLine(Integers2(0, 1).ToString())
 
' Create a three-dimensional (2x2x2) integer array.
' Same as Dim Integers3(1, 1, 1) As Integer
Dim Integers3(,,) As Integer = {{{3, 5}, {2, 7}}, {{0, 1}, {9, 8}}}
 
' This displays "7"
Console.WriteLine(Integers3(0, 1, 1).ToString())

Resize an Array

Problem

You need to expand the dimensions of an array.

Solution

The Visual Basic .NET ReDim statement with the Preserve keyword.

Discussion

The ReDim keyword allows you to specify new dimensions for an array after defining it. However, the existing items will be lost, unless you specify the Preserve keyword. When using Preserve, you can only resize the last dimension of the array. Thus, if you are resizing a two-dimensional array, you can only expand the second dimension. If you are resizing a one-dimensional array, you can resize the first (and only) dimension.

Dim IntArray(10, 10) As Integer
 
' (Configure the array here.)
 
' Add ten more columns to every row
ReDim Preserve IntArray(10, 20)
 
' The following statement will generate an exception.
' You cannot add more rows with the Preserve keyword.
ReDim Preserve IntArray(20, 20)

Technically, the ReDim statement releases the current array and creates a new one. If Preserve is specified, it copies the data to the new array. This process imposes some overhead, so it's always best to resize an array infrequently. One technique is to double the capacity of an array each time it must be resized. (Although in this case, your code must be aware of empty array elements and ignore them.) A more efficient approach is usually to use an ArrayList when you need a resizable array, as shown in recipe 3.5.

Create an Array That Is Not Bounded at Zero

Problem

You need to create an array that follows idiosyncratic dimension numbering (for example, has a lower bound of –2 or 5 instead of 0).

Solution

Don't attempt this unless required for compatibility reasons—it makes your code less usable and much more obscure. If required, use the Array.CreateInstance method.

Discussion

The Array.CreateInstance method allows you to create a nonstandard array. As parameters, you specify the type of object that will be contained in the array, the length of the array, and the lower bounds. The latter two parameters must be submitted as arrays, with one entry for each dimension. (This means you can use the CreateInstance method to create a jagged array that has different bounds for each row, as described in recipe 3.4.)

The following example creates a one dimensional array that has bounds from –5 to –1, sets a test value, and then iterates over all values, using the same approach that you would use with a standard array.

Dim Lengths() As Integer = {5}
Dim LowerBounds() As Integer = {-5}
 
' Create a 1-dimensional Array of type String,
' with bounds from -5 to -1.
Dim OddArray As Array = Array.CreateInstance(GetType(String), _
 Lengths, LowerBounds)
 
Console.WriteLine("Lower bound: " & OddArray.GetLowerBound(0).ToString())
Console.WriteLine("Upper bound: " & OddArray.GetUpperBound(0).ToString())
 
' Set an array value.
OddArray(-3) = "This is a test."
 
Dim i As Integer
For i = OddArray.GetLowerBound(0) To OddArray.GetUpperBound(0)
 Console.WriteLine(i.ToString() & ": " & OddArray(i))
Next i

This code requires late binding. If you have disabled late binding (by enabling Option Strict, as is often recommended), you'll have to use the more awkward Array.SetValue and Array.GetValue syntax. Here's how you would set a value:

OddArray.SetValue("This is a test.", -3)

And here's how you would retrieve it:

Console.WriteLine(i.ToString() & ": " & OddArray.GetValue(i).ToString())

Remember that values are always retrieved as generic object types and must be cast to the correct type, further complicating code. You must also check for null references for noninitialized array elements. For these reasons, creating nonstandard arrays should only be undertaken if required for legacy reasons.

Note

If you want to use an array with nonstandard lower bounds because the index number of the dimension corresponds to something in the real world, you are better off creating a custom class or collection with the desired behavior.

Create a Jagged Array

Problem

You need to create a nonrectangular array. For example, you might want to create a two-dimensional array in which different rows have different numbers of column elements.

Solution

Don't attempt this unless required for compatibility reasons—it makes your code less usable and much more obscure. If required, use the Array.CreateInstance method.

Discussion

Jagged arrays (sometimes described as arrays of arrays) introduce complexity, and should be used sparingly. However, they do have legitimate uses and are supported by Visual Basic .NET.

One way to create a multidimensional array is by including multiple sets of closed brackets when you define the array. As an example, the following code creates an array with 12 rows (one for each month), and a variable number of columns in each row (matching the number of days in the month).

' This array has 12 rows (representing months).
' Each row has a variable number of columns.
Dim Sales(11)() As Double
 
' Fill the array
Dim Days, Month As Integer
Dim Calendar As New System.Globalization.GregorianCalendar()
For Month = 1 To 12
 ' Size each row to the number of days in the corresponding month.
 Days = Calendar.GetDaysInMonth(2002, Month, Calendar.CurrentEra)
 Sales(Month - 1) = New Double(Days - 1) {}
Next
 
' Walk through the array and print all values.
Dim MonthRow() As Double
For Each MonthRow In Sales
 Console.Write("Month: ")
 
 Dim Column As Double
 For Each Column In MonthRow
 Console.Write(Column.ToString())
 Next
 Console.WriteLine()
Next

When you run this program, it will display a series of zeros (because no values were set). These values show the jagged structure of the array:

Month: 0000000000000000000000000000000
Month: 0000000000000000000000000000
Month: 0000000000000000000000000000000
Month: 000000000000000000000000000000
Month: 0000000000000000000000000000000
Month: 000000000000000000000000000000
Month: 0000000000000000000000000000000
Month: 0000000000000000000000000000000
Month: 000000000000000000000000000000
Month: 0000000000000000000000000000000
Month: 000000000000000000000000000000
Month: 0000000000000000000000000000000

The only limitation of this example is that every row must have the same data type. It's also possible to explicitly create an array of Array objects, where each Array object uses a different data type.

Dim StringArray() As String = {"blue", "green"}
Dim IntArray() As Integer = {1, 2, 3, 4, 5, 6}
 
Dim JaggedArray() As Array = {StringArray, IntArray}
 
 
Dim i, j As Integer
For i = 0 To JaggedArray.GetUpperBound(0)
 Console.Write("Row " & i.ToString & ": ")
 For j = 0 To JaggedArray(i).GetUpperBound(0)
 Console.Write(JaggedArray(i).GetValue(j).ToString() & " ")
 Next
 Console.WriteLine()
Next

This code displays two lines:

Row 0: blue green
Row 1: 1 2 3 4 5 6

Keep in mind that an overuse of jagged arrays usually indicates a problem that could be solved more elegantly using custom classes and collections.

Use a Dynamic ArrayList

Problem

You want to use a one-dimensional array that allows items to be inserted and removed dynamically and resizes itself automatically.

Solution

Use the System.Collections.ArrayList class.

Discussion

The ArrayList class is quite straightforward. Items are added using the Add method. Items can be removed using the Remove, RemoveRange, or RemoveAt methods. The latter two methods remove items based on their index numbers, while Remove searches the collection for the indicated item and then removes it. Instead of using the GetLength method, as you would with an array, you use the equivalent property Count.

Dim List As New ArrayList()
List.Add("blue")
List.Add("green")
List.Add("yellow")
List.Add("red")
 
' Remove "blue" by index number.
List.RemoveAt(0)
 
' Remove "green" using a search.
List.Remove("green")
 
Console.WriteLine("Items: " & List.Count.ToString())
 
' Display ArrayList contents ("yellow" and "red").
Dim Item As String
For Each Item In List
 Console.WriteLine(Item)
Next

The ArrayList class uses a capacity system similar to the StringBuilder class described in recipe 1.14. When an ArrayList is first created, it allocates an internal buffer for 16 items. If more items are needed, it expands the count by doubling it (to 32, then 64, and so on). If you know how many items an ArrayList will contain, you can reserve the required space in advance by specifying it in the ArrayList constructor. This can improve performance slightly.

' Reserve space for 50 elements.
Dim List As New ArrayList(50)

The ArrayList is weakly typed, which means that it stores everything as a base Object type. When retrieving an item, you need to cast it accordingly.

Dim Item As String = CType(List(0), String)

This behavior can introduce problems in an application because there's no way to ensure that the wrong type of object isn't added to an array. To solve this problem, you might want to create a custom strongly typed collection, as described in recipe 3.16.

Note

Microsoft .NET does provide one strongly typed list, although it's easy to overlook: the StringCollection class, which is provided in the System.Collections.Specialized namespace. This class only accepts strings (although duplicate string entries are completely acceptable).

Fill an ArrayList from an Array

Problem

You need to copy items from an array into an ArrayList.

Solution

You can add an entire range of items into an ArrayList quickly using the AddRange method.

Discussion

The ArrayList.AddRange method accepts any object that implements the ICollection interface (including an array or another ArrayList), and copies all the items it contains into the ArrayList.

Dim Colors() As String = {"blue", "green", "pink", "yellow"}
 
' Copy the strings in the Colors array into the List ArrayList.
Dim List As New ArrayList()
List.AddRange(Colors)
 
' Display the contents of the ArrayList.
Dim Item As String
For Each Item In List
 Console.WriteLine(Item)
Next

Keep in mind that if you are using a reference type, when you copy it into the ArrayList you are copying the reference, not the content of the object. Thus, both the ArrayList and the original array will be referencing the same object in memory.

Convert an ArrayList to an Array

Problem

You need to convert an ArrayList into a strongly typed array.

Solution

Use the ArrayList.ToArray method.

Discussion

Converting an ArrayList to an ordinary array is a useful task. For example, you might create a utility function that uses an ArrayList internally to quickly create a collection and dynamically add items. Using an ArrayList is intrinsically easier than using an array, because you don't need to worry about array dimensions. However, when you return the information from the function, you should use a generic array, which is more common and has the advantage of type safety.

In theory, you could inspect the Count property of the ArrayList, create a corresponding array, and iterate through the ArrayList, copying elements one by one. However, the ArrayList provides a simpler approach through its ToArray method. When using ToArray, you simply specify the type of array. The ToArray method will inspect every item in the ArrayList, attempt to convert it to the specified type, and then copy the reference to the array. If any item can't be converted, an exception will be thrown.

The following example shows a trivial function that searches a sentence for certain words, adding them to an ArrayList as they are found. When the operation is complete, the ArrayList is converted to an array of strings. The ToArray method returns an Array object, which must be cast to a strongly typed array using the CType function.

Private Function FindAnimalWords(ByVal sentence As String) As String()
 
 ' Fill the collection.
 Dim Words As New ArrayList()
 Dim Word As String
 For Each Word In sentence.Split()
 Select Case Word
 Case "dog", "cat", "fox", "mouse"
 Words.Add(Word)
 End Select
 Next
 
 ' Convert the ArrayList to an array, and then cast
 ' the generic array to a strongly typed array using CType().
 Return CType(Words.ToArray(GetType(String)), String())
 
End Function

Here's a simple code snipped to test this word search function:

Dim Sentence As String = "The quick brown fox jumps over the lazy dog"
Dim Animals() As String = FindAnimalWords(Sentence)

Note

The specialized Queue and Stack collections (described in recipes 3.12 and 3.13) also provide a ToArray method that allows you to copy elements into a strongly typed array, much as with the ArrayList.

Sort Items in an Array or ArrayList

Problem

You need to sort the items in an array or ArrayList. The items in the array or ArrayList implement IComparable (as do all basic .NET data types).

Solution

Use the Array.Sort or ArrayList.Sort methods.

Discussion

Both the Array and ArrayList types expose a Sort method. This method uses an optimized sort algorithm and compares objects using the IComparable interface. If the objects in the array don't support this interface, you'll need to use a custom comparer (as explained in recipe 3.9). If there's more than one type of object in the same collection, you won't be able to sort it.

The following example sorts strings in an ArrayList. In this case, the type of sort is culture specific and will order items alphabetically (with lowercase letters positioned before the same uppercase letter).

' Create and populate an ArrayList.
Dim Sentence As String = "The quick brown fox jumped over the lazy dog"
Dim List As New ArrayList()
 
' Split the sentence into an array of words,
' and add each word to the ArrayList.
List.AddRange(Sentence.Split())
 
Console.WriteLine("--- Unsorted ---")
Dim Value As String
For Each Value In List
 Console.WriteLine(Value)
Next
 
' Sorts the values of the ArrayList.
List.Sort()
Console.WriteLine(vbNewLine & "---- Sorted ----")
 
For Each Value In List
 Console.WriteLine(Value)
Next

The output of this test is shown here:

--- Unsorted ---
The
quick
brown
fox
jumped
over
the
lazy
dog
 
---- Sorted ----
brown
dog
fox
jumped
lazy
over
quick
the
The

The Sort method is overloaded in both the Array and ArrayList classes to accept index numbers specifying just a subset of the array that should be sorted, and a custom IComparer object that can perform a custom sort.

' Sort 5 items, starting at position 3 (the fourth item).
List.Sort(3, 5, Nothing)

If you wish to use a dictionary collection that sorts itself automatically, you might be interested in the SortedList class described in recipe 3.14. The SortedList class allows two ways to access items: by index number (in which case items are always accessed in their sorted order) or through the associated key value.

Sort Non Comparable Items in an Array or ArrayList

Problem

You want to sort an Array or ArrayList, but the items it contains do not implement IComparable.

Solution

Create a custom IComparer that can sort the type of object contained in the Array or ArrayList. Pass an instance of this IComparer object to the Sort method of the Array or ArrayList object.

Discussion

Some objects define a native sort order by implementing the IComparable interface. Others do not, either because there's no obvious criteria to use for sorting, or because there are several equally valid sort criteria. In these cases, you can create a custom IComparer, which is an object with a single purpose in life—to sort a specific type of object.

There are two reasons that you might use a custom IComparer rather than implement IComparable:

• You need to sort an object in multiple different ways. However, an IComparable object will only sort itself in one way.
• You didn't create the object, and therefore you can't modify the class code to implement IComparable.

For example, consider the System.IO.FileInfo object, which encapsulates information about a file. There are several ways that it might make sense to sort files, including by name, size, or creation date. However, the FileInfo class does not implement IComparable, so it has no intrinsic support for sorting.

To create an IComparer, you must implement a single method, Compare. Below is a custom FileInfoComparer that compares two FileInfo objects. It allows three different types of sorts, depending on the FileInfoCompareType value specified as a constructor argument. An equally valid approach would be to create three separate IComparer objects, one for each type of sort, but that approach would require more code.

' Define three ways a FileInfo object can be sorted.
Public Enum FileInfoCompareType
 Name
 CreateDate
 Size
End Enum
 
Public Class FileInfoComparer
 Implements IComparer
 
 Private _CompareType As FileInfoCompareType
 
 Public ReadOnly Property CompareType() As FileInfoCompareType
 Get
 Return _CompareType
 End Get
 End Property
 
 Public Sub New(ByVal compareType As FileInfoCompareType)
 Me._CompareType = compareType
 End Sub
 
 Public Function Compare(ByVal objA As Object, ByVal objB As Object) _
 As Integer Implements System.Collections.IComparer.Compare
 
 Dim FileA, FileB As FileInfo
 FileA = CType(objA, FileInfo)
 FileB = CType(objB, FileInfo)
 
 ' Determine the comparison type.
 Select Case CompareType
 Case FileInfoCompareType.CreateDate
 Return Date.Compare(FileA.CreationTime, FileB.CreationTime)
 Case FileInfoCompareType.Name
 Return String.Compare(FileA.Name, FileB.Name)
 Case FileInfoCompareType.Size
 Return Decimal.Compare(FileA.Length, FileB.Length)
 End Select
 
 End Function
 
End Class

To test this IComparer, you can retrieve an array of FileInfo objects for a directory using the DirectoryInfo.GetFiles method. You can sort this array by calling Array.Sort and supplying the IComparer instance. Below is a complete Console application that demonstrates this technique. In order to use this code as written, you must import the System.IO namespace where the DirectoryInfo and FileInfo types are defined.

Public Module CustomArraySort
 
 Public Sub Main()
 Dim Dir As New DirectoryInfo("C:")
 
 ' Retrieve an array of FileInfo objects.
 Dim Files() As FileInfo = Dir.GetFiles()
 
 ' Sort the array by filename.
 Array.Sort(Files, New FileInfoComparer(FileInfoCompareType.Name))
 
 ' Display the list of files to confirm its order.
 Console.WriteLine("An alphabetic file list:")
 Dim File As FileInfo
 For Each File In Files
 Console.WriteLine(File.Name)
 Next
 
 Console.ReadLine()
 End Sub
 
End Module

Use a Hashtable Instead of a Generic Collection

Problem

You need a dictionary (key-based) collection, or you want to replace the Visual Basic generic collection with a more powerful alternative.

Solution

Use the System.Collections.Hashtable type.

Discussion

The Hashtable class is a dictionary collection, where every item is indexed with a unique value. Hashtable collections are ideal for situations where you need to quickly retrieve individual items, because you can look up items using the corresponding key values, rather than by iterating through the contents of the entire collection. However, unlike arrays or the ArrayList class, you can't access items using an index number.

When using a Hashtable, you must decide what information to use for indexing items. This data must be unique. It might be derived from the object itself, or you might generate it on demand using a GUID or a sequence number. For example, consider the simple Customer class defined here:

Public Class Customer
 
 Private _ID As Integer
 Private _FirstName As String
 Private _LastName As String
 
 Public Sub New(ByVal id As Integer, ByVal firstName As String, _
 ByVal lastName As String)
 Me.ID = id
 Me.FirstName = firstName
 Me.LastName = lastName
 End Sub
 
 Public Property ID() As Integer
 Get
 Return Me._ID
 End Get
 Set(ByVal Value As Integer)
 Me._ID = Value
 End Set
 End Property
 
 Public Property FirstName() As String
 Get
 Return Me._FirstName
 End Get
 Set(ByVal Value As String)
 Me._FirstName = Value
 End Set
 End Property
 
 Public Property LastName() As String
 Get
 Return Me._LastName
 End Get
 Set(ByVal Value As String)
 Me._LastName = Value
 End Set
 End Property
 
End Class

When storing this information in a Hashtable, you might want to use the unique customer ID to index each Customer object.

' Create three customers.
Dim CustomerA As New Customer(1001, "Henry", "Bloge")
Dim CustomerB As New Customer(1020, "Janice", "Newport")
Dim CustomerC As New Customer(4420, "Heide", "Kraus")
 
' Add the customers to the collection, indexed by ID.
Dim Items As New Hashtable()
Items.Add(CustomerA.ID, CustomerA)
Items.Add(CustomerB.ID, CustomerB)
Items.Add(CustomerC.ID, CustomerC)
 
' Retrieve an item.
Dim Cust As Customer = CType(Items(1020), Customer)
Console.WriteLine("Retrieved: " & Cust.FirstName & " " & Cust.LastName)
' Displays "Retrieved: Janice Newport"
 
' Now create a new Customer object that duplicates CustomerA.
Dim CustomerACopy As New Customer(1001, "Henry", "Bloge")
 
' Check for this customer in the collection.
If Not Items.Contains(CustomerACopy) Then
 ' This code always runs, because the object has not been added.
 Console.WriteLine("Object is not in the collection.")
End If
 
' Check for this customer key in the collection.
If Items.ContainsKey(CustomerACopy.ID) Then
 ' This code always runs, because the key exists in the collection.
 Console.WriteLine("An object with this ID is in the collection.")
End If

Note that like the ArrayList, the Hashtable stores items as the generic object type, and you must use casting code when retrieving an item.

Some other useful Hashtable members include:

• Remove deletes an item from the collection. You specify the key of the item you want removed.
• Contains and ContainsKey return True or False, depending on whether a specified key is in the Hashtable. This provides a quick way to perform a simple search.
• ContainsValue returns True or False, depending on whether a specified object is in the Hashtable. For example, in the previous code example where the Hashtable was used to store Customer objects, you could call ContainsValue with a Customer object. It would return True only if this object is already in the collection.
• The Keys property provides a read-only collection of all the keys used in the Hashtable.
• The Values property provides a read-only collection of all the objects in the Hashtable.

  Note

  The Hashtable class works more or less the same way as the standard Visual Basic 6 Collection type, which is still included in Visual Basic .NET for backward compatibility. However, for most programming tasks, a Hashtable is preferable to a generic collection, because a Hashtable ensures that every item has a key that can be used to locate or remove the item. Without a key, the only way to find an item is by iterating through the entire collection and examining each object. Furthermore, only the Hashtable supports any type of object as a key. The generic collection is limited to string values.

  If you don't have a suitable value to use as a key, you can always use the reference of the object you are adding:

  ' Use the object reference as a key.
  Dim Col As New Hashtable()
  Col.Add(ItemA, ItemA)

  This allows you to quickly remove an object using the following syntax:

  Col.Remove(ItemA)

Enumerate Items in a Hashtable

Problem

You need to enumerate over the contents of a Hashtable.

Solution

Use the DictionaryEntry type with a For/Each block.

Discussion

With a generic collection, you perform enumeration using the type in the collection (or one of its base types). The Hashtable does not support this convention. Instead, you must iterate over a collection of DictionaryEntry objects. There is one DictionaryEntry object for each item stored in the collection. You can retrieve the key for the item from the DictionaryEntry.Key property, and you can retrieve the item in the collection from the DictionaryEntry.Value property.

The following code demonstrates this technique on a collection that contains strings:

' Create the collection and add two items.
Dim Col As New Hashtable()
Dim ItemA As String = "ItemA"
Dim ItemB As String = "ItemB"
Col.Add("First Item", ItemA)
Col.Add("Second Item", ItemB)
 
' Enumerate over the collection contents.
Dim Item As DictionaryEntry
For Each Item In Col
 Console.WriteLine("Key: " & Item.Key.ToString())
 Console.WriteLine("Object: " & Item.Value.ToString())
 Console.WriteLine()
Next

Looking at the output for this code, you'll notice that the enumeration actually takes place backward, starting with the most recently added item:

Key: Second Item
Object: ItemB
 
Key: First Item
Object: ItemA

This approach has the advantage that you can easily determine the keys of all items in a collection.

Use a Queue (FIFO Collection)

Problem

You need a collection where items will be retrieved in the same order they are added.

Solution

Use the System.Collections.Queue type, which provides a first-in, first-out collection.

Discussion

Queues are used for a variety of sequential programming tasks. For example, you might use a queue to store a list of tasks that needs to be performed with a server-side component. Because the queue is a first-in, first-out collection, the oldest items are always dealt with first.

Conceptually, the Queue is a dynamically sized array that stores objects, much as the ArrayList does. The Queue starts with an initial capacity of 32 items (unless you supply a different capacity in the constructor) and doubles the capacity as needed. You can retrieve the number of items from the Count property, add an item with the Enqueue method, or retrieve an item with the Dequeue method, which simultaneously removes the item from the Queue. It's also possible to use Peek to retrieve the next item in the Queue without removing it. However, you can't retrieve queued objects out of order or by index number.

Here's the code needed to create a simple queue and read all items:

Dim Queue As New Queue()
 
Queue.Enqueue("Item A")
Queue.Enqueue("Item B")
Queue.Enqueue("Item C")
 
' Retrieve all items and clear the queue.
Dim Item As String
Do While Queue.Count > 0
 Item = CType(Queue.Dequeue, String)
 Console.WriteLine("Retrieved: " & Item)
 Console.WriteLine(Queue.Count.ToString() & " items remaining.")
Loop

Here's the output for this test:

Retrieved: Item A
2 items remaining.
Retrieved: Item B
1 items remaining.
Retrieved: Item C
0 items remaining.

Use a Stack (LIFO Collection)

Problem

You need a collection where items will be retrieved in the reverse order (so that the most recently added item is always accessed first).

Solution

Use the System.Collections.Stack type, which provides a last-in, first-out collection.

Discussion

Stacks are used for programming tasks where you always need to access the most recent items first. Like the ArrayList and Queue, Stack is a dynamically sized array that stores objects. It starts with an initial capacity of 32 items (unless you supply a different capacity in the constructor) and doubles the capacity as needed. You can retrieve the number of items from the Count property, add an item at the top of a Stack with the Push method, or retrieve an item with the Pop method, which simultaneously removes the item from the Stack array. It's also possible to use Peek to retrieve the next item in the Stack without removing it. However, you can't retrieve objects out of order or by index number.

Here's the code needed to create a simple stack and read all items:

Dim Stack As New Stack()
 
Stack.Push("Item A")
Stack.Push("Item B")
Stack.Push("Item C")
 
' Retrieve all items and clear the queue.
Dim Item As String
Do While Stack.Count > 0
 Item = CType(Stack.Pop, String)
 Console.WriteLine("Retrieved: " & Item)
 Console.WriteLine(Stack.Count.ToString() & " items remaining.")
Loop

Here's the output for this test:

Retrieved: Item C
2 items remaining.
Retrieved: Item B
1 items remaining.
Retrieved: Item A
0 items remaining.

Use a Sorted List

Problem

You want to use a collection that is automatically sorted every time an item is added or removed.

Solution

Use the System.Collections.SortedList type, which sorts items based on the key.

Discussion

The SortedList class is a key-based dictionary collection that stores items in a perpetually ordered state. That makes it slower when adding or removing items. However, using a SortedList collection is usually faster than continuously resorting an Array or ArrayList. Behind the scenes, a sorted list uses two arrays: one to store key values, and one to store the data itself (or the object reference).

The most important aspect to understand about the SortedList class is that it orders items based on the key value, not the object itself. This means that the key must be a type that supports IComparable (such as an integer or a string). Alternatively, you can specify a custom IComparer as an argument to the SortedList constructor. This IComparer will then be used to sort all items, much as in recipe 3.9.

The following code retrieves a set of FileInfo objects from the current directory, adds them to a sorted list collection, and uses the filename as the key value. In order to run this code, you must import the System.IO namespace.

Dim Dir As New DirectoryInfo("C:")
 
' Retrieve an array of FileInfo.
Dim Files() As FileInfo
Files = Dir.GetFiles()
 
' Add them to a sorted list, indexed by filename.
Dim List As New SortedList()
Dim File As FileInfo
For Each File In Files
 List.Add(File.Name, File)
Next
 
' Verify the order.
Dim Item As DictionaryEntry
For Each Item In List
 Console.WriteLine(CType(Item.Value, FileInfo).Name)
Next

Because the SortedList uses the key value, not the object, this approach is unsuitable if the filename might change. In this case, the FileInfo object will remain sorted under the original filename. There's no way to modify the key value for an object—you can only remove the item and add it again.

Create Shallow and Deep Copies of a Collection or Array

Problem

You need to copy a collection.

Solution

To create a shallow copy, use the Clone method. To create a deep copy, iterate over the collection, and copy each item.

Discussion

All collection types provide a Clone method that makes it easy to quickly copy the entire collection.

' Create an ArrayList and add some items.
Dim ListA As New ArrayList()
ListA.Add("blue")
ListA.Add("green")
ListA.Add("yellow")
 
' Create a duplicate ArrayList.
Dim ListB As ArrayList()
ListB = CType(ListA.Clone(), ArrayList)

This is known as a shallow copy, and it works fine for value types (or reference types that behave like value types, such as String). However, this method isn't always appropriate when used with ordinary classes. As an example, consider what happens if you create an ArrayList, populate it with the basic Customer class (shown in recipe 3.10), and then clone it.

' Create an ArrayList with three customers.
Dim ListA As New ArrayList()
ListA.Add(New Customer(1001, "Henry", "Bloge"))
ListA.Add(New Customer(1020, "Janice", "Newport"))
ListA.Add(New Customer(4420, "Heide", "Kraus"))
 
' Create a duplicate ArrayList.
Dim ListB As New ArrayList()
ListB = CType(ListA.Clone(), ArrayList)

The Customer class is, like every class, a reference type. This means that the ArrayList doesn't actually store Customer objects. Instead, it stores a list of object references that point to Customer objects, which are floating about in a different portion of memory (known as the managed heap). When you call Clone, you duplicate the references, but you don't actually duplicate the objects. Thus, you have two collections that reference the same objects.

In some cases, this might be the behavior you want (as it reduces the overall memory overhead). However, if you intend to continue using both collections, this probably isn't the behavior you want, because if you retrieve a reference and change an object using one collection, the changes will automatically affect the other.

In this situation, the only approach is to use manual code to create a deep copy. You need to enumerate through the collection and duplicate each individual item.

Dim ListB As New ArrayList()
 
' Clone the objects.
Dim Item As Customer
For Each Item In ListA
 ' Clone the object in ListA into the corresponding row in ListB.
 ListB.Add(New Customer(Item.ID, Item.FirstName, Item.LastName))
Next

The actual method you use to clone the object depends. In our simple example, you would need to instantiate a new Customer object manually. However, if the object implements the ICloneable interface, you can call the object's Clone method to create a new copy.

For Each Item In ListA
 ListB.Add(CType(Item.Clone(), Customer))
Next

If the object is serializable, you can also use another approach that involves serializing the object to memory, duplicating it, and then deserializing the copy. This process, and the ICloneable interface, are discussed in Chapter 4.

Create a Strongly Typed Collection

Problem

You need to create a collection that can only contain one type of object and rejects attempts to add other data types.

Solution

Create a custom collection class by deriving from System.Collections.CollectionBase, and implement type-safe Add, Remove, and Item methods.

Discussion

You could create a custom collection by implementing the IList, ICollection, and IEnumerable interfaces. However, .NET provides an easier option with the abstract CollectionBase class. Internally, the CollectionBase uses an ArrayList, which is exposed through the protected property List.

As an example, consider the simple Customer object shown here:

Public Class Customer
 
 Private _ID As Integer
 Private _FirstName As String
 Private _LastName As String
 
 Public Sub New(ByVal id As Integer, ByVal firstName As String, _
 ByVal lastName As String)
 Me.ID = id
 Me.FirstName = firstName
 Me.LastName = lastName
 End Sub
 
 Public Property ID() As Integer
 Get
 Return Me._ID
 End Get
 Set(ByVal Value As Integer)
 Me._ID = Value
 End Set
 End Property
 
 Public Property FirstName() As String
 Get
 Return Me._FirstName
 End Get
 Set(ByVal Value As String)
 Me._FirstName = Value
 End Set
 End Property
 
 Public Property LastName() As String
 Get
 Return Me._LastName
 End Get
 Set(ByVal Value As String)
 Me._LastName = Value
 End Set
 End Property
 
End Class

You can derive a type-safe CustomerCollection from CollectionBase. Then you add a strongly typed Add method and a default property named Item, which automatically casts the retrieved object to the correct type.

Public Class CustomerCollection
 Inherits System.Collections.CollectionBase
 
 Public Sub Add(ByVal item As Customer)
 Me.List.Add(item)
 End Sub
 
 Public Sub Remove(ByVal index As Integer)
 If index > Count - 1 Or index < 0 Then
 Throw New ArgumentOutOfRangeException( _
 "No item at the specified index.")
 Else
 List.RemoveAt(index)
 End If
 End Sub
 
 Default Public Property Item(ByVal index As Integer) As Customer
 Get
 Return CType(Me.List.Item(index), Customer)
 End Get
 Set(ByVal Value As Customer)
 Me.List.Item(index) = Value
 End Set
 End Property
 
End Class

Here's a simple test of the type-safe CustomerCollection:

Dim Customers As New CustomerCollection()
 
' This succeeds.
Customers.Add(New Customer(1001, "Henry", "Bloge"))
 
' This fails at compile time.
Customers.Add("This is a string")

One limitation of the CollectionBase approach is that you can only create nonkeyed collections (such as the ArrayList). If you need to create a strongly typed dictionary collection, see recipe 3.17.

Incidentally, the .NET Framework includes one strongly typed collection class: the StringCollection class in the System.Collections.Specialized namespace, which only allows String objects.

Create a Strongly Typed Dictionary Collection

Problem

You need to create a key-based collection that can only contain one type of object and rejects attempts to add other data types.

Solution

Create a custom dictionary collection class by deriving from System.Collections.DictionaryBase, and implement type-safe Add, Remove, and Item methods.

Discussion

With a custom dictionary collection, you can place restrictions on the type of objects stored in the collection and on the type of object used to index items in the collection. Internally, the DictionaryBase object uses an ordinary weakly typed Hashtable, which is exposed through the protected property Dictionary. However, external code can't directly access this collection. Instead, it must use one of the type-safe methods you add to your custom class.

As an example, consider the simple Customer object shown in recipe 3.16. Using DictionaryBase, you can derive a type-safe CustomerDictionary that has a strongly typed Add method, which requires an integer key and only accepts Customer objects for insertion in a collection. You'll also implement a Remove method and a default property named Item, which automatically casts the retrieved object to the correct type.

Public Class CustomerDictionary
 Inherits System.Collections.DictionaryBase
 
 Public Sub Add(ByVal key As Integer, ByVal item As Customer)
 Me.Dictionary.Add(key, item)
 End Sub
 
 Public Sub Remove(ByVal key As Integer)
 Me.Dictionary.Remove(key)
 End Sub
 
 Default Public Property Item(ByVal key As Integer) As Customer
 Get
 Return CType(Me.Dictionary.Item(key), Customer)
 End Get
 Set(ByVal value As Customer)
 Me.Dictionary.Item(key) = value
 End Set
 End Property
End Class

Here's a simple test of the type-safe CustomerDictionary:

Dim Customers As New CustomerDictionary()
Dim CustomerA As New Customer(1001, "Henry", "Bloge")
 
' This succeeds.
Customers.Add(CustomerA.ID, CustomerA)
 
' This fails because the object is not a Customer.
Customers.Add(9024, "This is a string")
 
' This fails because the ID is not an integer.
Customers.Add(CustomerA.FirstName, CustomerA)

Incidentally, the .NET Framework includes one strongly typed dictionary class: the StringDictionary class in the System.Collections.Specialized namespace, which only allows String objects.

Remove Items While Iterating Through a Collection

Problem

You need to search for items and delete them. However, you can't delete items while iterating through a collection.

Solution

Add the items that you want to delete to another collection. Then iterate through this collection and remove all items from the original collection.

Discussion

Enumerating through a collection is strictly a read-only operation. However, you can enumerate through a collection to find the items you need to remove, and then delete them in a second step, as shown below.

Dim List As New ArrayList()
List.Add("This")
List.Add("is")
List.Add("a")
List.Add("simple")
List.Add("test")
 
' Mark words that start with "t" for deletion.
Dim ItemsToDelete As New ArrayList()
Dim Item As String
For Each Item In List
 If Item.Substring(0, 1).ToUpper() = "T" Then
 ItemsToDelete.Add(Item)
 End If
Next
 
' Delete the words that are marked for deletion.
For Each Item In ItemsToDelete
 List.Remove(Item)
Next
 
' Display remaining (3) items.
For Each Item In List
 Console.WriteLine(Item)
Next

This two-step approach requires very little additional memory. Even if you are storing large items in a collection, you'll simply copy the reference, not the object content, to the new collection.

Some collection types, such as the ArrayList, allow you to remove items by index number. In this case, you can use the slightly more efficient code below that does not require a search when looking up the items for deletion:

Dim ItemsToDelete As New ArrayList()
Dim Item As String
 
' Move through the list by index number, and store the index number
' of every item that needs to be deleted.
Dim i As Integer
For i = 0 To List.Count - 1
 Item = CType(List.Item(i), String)
 If Item.Substring(0, 1).ToUpper() = "T" Then
 ItemsToDelete.Add(i)
 End If
Next
 
' Count backward to prevent index renumbering problems.
Dim Index As Integer
For i = (ItemsToDelete.Count - 1) To 0 Step -1
 Index = CType(ItemsToDelete(i), Integer)
 List.RemoveAt(Index)
Next

Iterate Through Collection Items in Random Order

Problem

You need to enumerate through all the items in a collection, but you don't want to visit items in order.

Solution

Create the RandomIterator class shown below, and use it to store an ArrayList of randomly ordered items.

Discussion

By default, enumeration moves through the items of a collection in order from first to last. And while it's easy to randomly select a single item in a collection using the Random class, it's more difficult to randomly walk through all items in a collection and ensure that each one is visited only once.

The solution is the RandomIterator class shown below. It stores a private collection and inserts all items into that collection in a random order. You can then walk through this collection of randomly ordered items.

Public Class RandomIterator
 Implements IEnumerable
 
 Private Items As New ArrayList()
 
 Public Sub New(ByVal collection As IEnumerable, _
 Optional ByVal seed As Integer = 0)
 Dim Rand As Random
 If seed = 0 Then
 Rand = New Random()
 Else
 Rand = New Random(seed)
 End If
 
 Dim obj As Object
 For Each obj In collection
 Items.Insert(Rand.Next(0, Items.Count + 1), obj)
 Next
 End Sub
 
 Public Function GetEnumerator() As System.Collections.IEnumerator _
 Implements System.Collections.IEnumerable.GetEnumerator
 
 ' Return the enumerator for the internal collection.
 Return Items.GetEnumerator()
 End Function
 
End Class

The constructor performs most of the work for the RandomIterator class. It accepts a collection object and duplicates all the items into the internal collection, inserting them at random positions. Remember, if your collection stores reference types, this operation doesn't actually clone the object; it simply copies the reference. (Thus, it doesn't matter which collection you use to access the object, you are still working with the same object.) Once the internal ArrayList is filled, you can call GetEnumerator to enumerate through the collection of randomly ordered objects.

Note

You'll notice that the constructor optionally accepts a seed for the random number generator. You should set this value if you need to create several RandomIterator objects at the same time. Otherwise, on a fast computer the items could conceivably be created at the same millisecond, given the same seed value, and then ordered in the same "random" order.

The following example shows a Console application that puts the RandomIterator class at work:

Public Module RandomIterationTest
 
 Public Sub Main()
 Dim Colors() As String = {"blue", "green", "pink", "yellow"}
 Dim Color As String
 
 For Each Color In New RandomIterator(Colors)
 Console.WriteLine(Color)
 Next
 Console.WriteLine()
 
 For Each Color In New RandomIterator(Colors)
 Console.WriteLine(Color)
 Next
 
 Console.ReadLine()
 End Sub
 
End Module

Both of these lists are randomly sorted. Here's an example of the output you might see:

yellow
blue
pink
green
 
blue
pink
yellow
green

This example is adapted from a sample first provided by VB-2-The-Max (http://www.vb2themax.com).