CSE 333 Exercise 9
Due: Wednesday, November 18 by 11 AM
Rating: 3 (note)
Each exercise this quarter is rated on a integer scale of 1 – 5, inclusive, with 1 being the "least time-consuming" and 5 being the "most time-consuming".
This difficulty scale is meant as a rough guide for you in predicting the amount of time to set aside for each exercise as you balance the work required for 333 with your other obligations. However, it is necessarily imperfect as everyone's set of circumstances and experiences with the exercises differ. If your experience with an exercise does not align with its rating, that is not a reflection of you or your abilities.
Goals
- Define a class that inherits from and implements an abstract class.
- Evaluate a situation to figure out what smart pointers to use.
- Utilize smart pointers to manage complex memory structures.
Problem Description
In this exercise, you will create a simplified C++ linked list class which can only store integers. Note the major differences between this and the C-style linked list module from Homework 1:
LinkedListwas a public-facingtypedef-ed struct with the implementation hidden in LinkedList_priv.h. Now it is a class with private data members fornum_elements,head, andtail.LinkedListNodewas defined in LinkedList_priv.h but is now a private data member of the class.LinkedListfunctions took pointers toLinkedListstructs as parameters but now these functions are public class members.LinkedList_Allocateis handled by the class constructor(s) andLinkedList_Freeis handled by the class destructor.LinkedListmemory was manually managed by you as the programmer but now will be managed via smart pointers.
Provided Files
We have provided you with the following five source files, which can be obtained by pulling from your GitLab repo.
IntList.h— Defines an abstract classIntList, which can store integers. Integers can be added to or removed from either the front or the end of the list. Users can also get the size of the list. Note that since this is an abstract class, you cannot construct an instance ofIntList(i.e.,IntList list();would not compile).test_list.cc— Tests your implementation of the LinkedIntList files described below. Note that these tests are not exhaustive, and you may want to more thoroughly check your solution.Makefile— Provided for your convenience in compiling the executable.LinkedIntList.h— Contains the class definition ofLinkedIntListthat you will need to complete.LinkedIntList.cc— Contains member function definitions ofLinkedIntListthat you will need to complete.
LinkedIntList.h and
LinkedIntList.cc so you should not modify the other
source files.
Do feel free to modify the test files, though, or create your own.
Requirements
LinkedIntListshould derive fromIntListand have implementations of all the pure virtual functions declared inIntList.LinkedIntListshould have an empty destructor since smart pointers should be used to clean everything up.LinkedIntListshould have a default (0-argument) constructor.- You should explicitly disable (
= delete) the copy constructor and assignment operator forLinkedIntList.
LinkedIntList using normal ("raw") pointers,
i.e., no smart pointers.
Your code should still pass the provided test file, but will leak
memory.
Afterwards, you should edit your implementation to use smart
pointers and make sure no memory errors are generated.
Implementation Notes
Linked List
When implementing a linked list, consider the following cases:
- Insertion: (1) empty list, (2) one or more elements.
- Deletion: (1) empty list, (2) one element, (3) more than one element.
Smart Pointers
This exercise makes use of smart pointers to manage memory; as a
result, you are forbidden from using delete in
LinkedIntList (other than for disabling the cctor and
op=).
Be sure to use the most appropriate smart pointer type(s).
Refer to lecture slides and C++ documentation (e.g., the
memory header)
for details on how to use smart pointers and their methods.
Abstract Classes
We have provided the abstract class IntList.
An abstract class is one that has at least one pure virtual
function.
Your LinkedIntList should inherit from
IntList, but should not be an abstract class itself.
To avoid this, you should make sure that LinkedIntList
has no pure virtual functions.
Test Suite
We have provided a test suite executable in your GitLab repo that can help you check just the output correctness of your code (i.e., it does not check style or memory). This test suite is purposely opaque and will not reveal what is failing. You should aim to see the following output:
$ ./test_ex9 Test cases purposely not revealed. 0 failed
Style Focus
Classes
This is yet another exercise with C++ classes so you should be sure to follow the best standards with commenting and organizing your classes as laid out in the lecture and the ex6 and ex7 sample solutions.
Const
Functions, parameters, and variables should be labeled with
const, where appropriate, throughout your program.
Documentation
Make sure that you have descriptive comments with function and class declarations.
Submission
Submit the following file(s) by creating an ex9-submit tag in your repo before the assignment deadline. The file(s) should be located in the exact directory listed below, including capitalization:
ex9/LinkedIntList.hex9/LinkedIntList.cc
Other files in the ex9/ directory will be ignored, so
you may keep the files unnecessary for submission in there!
For full credit, your code must:
- Compile without errors or warnings on CSE Linux machines
(lab workstations,
attu, or CSE home VM). - Have no runtime errors, memory leaks, or memory errors
(
g++andvalgrind). - Be contained in the files listed above and compile with the provided Makefile.
- Have a comment at the top of your
.ccand.hfiles with your name(s) and CSE or UW email address(es). - Be pretty: the formatting, modularization, variable and
function names, commenting, and so on should be consistent with
class style guidelines.
Additionally, the linter shouldn't have any complaints about your
code (
cpplint.py). - Be robust: your code should deal with hard-to-handle/edge cases and bogus user input (if there are any) gracefully.