lab

EECS 280 Lab 7: Dynamic Memory

Lab Due Sunday, November 1, 2020, 8:00 pm

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 Exam Prep, but it is not turned in for credit.

Files to submit

Completion Criteria/Checklist:

To pass this lab, you must finish tasks 1 and 2.

Lab Exercises

The Files

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.

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++11 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:

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:

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/p1-stats/setup_valgrind.html#checking-for-memory-leaks

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 required files to the autograder.