lab

EECS 280 Lab 7: Dynamic Memory

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

Direct autograder link

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

• ArrayIntVector.cpp

Completion Criteria/Checklist:

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

• (Task 1) Implement grow and call it in push_back.

• (Task 2) Implement the ArrayIntVector destructor.

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.

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:

• 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 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:

• 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 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 ArrayIntVector 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/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.