In this lab, we will modify
IntVector from the previous lab by using dynamically allocated arrays to support storage of arbitrarily many elements. Additionally, we’ve prepared an Exam Prep that reviews similar topics.
You may work alone or with a partner. Please see the syllabus for partnership rules.
Submit the code files below on the autograder. We encourage you to complete the lab worksheet, but it is not turned in for credit.
To pass this lab, you must finish tasks 1 and 2.
(Task 1) Implement
grow and call it in
(Task 2) Implement the
We have provided starter files for this lab. Use the following commands in a terminal at your working directory to download the files.
$ wget eecs280staff.github.io/lab/lab07/starter-files.tar.gz $ tar -xvzf starter-files.tar.gz
Here’s a summary of this lab’s files. You will turn in the bolded ones.
||Contains the interface of
||Contains implementations for
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 “work” out of the box, 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++11 ArrayIntVector.cpp lab07.cpp -o lab07.exe $ ./lab07.exe
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:
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.
IntVector cannot store more elements than the space it has in its member array, so we cannot create
IntVectors 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:
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 own
elts_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 an
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
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
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.
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:
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 the required files to the autograder.