EECS 280 Lab 06: Container ADTs
Lab Due Sunday, Oct 25, 2020, 8:00 pm
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
To pass this lab, you must finish task 1. Tasks 2 and 3 are optional.
- (Task 1) Implement the public functions for
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!
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.
||Contains the declaration and interface of
||Contains implementations for
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
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:
IntVectorstores its elements in a private member array called
IntVectorhas a fixed maximum size stored in the
IntVectorkeeps track of its current size in the private member
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:
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
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.
assert statements to check the REQUIRES clause for the following
For example, in
push_back we would
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
member variable satisfies the constraints:
0 <= num_elts and num_elts <= CAPACITY
IntVector instance could exist with some nonsense
num_elts value like
-2. There’s no restriction in
prevents this, so we must manually enforce a representation invariant
to limit the data members to take on values that make a sensible
For this task, define a private member function,
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
to be violated.
Submit the required files to the autograder.