Keys and Indexes

Context

The chart depicts the typical evolution of a software project. At the beginning, not much code is produced. The quality requirements for this code, though, is tough. Since everything else will rely on the code written in the first phase, this code needs to be thoroughly debugged. Just as you wouldn't want to build a house on a bad foundation, you don't want to start coding the application without a sound basis.

One of the hairy problems when writing programs with dynamic memory allocation (i.e. using new and delete), are memory leaks. This happens when memory allocated with new is not freed with a corresponding delete.

There are some obvious places where memory leaks are likely to happen, and some less obvious ones:

• memory allocated in a constructor should be freed in the destructor.
• when data is overwritten, the memory allocated should be freed before overwriting.

The second case happens in an assignment (operator=()) or in the readContents() function. In both cases, new data replaces data that was there previously. It is very easy to forget to free the memory allocated for the old data.

The tests in this week's exercise will run your code several times and check if memory usage remains constant.

Exercises

Change 5

We will extend the List class to include a copy constructor and an assignment operator. Lists should behave just like any other object, so that you can copy lists by using a simple statement like:

...
List list1, list2;

list1.read();
list2 = list1; // make a copy of list1.
...

The test will thoroughly exercise your code and check for memory leaks.

Change 6

In anticipation for next week's pointer classes, we will want to create indexed lists. This means we would like to be able to search lists for a key value. The key value we will use a simple string with no whitespaces.

In case there is no defined value for a key, we will use the string <nil>.

You should use some of the auxiliary functions defined in Base.h. In particular, please use:

IOstatus read(char*& word)

Reads a sequence of characters up to the next white space. This function automatically allocates memory for the string read. You just need to supply a pointer. For example:

virtual IOstatus Key::readContents()
{
  return ::read(key_);
}

Note how we use :: to tell the compiler we want the read() function which is not a member of any class, and not the read() member function of the Base class. Also, note that the example is incomplete. There is a memory leak right there - fix it!

IOstatus write(char* word)

This function does basically the same thing as cout << word;. Writing out stuff is always easier than reading it...

char* newString(char* word)

Allocates memory and copies the supplied string into it. Does automatic error checking if we run out of memory.

Copy the provided header file Key.h and implement Key.C. Once again, the tests will severly challenge your code for memory leaks. The good news is, though, that this is the last class to use dynamic memory allocation, and that we never, ever need to worry about memory leaks again in all the rest of the monopoly project.

Note that during compilation, you will get many warnings about "non-const" and "using temporaries". We will fix this in change 11.

Change 7

This is an easy one. We will extent the List class so that it uses the Key class. Note how already in the description, we can distinguish between inheritance and containment:

An Indexable is a Listable that has a Key. An Index is a List that has a search function.

Actually, it has two: search forward and search backward, which supercede head() and last().

Once again, use the provided header file Index.h and implement Index.C. Note how the constructors use initialisers to properly initialize their data members and their base classes.

The tests are fairly basic, but instructive. Note how TestObject inherits from Indexable, and how the TestObject::readContents() function calls the Indexable::readContents() function.