Bag ADT using Dynamic Array – 3

We now look at the implementations of the resize, insert and remove member functions.

4. We begin with the resize member function: void resize ( size_t new_cap);

This function allocates new memory in the heap equal to that needed to store new_cap number of Items.

We note that if capacity == new_cap, we do not need to do anything. Also, if new_cap < used, then obviously, since we cannot allow that to happen, we set new_cap = used.

Once we have allocated new memory, we copy Items to that location, after which we free the old memory.

——

void Bag:: resize (size_t new_cap)

{

if (capacity == new_cap)

return;

if (new_cap < used)

new_cap = used;

//allocate new memory.

Item *new_data = new Item[new_cap];//new_handler gets called in case of failure.

//copy old items to new memory.

for (size_t i = 0; i < used; i++)

new_data[i] = data [i];

//free old memory.

delete  [ ] data;

data = new_data;

capacity = new_cap;

}

———

We now look at the insert function.

4. void insert (const Item& entry);

Given that we have the resize function with us, implementing insert becomes that much more easier.

——

void Bag:: insert (const Item& entry)

{

//check if we have space to insert in existing data array.

if ( used == capacity)

resize (capacity + 1);

//insert the Item entry.

data[used] = entry;

used ++;

}

——

5. remove is also simple to implement — bool remove (const Item& target);

In case the Item target is not present in our Bag, we return false. Else, we remove one instance of the Item from our Bag, and return true.

——-

bool Bag :: remove ( const Item& target)

{

for (size_t i = 0; (i < used) && (data[i] != target)  ; i++);

//if target is not present, i == used.

if (i == used)

return false;

//overwrite at the index of target.

data[i] = data[used-1];

used – – ;

return true;

}

——–



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: