lab

EECS 280 Lab 06: Container ADTs

Lab Due Sunday, Oct 25, 2020, 8:00 pm

Direct autograder link

In this lab, we will practice creating and using container abstract data types. A container is an object that can store a collection of elements. In this example, we will focus on IntVector, a container that holds integer values and allows random access to any element. The container internally manages the storage space for its elements using an array and provides a public interface for accessing and updating them. Additionally, we’ve prepared an Exam Prep that reviews similar topics. Finally, we’ve included some optional exam-style practice problems to study for the exam.

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

• IntVector.cpp

Completion Criteria/Checklist:

To pass this lab, you must finish task 1. Tasks 2 and 3 are optional.

• (Task 1) Implement the public functions for IntVector in the IntVector.cpp file.

Note: Tasks 2 and 3 are HIGHLY recommended! In past terms, the majority of the bugs in student submissions for Project 4 could be caught using the techniques in these tasks!

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/lab06/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 lab06.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 IntVector.cpp lab06.cpp -o lab06.exe
$ ./lab06.exe

Introduction

The IntVector class is declared in IntVector.h. Take a moment to familiarize yourself with the general structure of the class and the interface it provides. Note that:

• An IntVector stores its elements in a private member array called data.
• An IntVector has a fixed maximum size stored in the CAPACITY member variable.
• An IntVector keeps track of its current size in the private member num_elts.

Task 1 - Basic IntVector

Your first task is to write the basic member functions needed for the IntVector class. Stubs for these functions are found in IntVector.cpp. Replace these with your code.

The functions to implement for this task are:

• IntVector::push_back
• IntVector::pop_back
• IntVector::at
• IntVector::operator[]
• IntVector::size
• IntVector::empty
• IntVector::full
• operator<<

As you complete each function, run the provided testing code to check that your implementation is correct. If you are having difficulty implementing some of them, you may find it useful to add the assert statements from tasks 2 and 3 to help you debug.

Task 2 - Use asserts to Check REQUIRES Clauses (Optional)

RMEs have been provided for each of IntVector’s functions. We know that we are allowed to assume the conditions of the REQUIRES clause are satisfied when writing code for each function. However, it can be very useful for debugging purposes to go ahead and explicitly use assert to check each of them. This way, if we accidentally call a function without ensuring that its REQUIRES clause is satisfied, we’ll get a clean error message rather than undefined behavior that may be hard to detect or diagnose. It is also possible to turn off all asserts when compiling for release rather than debugging, so we can use assertions generously without worrying about a performance penalty.

Add assert statements to check the REQUIRES clause for the following functions:

• IntVector::push_back
• IntVector::pop_back
• IntVector::at
• IntVector::operator[]

For example, in push_back we would assert(!full()); at the start of the function.

Task 3 - Use assert to Check Representation Invariants (Optional)

A representation invariant is a constraint on the internal state of an object that should hold immediately after object construction and should be maintained throughout the lifetime of the object, except (possibly) during the execution of a member function. Essentially, representation invariants express what is needed for an instance of an ADT to make sense.

In the case of an IntVector, an invariant we must enforce is that the number of elements must be nonnegative and no greater than the maximum capacity. More precisely, we must ensure that the num_elts member variable satisfies the constraints:

0 <= num_elts and num_elts <= CAPACITY

Technically, an IntVector instance could exist with some nonsense num_elts value like -2. There’s no restriction in C++ that prevents this, so we must manually enforce a representation invariant to limit the data members to take on values that make a sensible object.

For this task, define a private member function, check_invariants, that returns a boolean value to indicate whether the representation invariants hold for the object it is called on. Then, at the beginning and end of every member function, add assert(check_invariants()). Now, you will get an error message (i.e. failed assertion) if some part of your code has a bug that causes the representation invariants of an IntVector to be violated.

Submit

Submit the required files to the autograder.