Managing Collections of Objects

Our applications often need to manage data in groups. For instance, we may have a set of similar database records that we want to iterate through, or perhaps we need to sort values in an array. To do so, we typically place this data into a collection for easy management and storage. A collection is simply a class that exposes properties and methods for working with a group of like data. Collection classes often implement standard interfaces that allow us to retrieve, count, and generally order our data in our application.

Depending on our design and requirements, a surprising number of collection strategies are available to us. The Framework Class Library exposes all-purpose collections (such as the ArrayList) as well as highly specialized collections (such as BitArray). The more specialized a given collection class, the more limited it is to its specific purpose. Because of the large variety of collections available, this section will detail a number of collections and demonstrate their usage.

System.Collections Namespace

Collections differ based on how elements are stored, sorted, searched, and compared. These are the key considerations to examine when searching for the right class for the task at hand. For example, items in collections are typically accessed by a key value or by indicating the index of the item. Additionally, classes such as Queue and Stack are used to store items you expect to remove from a collection. Table 19.1 presents the various collections in the library across these parameters.

Stack

The Stack collection class stores objects in the reverse order they were placed in the collection. That is, adding a tenth item to a collection with nine items makes the new item the first item in the collection and pushes each subsequent item down the “stack.” One becomes two, two, three, and so on. As items are accessed or removed from the stack, they are done so sequentially. So even though item one represents the last item to be added (10), it is the first item to be accessed. This is also known as “last in, first out.”

One interesting thing about a stack is that you cannot change an item's value after it has been placed on the stack. You can only remove it from the stack.

Stacks can be very useful in the right context. They offer temporary storage for data that is accessed in a particular manner. One of the most common uses of the stack collection is to store the state of an object or variable between calls.

Constructors

Three constructors are available for creating a Stack instance. The first, which takes no parameters, creates a Stack object with a default initial capacity of 10. The Stack class doubles its current size when its capacity is reached. If you have a good idea of what your Stack size will be, you can save the overhead of doubling every time the capacity is reached, or from allocating more memory than is necessary, by using the constructor, New Stack(initialCapacity as Integer). This constructor lets you initialize the Stack object to your intended size. Last, you can create a new Stack instance from an existing collection object. This constructor takes an instance of a collection object derived from the ICollection interface. Items are added to the Stack object, based on the order they are enumerated, using the IEnumerable interface. We'll discuss these interfaces in greater detail in just a minute.

Properties and Methods

The key methods for working with a Stack object are Push, Pop, and Peek. Items are said to be pushed onto the stack, popped off the stack, or peeked at. Table 19.2 is a reference detailing the key properties and methods of the Stack collection class.

Dim myStack As New Collections.Stack()
Dim myEnum As IEnumerator

'add items to the stack ...

myEnum = myStack.GetEnumerator

Do While myEnum.MoveNext <> False
  Console.WriteLine(myEnum.Current)
           Loop

Learning by Example: Stack Collection

In Listing 19.1, we create a simple class, called StackClass, that monitors internal calls to various functions similar to a call stack. The class exposes one function, SomeFunction, which uses a random number to simulate code logic and in turn calls other internal functions. Each function pushes a value onto the stack when it is called. The resulting Stack collection is exposed as a property of the class CallStack.

Additionally, we create a console application that creates an instance of StackClass, calls its function, and writes the Stack contents to the command window.

Listing 19.1. A Simple Call Stack

Module Module1

  Sub Main()

    'local scope
    Dim myStackClass As New StackClass()
    Dim i As Integer

    'call the class' function
    myStackClass.SomeFunction()

    'write out the stack
    For i = 1 To myStackClass.CallStack.Count
      Console.WriteLine(myStackClass.CallStack.Pop)
    Next

    'pause
    Do While Console.ReadLine <> "s" : Loop

  End Sub

End Module

Public Class StackClass

  'global stack collection object
  Private myStack As Collections.Stack
  Private myRandom As New Random()

  Public Sub New()

    'purpose: create an instance of the stack collection
    '         within the object's constructor
    myStack = New Collections.Stack(initialCapacity:=15)

  End Sub

  Public Function SomeFunction()

    'purpose: simulate logic with random numbers, track procedure
    ' calls using a stack instance

    'push this function onto the stack
    myStack.Push(obj:="SomeFunction")

    'some logic ... random number
    If myRandom.Next(maxValue:=3) = 2 Then
      Call SomeFunction2()
    Else
      Call SomeFunctionElse()
    End If

  End Function

  Private Function SomeFunction2()

    'purpose: demonstrate call stack

    'push this function onto the stack
    myStack.Push(obj:="SomeFunction2")

    'some logic ... random number
    If myRandom.Next(maxValue:=3) = 2 Then
      Exit Function
    Else
      Call SomeFunctionElse()
    End If

  End Function

  Private Function SomeFunctionElse()

    'purpose: demonstrate call stack

    'push this function onto the stack
    myStack.Push(obj:="SomeFunctionElse")

    'some logic ... random number
    If myRandom.Next(maxValue:=4) = 2 Then
      Exit Function
    Else
      Call SomeFunction2()
    End If

  End Function

  Public ReadOnly Property CallStack() As Collections.Stack

    Get
      'return the stack object for examination
      Return myStack
    End Get

  End Property

End Class
							

Queue

The Queue class is the opposite of the Stack collection and mimics the functionality most closely associated with a message queue. Items are added and removed from a queue in a “first-in, first-out” (FIFO) order. That is, the oldest item in the queue has the top priority and is removed first. Queues are best used for managing message priority and transaction order. Unlike message queues, the Queue collection class is persisted only in memory and not to disk.

Constructors

Four options are available for creating a Queue instance. The first allows us to create a Queue instance that takes no parameters. It simply creates a Queue object with an initial capacity of 32 and a growth factor of 2. The initial capacity defines the starting size of the queue. When this size is reached, the queue is expanded by multiplying its current size by the growth factor (in this case it, doubles the queue's size).

The second constructor enables you to indicate the initial size using the parameter capacity as Integer for the Queue collection. This can save the overhead of doubling every time the capacity is reached or from allocating more memory than is necessary.

A third constructor, capacity as Integer, growFactor as Single, enables you to indicate both the starting capacity and the value by which the capacity is multiplied when the Queue instance reaches its maximum.

Last, you can create a new Queue instance from an existing collection object. This constructor takes an instance of a collection object derived from the ICollection interface. Items are added to the Queue object based on the order in which they are enumerated using the IEnumerable interface.

Properties and Methods

The methods used most often when working with the Queue class are Enqueue and Dequeue. Table 19.3 details these and other key properties and methods of the Queue collection class.

Learning by Example: Queue Collection

Listing 19.2 is a simple console application that writes three items to a Queue collection instance using the Enqueue method. It then pulls those items out of the collection using the Dequeue method. The results are output to the console window.

Listing 19.2. Queue Collection

Module Module1

  Sub Main()
    'purpose: demonstrate queue collection class

    'local scope
    Dim myQueue As Collections.Queue
    Dim i As Int16

    'create new instance
    myQueue = New Collections.Queue(capacity:=3)

    'add items to the queue
    myQueue.Enqueue(obj:="Item 1")
    myQueue.Enqueue(obj:="Item 2")
    myQueue.Enqueue(obj:="Item 3")

    'write queue contents to the console
    For i = 1 To myQueue.Count

      'remove the item from the queue
      Console.WriteLine(myQueue.Dequeue())

    Next

    'pause
    Do While Not Console.ReadLine = "s" : Loop

  End Sub

End Module
							

ArrayList

The ArrayList collection class is best used for working with a group of objects after they have been added to the collection. Unlike Stack and Queue, the ArrayList collection enables you to modify the value of an item after it has been added. Additionally, you can use the Sort method to order the items in the array or the Reverse method to reverse all the items in the array. The class has strong support for working with items as a range. Methods such as AddRange, GetRange, InsertRange, and SetRange all support the manipulation of the ArrayList in chunks. A number of methods also are used to find items within the collection, including BinarySearch, Contains, IndexOf, and LastIndexOf. If you need a powerful and flexible collection object that enables you to do a lot of manipulation on the collection, rather than simple storage, you should consider an ArrayList.

Constructors

Three options are available for creating an ArrayList instance. The first, which takes no parameters, creates an ArrayList object with a default initial capacity of 16. The initial capacity defines the starting size of the queue. When the ArrayList reaches its capacity, it automatically doubles its capacity.

The second constructor enables you to indicate the initial size of the ArrayList collection, capacity as Integer. Provided that you have a good idea of the size your collection needs to support, this can save the overhead of doubling or from allocating more memory than is necessary.

Last, you can create a new ArrayList instance from an existing collection object. This constructor takes an instance of a collection object derived from the ICollection interface. Items are added to the ArrayList object based on the order in which they are enumerated using the IEnumerable interface.

Properties and Methods

Table 19.4 details key properties and methods of the ArrayList collection class.

Learning by Example: ArrayList Collection

In Listing 19.3, we create an ArrayList collection. We add five items to the collection using the Add method. We then call Sort followed by Reverse. We use GetRange and GetEnumerator to display a range of items in the array list. Then, we use the IndexOf method to display the position of an item in the collection. Finally, we call the RemoveRange method to remove three items from the array list.

Listing 19.3. ArrayList

Module Module1

    Sub Main()

        'local scope
        Dim myArray As New Collections.ArrayList()
        Dim myRange As Collections.ArrayList
        Dim myEnumerator As IEnumerator
        Dim i As Short

        'lower the array's capacity from default
        myArray.Capacity = 5

        'add items to the arrayList
        myArray.Add("Item R")
        myArray.Add("Item E")
        myArray.Add("Item B")
        myArray.Add("Item L")
        myArray.Add("Item F")

        'sort the array
        myArray.Sort()

        'reverse the array
        myArray.Reverse()

        'check the index of an item (array is zero-based)
        Console.WriteLine(myArray.IndexOf("Item E"))

        'pull 2 items out of the array using GetRange
        myRange = myArray.GetRange(3, 2)

        'write range items out
        myEnumerator = myRange.GetEnumerator
        Do While myEnumerator.MoveNext
            Console.WriteLine(myEnumerator.Current)
        Loop

        'delete 3 items out of the array
        myArray.RemoveRange(2, 3)

        'write out new count
        Console.WriteLine(myArray.Count)

        'pause
        Do While Console.ReadLine() <> "s" : Loop

    End Sub

End Module
							

Hashtable

The Hashtable class provides fast and easy access to items based on key values. Users of VB's dictionary object will find the Hashtable class very familiar because it derives from the interface IDictionary.

Items are added to a Hashtable collection using a unique key value. In turn, keys are internally converted to hash codes. A hash code is a numeric value that represents the unique key. Hash codes are used to identify buckets inside the collection. Buckets are a subgroup of elements within the collection; splitting the collection into buckets makes access and retrieval of elements faster. When the collection is partitioned into buckets and each bucket is indexed by a hash code, there is no need to search the entire collection for an item. Instead, the bucket is accessed based on the key and the item returned.

The Hashtable class is best used when working with items that naturally contain a unique key. A row in a recordset is a good example of a candidate. Each column represents a unique key for the value it contains. Users access the values by indicating the column name or key.

Constructors

The Hashtable class can be created using a large variety of constructors. The quantity is simply the result of the various combinations of all the possible parameters that can be passed on the constructor. Rather than list all these constructors, we'll describe all the possible parameters and define how you might use them.

• capacity as Integer— Indicates the number of Hashtable buckets to be allocated to the collection. The default capacity for a Hashtable instance is zero.

• d as IDictionary— Creates an instance of a Hashtable class from a collection object derived from an IDictionary interface.

• loadFactor as Single— Indicates the ratio of items in the collection to Hashtable buckets that store the items. A smaller value provides faster lookup but consumes more memory. The default value is 1.0, indicating a ratio of one item per bucket.

• hcp as IHashCodeProvider— Indicates the class that provides the hash code. Valid classes are those that inherit from IHashCodeProvider.

• comparer as IComparer— Indicates the comparer to use when creating the Hashtable instance.

Properties and Methods

Table 19.5 details key properties and methods of the Hashtable collection class.

Learning by Example: HashTable Collection

Using the Hashtable collection class is straightforward. In Listing 19.4, we use the Add method to add four items to the collection and then reference two of those items by their keys and write their contents to the console window.

Listing 19.4. Hashtable

Module Module1

  Sub Main()

    'purpose: demo hashtable collection

    'local scope
    Dim myHashtable As New Collections.Hashtable()

    'add items to the collection
    myHashtable.Add(key:=1, value:="Microsoft")
    myHashtable.Add(key:=2, value:="Visual")
    myHashtable.Add(key:=3, value:="Basic")
    myHashtable.Add(key:=4, value:=".NET")

    'return the hash code of a specific item
    Console.WriteLine(myHashtable.Item(key:=2) _
      & myHashtable.Item(key:=3))

    'pause
    Do While Console.ReadLine() <> "s" : Loop

  End Sub

End Module
							

Thread Safety and Synchronization

Thread-safe is a term that indicates whether multiple threads can access an object simultaneously; if an object does not allow this type of access, it is considered to be thread-safe. The safe portion of the terms connotes the many problems that can occur when two threads access—and change—the global data of an object at the same time (see Chapter 12, “Working with Threads,” for more detail).

By default, the collection classes in the System.Collections namespace are not thread-safe. In fact, the majority of objects in the .NET Framework Class Library are not thread-safe. The reason has to do with performance. The process of making objects thread-safe degrades performance.

This process of ensuring thread safety is called synchronization. Synchronization ensures that properties and methods of a given object are accessed by only one thread at a time. Sounds good and safe, right? It is, but it requires the CLR to block threads from accessing synchronized objects while another thread is executing a method or property. However, blocking equates to a performance penalty. Therefore, thread safety via synchronization requires a performance hit.

This undesired performance hit coupled with the fact that the majority of .NET applications will execute on a single thread makes objects in the library not thread-safe by default. If, however, you need a thread-safe version of a given object, typically an appropriate synchronization method exists.

The collection classes that we've discussed thus far have an IsSynchronized property. This property is of the type Boolean. The property returns True if the collection class instance is synchronized. To create a synchronized version of a given collection, you use the Synchronized method. This method returns a synchronized wrapper for your collection class. The method takes the instance of the collection you want synchronized as its parameter.

The following code snippet creates an ArrayList object, adds a few items to the collection, and then outputs a thread-safe version.

Dim myArray As New Collections.ArrayList()
Dim mySafeArray As Collections.ArrayList

myArray.Add(value:="Test 1")
myArray.Add(value:="Test 2")
myArray.Add(value:="Test 3")
mySafeArray = myArray.Synchronized(list:=myArray)

Console.WriteLine(myArray.ToString & ": " & myArray.IsSynchronized)
Console.WriteLine(mySafeArray.ToString & ": " _
  & mySafeArray.IsSynchronized)
						

Suggestions for Further Exploration

• The BitArray class provides compact storage for an array of True and False values.

• The SortedList class provides a collection based on key/value pairs and is sorted by the collection's keys.

• Check out the namespace System.Collections.Specialized for more specialized collection classes. For example, the ListDictionary class provides Hashtable-like functionality on small groups of objects (10 or fewer). The classes StringCollection and StringDictionary are also available for manipulating collections of string values.