Chapter 6: Collections of Objects

The properties and behaviors of some common collection types,How collections enable us to model very sophisticated real-world concepts or situations,How we can define our own collection types

More Sophisticated Collection Types

In an OO language, there are typically many different types of collections available to us as programmers, arrays being arguably the most primitive. There are several problems with using an array to hold a collection of objects:

• It's often hard for us to predict in advance the number of objects that a collection will need to hold-e.g., how many students are going to enroll this semester ? However, as mentioned earlier, arrays require that such a determination be made at the time they are first instantiated and, once sized, can't be expanded. So, to use an array in such a situation, we'd have to make it big enough to handle the worst-case scenario, which isn't very efficient. On the other hand, when we do know how many items we're going to need to store-say, the abbreviated names of the 12 months in a year-an array might be a fine choice.
   
• We also talked earlier about the "land mine"issues inherent in arrays.

Fortunately, OO languages provide a wide variety of collection types besides arrays for us to choose from, each of which has its own unique properties and advantages. Let's talk about the general properties of three basic collection types found in most OO languages:

• Ordered lists
   
• Sets
   
• Dictionaries

Then, in Chapter 13, we'll illustrate some specific C# implementations of these collection types.

Ordered Lists

An ordered list is similar to an array, in that items can be placed in the collection in a particular order and later retrieved in that same order. Specific objects can also be retrieved based on their position in the list; e.g., retrieve the second item. One advantage of an ordered list over an array, however, is that its size doesn't have to be specified at the time that the collection object is first created; an ordered list will automatically grow in size as new items are added (see Figure 6-6). (In fact, virtually all collections besides arrays have this advantage!)


Figure 6-6. Collections other than arrays grow gracefully as needed.

By default, items are added at the end of an ordered list unless explicit instructions are given to insert a new item somewhere in the middle.

When an item is removed from an ordered list, the "hole"that would have been left behind is automatically closed up as shown in Figure 6-7. This is actually true of most collection types other than arrays, and so we don't generally speaking encounter the "land mine"problem with nonarray collections.


Figure 6-7. Collections other than arrays automatically shrink as items are removed.

An example of where we might use an ordered list in building our Student Registration System would be to manage a wait list for a course that had become full. Because the order with which Student objects are added to the list is preserved, we can be fair about selecting students from the wait list in first-come, first-served fashion should seats later become available in the course.

The C# ArrayList class is a specific example of an ordered list implementation.

Sorted Ordered Lists

A sorted ordered list is a special ,type of ordered list: when we add an object to a sorted ordered list, the list automatically inserts the object at the appropriate location in the list to maintain sorted order, instead of automatically adding the new object at the end of the list as with a generic ordered list.

With a sorted ordered list, we have to define the basis upon which the objects will be sorted, i.e., we must define a sort key. For example, we may wish to maintain a list of Course objects sorted by the value of each Course's courseNo attribute for purposes of displaying the SRS course catalog.

Note that we could accomplish the same goal using a generic ordered list, but then the burden of keeping things sorted properly is on us, the programmers, instead of on the collection object! That is, we'd have to step through the (unsorted) list, comparing a newly added item's value to the value of each object already in the list until we found the correct insertion point, in order to preserve sorted order.

Sets

A set is an unordered collection, which means that there is no way to ask for a particular item by number once it has been inserted. Using a set is like throwing an assortment of differently colored marbles into a bag: we can reach into the bag to pull the marbles out one by one, but there is no rhyme or reason as to the order with which we pull them out. Similarly, with a set, we can step through the entire collection of objects one-by-one to perform some operation on them; we just can't guarantee in what order the objects will be processed. We can also perform tests to determine whether a given specific object has been previously added to a set or not, just as we can answer the question "Is the blue marble in the bag?"(See Figure 6-8.)



Figure 6-8. A set is an unordered collection.

Note that duplicate object references aren't allowed in a set. If we were to create a set of Student object references, and a particular Student object reference had already been placed in that set, then the same Student object reference couldn't be added to the set a second time; the set would reject it. This isn't true of collections in general, however: if we wanted to, we could add a reference to the same Student object to an ordered list, for example, multiple times (see Figure 6-9).


... UNLESS the collection is a set!

Figure 6-9. Collections other than sets accommodate mutiple references to the same object.

An example of where we might use sets in building our Student Registration System would be to group students according to the academic departments that they are majoring in.Then, if a particular course-say, Biology 216-requires that a student be a Biology major in order to register, it would be a trivial matter to determine if a particular student is a member of the Biology Department set or not.