Bag ADT using Dynamic Array – 3
February 13, 2011 Leave a comment
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)
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;
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)
//overwrite at the index of target.
data[i] = data[used-1];
used – – ;