Lab 7
You cannot submit for this problem because the homework's deadline is due.
EECS 280 Lab 7: Dynamic Memory
Lab Due Tuesday, June 18, 2024, 11:59 pm
In this lab, we will modify IntVector
from the previous lab by using dynamically allocated arrays to support storage of arbitrarily many elements.
Completion Criteria/Checklist:
To pass this lab, you must finish tasks 1 and 2.
Lab Exercises
The Files
Here's a summary of this lab's files.
File | Description |
---|---|
ArrayIntVector.h |
Contains the interface of ArrayIntVector . |
ArrayIntVector.cpp |
Contains implementations for ArrayIntVector . |
lab07.cpp |
Contains the main function that runs testing code. |
Testing Code
The main
function in lab07.cpp
contains testing code we've written for you, printing the correct results and those produced by your code for you to compare.
The starter code should compile successfully without any modifications, so make sure you are able to compile and run it with the following commands. The code may be missing some pieces, contain some bugs, or crash when you run it, but you'll fix each throughout the course of the lab.
$ g++ -Wall -Werror -g -pedantic --std=c++17 ArrayIntVector.cpp lab07.cpp -o lab07.exe
$ ./lab07.exe
Introduction
Changes to the IntVector ADT
The IntVector
we implemented last time had a significant restriction -- the capacity of the data
member that stores elements was fixed at compile time, as required by C++ for non-dynamic arrays. This leads to two problems:
An
IntVector
that only stores a few elements wastes a lot of memory, since it has an array member with a much larger capacity than it needs.An
IntVector
cannot store more elements than the space it has in its member array, so we cannot createIntVector
s that store a lot of elements.
In this lab, we fix these problems by decoupling the storage of the elements from that of the vector itself. Rather than storing the elements in an array that lives directly inside the vector object, we store them in a dynamic array and just keep around a pointer to the first element. The new ADT, which we call ArrayIntVector
, is declared in ArrayIntVector.h
. Read the comments for more details, and take note of a few things in particular:
The
data
member is not an array itself, but a pointer to the first element of a dynamically allocated array.There is no longer a fixed capacity restriction. Instead, each
ArrayIntVector
has its ownelts_capacity
member variable whose value matches the current capacity of the dynamically allocated array.Since we are making use of dynamic memory,
ArrayIntVector
now has an explicit destructor for cleaning up the dynamically allocated array when anArrayIntVector
dies.
Task 1 - Growing
Start by compiling and running the test code we've provided. One of the representation invariant assertions (num_elts <= elts_capacity
) will fail when the code gets to the part of main
that adds 2 one hundred times, since we specified an initial capacity of only 5 when the array was created (at the top of main
).
To fix this, let's make ArrayIntVector
increase its capacity when it needs to add a new element but doesn't have enough room. Internally, this means the ArrayIntVector
will dynamically allocate a new, larger array to hold its elements. This is done in the private member function grow
; go ahead and implement it in ArrayIntVector.cpp
.
After implementing grow
, remember to add code in push_back
to call grow
when needed.
Note: make sure to run the testing code again to check that it actually works.
Task 2 - Destructors
Next, check the code for memory leaks using Valgrind. You should find that after completing Task 1, our implementation of ArrayIntVector
is leaking memory, which means we are not freeing all the memory we allocate. You might find this tutorial helpful:
https://eecs280staff.github.io/tutorials/setup_leakcheck.html
Currently, we are allocating memory for the data array in ArrayIntVector
's constructor. However we never actually deallocate the data array at the end of the object's lifetime. To fix this, you should implement a destructor to clean up its members, since this is automatically called when the object is destroyed.
Now recompile your code and run Valgrind again to confirm the memory leaks are gone.
Submit
Submit the files to the autograder.