In the last two chapters we have worked with a number of contract instances. Each instance had to have its own unique name and had to be passed separately to any module needing it. In real world situations collections of items such as contracts are often passed around, manipulated, and handled together as one unit. There might be a file of contracts, a gradebook of grades, a database of employees, or a roster of students. In this chapter we look at one way to represent a collection of items that are all of the same type.

A. Chunking
Studies of human intelligence have shown that humans can only hold a limited number of elements in their immediate awareness at any one time. Imagine yourself juggling balls. You can visualize two balls, probably three, four or five. However, very quickly, you reach the maximum number of balls you can visualize at once. Some psychologists refer to the "magic numbers 3-7", indicating that we can be aware of somewhere between three and seven elements at any one time. Regardless of the exact number, it is a fact that there are sharp limits to what we can handle in our immediate awareness. That is one reason this text pushes the idea of functional and object-based decomposition.

It turns out that humans handle this limitation by grouping or 'chunking' items together. Consider phone numbers. By breaking phone numbers up into elements - area code, prefix, last 4 digits - they become easier to remember and manipulate. When you call a long distance number, you start by holding in your head these three chunks. Then, as you dial each chunk, you break out its parts. To begin, you consider the area code as three separate digits, while still keeping the chunked prefix and last part, for a total of five elements. Then, when you are finished dialing the area code, you decompose the prefix into its three numbers etc.

We perform this chunking process with both objects and operations. For example, we put a label on the steps for some activity - studying for a test, coaching basketball, dancing a polka, or writing a computer program. In fact, when it comes to writing programs, this is just what we are doing with functions and classes. For example, we group together a collection of instructions as a function and give it a name. Likewise, we determine the properties and actions of some element of our problem, group these together as a class, and give that class a name. This process works because it is in line with the natural processes humans use for handling complexity.

B. The Array as a Chunking Mechanism
In this chapter we look at a different grouping mechanism, one that groups together some number of elements all of the same type. These groups of the same type are called arrays. Contrast this array type with the 'class' in which the properties may be of all different types.

Consider a program that keeps track of a store's inventory - how many of each item that the store sells are on hand. To keep things simple, assume that each item has a numeric code and that these codes go from 1 to 10,000. In other words, we will assume that the store sells 10,000 different items, each with a unique code in the range 1 to 10,000. Now, one way to handle this in a program would be to have a unique variable for each item. This would require 10,000 variables! Imagine the code you would need to write, for example, to handle reducing the inventory when some quantity of an item is sold. To record the inventory reduction, you would have to write an input routine that got the item code (easy to do with check-out scanners - in fact that is one of their purposes), followed by a giant 'switch' statement to perform the operation that would reduce the count for that specific item. Switch statements are nice, but imagine one with 10,000 branches:

switch(itemCode)
{	case 1: 
		item1 -= amountSold
		break;
	case 2:
		item2 -= amountSold
		break;
	case 3:
		item3 -= amountSold
		break;
	.
	.
	.
	case 9999:
		item9999 -= amountSold
		break;
	case 10000:
		item10000 -= amountSold
		break;
}

You would have to write similar code to handle shipments of new items (increasing the inventory counts) and inventory reports.

There are three things to note here. First, the problem itself is relatively simple and if the store only sold four or five items, you could write this code with what you already know. In other words, we need a way to perform the operations we already understand how to perform but in a way that reduces the repetition involved in handling large quantities. Second, we need a way to declare that 10,000 items exist, without having to name each one separately. Third, we need some way to get access to each individual item on its own. These last two requirements can be re-phrased as - we need a way of referring to a whole collection of data with one name AND, at same time, we need to have access to the individual elements of that collection.

This is what the array provides us. With it, one can write a declaration that sets aside enough memory for 5, 500, 5,000, or whatever number of individual elements of some type AND gives all these memory locations one name. The types involved can be the built-in ones (integer, double, character, bool) or they can be a user defined type such as a class type or array type.

Back to our inventory problem. We know the number of items - 10,000 - and making up a name for the inventory is not too hard - how about itemInventory. Now, what type should we use in our declaration? To answer this question, we need to ask what the 10,000 memory locations we are about to set up will hold. Since we are recording the amount of each item in stock and assuming one never has a fraction of an item (something to discuss at specification time), we can conclude that the type should be 'int'. Here then is the declaration:

int itemInventory[10000];

The declaration is the same as what we have seen in the past except for the number inside the square brackets. It represents to the compiler the number of integers to be set aside under the name 'itemInventory'.

The question of the type of an array can be confusing. In answer to the question above, you might have been tempted to say that these memory locations will hold the item codes. We will see in a moment that the item codes are used to 'name' the individual elements of the array, but the array elements do NOT contain item codes. To hopefully make this clearer, consider the related problem of maintaining the price of each item. Again, we need an array of 10,000 elements but this time each element holds a price. Since prices are represented in C++ with 'doubles', our declaration would now be:

double itemPrices[10000];

Both arrays will use the item codes to access the individual elements of the array, but the type of the second array has changed to 'double', since the array holds prices.

If these two variables (itemInventory and itemPrices) were declared in the same program, the compiler would need to set aside enough memory for 10,000 integers and enough separate memory for 10,000 doubles. Both of these memory blocks would be contiguous, meaning that all 10,000 integers would be next to each other and all 10,000 doubles would be next to each other. Figure 7.1 shows how memory might look. Note how both arrays have 10,000 contiguous memory locations labeled from 0 to 9999 but that the array of doubles takes up more space.

Figure 7.1

When a program containing these two arrays is run, it is up to the system to find enough memory in RAM for these two large memory blocks or stop. If you have ever run a program and received an out of memory error (especially in the old DOS game programs), this might have been part of the problem.

Top of Section

Main Menu

Next Section