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.

  • Implement grow and call it in push_back.

  • Implement the ArrayIntVector destructor.

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

Lab 7

Not Claimed
Status
Finished
Problems
1
Open Since
2024-06-14 00:00
DDL
2024-06-18 23:59
Extension
72.0 hour(s)