Notes for week 8

For this week no new links.

Design of a Template Class

Throughout the first weeks of this course when we needed an array, we would use darray.h for our array. While c has a primitive data type array, this type is not an object and may cause problems with memory management.

The newest c++ compilers come with a template library that contains an array class. Our version of Borland's c++ has a type called TArray, but it has a few problems (such as not allowing arrays of integers). I avoided these problems by making my own array class. The process of deciding what will go into such a class is instructive in of itself, but in addition we will see many new concepts including: overloading operators, multiple declarations of several functions, the meaning of constant functions, reference return values and templates. I also hope to review iterators and their use.

What Functions and Operators Do You Need in an Array?

Primitive Operators

First we should distinguish between the primitive array found in Pascal, c and most programming languages and our extended version of an array. Primitive arrays usually only have the operators:

assignment operator =
subscript operator [ ]
equality operator ==
not equal operator !=

I found it useful to add a concatenate operator += to this list.

Useful Array Manipulation Functions

You have already seen some applications where we used the array class like a list. This is a fairly common practice with c++ library writers. Why add these extra functions? Frequently you will find programs need functions that add things to an array, delete things from the array and search the array for an item. The two commonest types of insert are insert an item and insert an item at a given position. Similarly we may delete an item whereever that item is in the array or just delete the item at a given position in the array. Once we have imposed this type of structure on an array, it is useful to be able to delete everything in the array and reset the interal values. The clearArray function does this. Summarizing these functions:

addItem - adds an item at the end of the array
addItemAt - adds an item at a designated position in the array
deleteItem - deletes the item if it exists
deleteItemAt - deletes the item at the specified location
find - finds the specified item if it exists
clearArray - clears the array and resets the internal settings
numberInArray - returns the number of items found in the array due to inserts and deletes

I have avoided Borland's problem with arrays of integers by using different names for deleteItem and deleteItemAt. Suppose our array contained items of type Type. We could define the function deleteItem(Type) that would delete the parameter item whereever it is in the list and the function deleteItem(int) that deletes the item at the specified location. We have a problem when the type of item in the array is int. In this case the compile can't tell one deleteItem from the other. These problems can often be avoided by more careful naming. These functions have different purposes, so their names should indicate there distinctive purposes.

Some Diversions

Before completing the list of functions we should stop to consider some of the problems that you may have by extending the list of functions of a primitive type.

Make sure that your new functions don't destroy the operations that already exist. If someone wants to use your array and has existing functions, make sure all of the old things work correctly.
Beware that if you mix the use of [ ] with the list functions you may end up with a non working structure. If for example you use addItem to add three things (say 1, 2, and 3) so the array looks like:
```
0 - 1
1 - 2
2 - 3
```
Then you set array[3] = 5, find(5) will not find 5 since it is only prepared to look up to subscript 2.

Some Functions You Need, But Never Knew You Did

When you implement this design, you will discover the need for additional "housekeeping" functions. We certainly will need at least one constructor -- the default. Some thought about the construction of the array class will lead to more functions.

Other Properties Of This Class

Before we complete the list of functions we have to complete our list of desired properties. One of the things we want to avoid from c is extensive memory management. This often leads to errors in c++, so we will design the class to hide pointers in much the same way we did with RcPointers.

Another thing that would be an improvement over c arrays is range checking. In c it is easy to write over areas outside the array since there is no range checking. There are two forms of range checking:

Check the subscript and if out of range issue an error
Check the subscript and if out of range increase the size of the array so the subsript is in range.

In this class we will have our cake and eat it too. The constructor will allow us to set the amount of resizing. The default resize is 1. This means that exactly enough memory is allocated to allow access to subsripts that exceed the upper limit. If your array will grow frequently, it is best to specify a larger resize. This will allocate larger blocks of memory and avoid problems of memory fragmentation. If you specify resize of zero, the array will have a constant size and attempts to go beyond this size will result in an error. The error throws a message. In no case may your subsript be less than zero.

The find makes use of the fact that subsripts are greater than or equal to zero by returning -1 if the search fails, and the subscript otherwise. When you create an array of anything, you must be sure to define both the == operator and the != operator for the data type stored in the array. This is a good habit to foster since many template classes assume that these operators exist.

Actual construction of this class is completed in week 9.