array of objects

Objectives:

• Understand the differences using static array versus dynamic array in object design.

• Explore the consequences of designing one way or the other, such as required member, constructor/destructor.

• Using array operations (insert, delete, print, update,....) to understand complexity (big O notation).

Array in object design

A car dealer has name, address and many cars. A shopping cart has customer-id and many items. A stock portfolio has a name and many stocks. A student course has a course number, teacher, and many students. A student record has name and many classes.

Store all these "many" in an array is a straightforward and natural approach. There are two distinct ways of creating array: static and dynamic. What are the differences, consequences, and trade-off? Let's use shopping cart as an example.

case 1: Fixed-size Static Array

class cartTypeS-NoGood {

public:

int id;

itemType goodie[10];

}

Of course, we will have other functions (e.g. addItem, deleteItem etc) as needed. But, there are certain things that we MUST have in the cartType. We must have a size that indicates the number of items currently stored in goodie array. Without it, we won't be able to perform add/delete/print easily. [note: Yes, we can invent an "empty marker" to distinguish empty or occupied array item. I wouldn't recommend it as it causes more complex operations.]

Do we absolutely need a max_size member which indicates the capacity (in our case 10) of the array? One obvious usage for it to verify if our shopping cart is full. Since the max-size of static array is fixed at compile time, it is usually done with a #define constant. Checking max_size can be accomplished by comparing with the #define constant. So, max_size field for a static array is not necessary, but I would recommended it for reasons of simplicity and consistency. When we use dynamic array (as will be discussed next), both size and max_size are required. Life is simpler when it is unified.

#define MAX_SIZE 10

class cartTypeS {

public:

int id;

int size; // must have

int max_size;

itemType goodie[MAX_SIZE];

}

From previous deep-copy discussion, we know we can leverage the default copy constructor and assignment operator overloading. Do we need constructor and destructor? Destructor is not needed as everything is static. The system default will recycle all the static storage. However, we must have constructor because we need to initialize the variables: clear size and set max_size. Hmmm, we need constructor, but why not copy constructor?

case 2: Fixed-size Dynamic Array

class cartTypeDS {

public:

int id;

int size; // must have

int max_size;

itemType * goodiep = new itemType[MAX_SIZE];

}

The above dynamic array is a direct porting from static array implementation carTypeS. It is a "fixed size" dynamic storage. We need to do deep-copy, constructor, desctructor, .. etc. What do we gain? Not much. Program is smaller. No big deal. In fact, we probably lose more. How about another design?

case 3: Variable-size Dynamic Array

class cartTypeD {

public:

cartTypeD (int max);

int id;

int size; // must have

int max_size; // must have

itemType * goodiep;

}

Here we specify a maximum size of the array in constructor. The constructor routine creates a dynamic array to store max number of items and put the pointer to goodiep, such as goodiep = new itemType[max].

This design gives us the flexibility of creating bigger or smaller shopping carts. Yes, we do need to carry the burden of deep copy, but we have a very usable and effective way of dealing with real world scenario.

Do we absolutely need to decide the size of the array during construction? It is commonly done, but not necessary. Look at this design:

case 3a: Two-step Variable-size Dynamic Array

class cartTypeD2 {

public:

cartTypeD2 ();

void set_max_size(int);

int id;

int size;

int max_size;

itemType * goodiep;

}

It is certainly ok to create a cartTypeD2 object without the item array. It would be good practice to set goodiep=NULL and max_size=0 in constructor though. When the object calls set:_max_size, actual storage is created dynamically at that time. This type of design has some complications: user may call set_max_size() multiple times. So, be sure to free previous storage before allocate new ones. Furthermore, do you want to preserve previous items or not? In short, use this approach only when you know exactly what you're doing. Or, shall I say, you should consider using linked list instead.

Discussions:

• 1. Which way is better, cartTypeS, cartTypeDS, cartTypeD, cartTypeD2? The only thing I know is that I can not find many reasons to do cartTypeDS (but I used it myself in sample code too.) The other three mentioned above all have their usages. A political (but true) answer is that it depends on how you want to use it (i.e. the requirements).

  2. Beyond basic constructor / destructor / assignment operator overload, you should implement a few functions (e.g. insertItem, deleteItem) with both cartTypeS and cartTypeD. Compare them and internalize their differences. The array ppt in https://sites.google.com/site/sjsucmpe126/slides has some textbook's example code.

  3. If you have more energy, think about "find-item" in the cartType class? How would you do it? Are there different ways of implementing it? For example, shall we find an item with item's key or find an item with an item object? What's the pros and cons?

  4. Now, we seem to have a good handle on variable number of items in a shopping cart. We do have a limitation though: each item is fixed size. What if some items are much larger than others?