Phase 3: Constructor, Destructor, swap(), size(), and buckets()
Now you'll start implementing your HashSet. As usual, you'll probably want to have the
close to hand while you work.
As usual, for each piece that you implement, you will use these four steps:
-
Plan: By drawing pictures and making notes, you will sketch out what you want to do. Your notes/picture should take into account any edge cases that you will need to consider. You will submit your planning to us by uploading a picture, which we’ll check for completeness. We will not grade the correctness of your planning, and you should complete this step in the way that is most beneficial to you for understanding what you’re being asked to implement.
-
Write Tests: After you plan, but before you start writing any implementation code, you will add tests to your
hashset-test.cppfile. Your tests should be designed to confirm that working implementations are correct, and also to identify problems with broken implementations. You should specifically test any edge cases that you identified in planning. We will run your tests against working and broken implementations ofHashSet, and you will be graded both for completeness (your coverage of cases) and for correctness (do your tests check the things that they say they’re checking?) -
Implement: Once you’re satisfied with your planning and test writing, you will implement the function(s) for the step you’re on. Like all coding parts in CS 70, we will grade your implementation for completeness, correctness, style, elegance, and clarity.
-
Test & Fix: After your implementation is written, you should run your tests and ensure that your implementation passes them. If your implementation doesn’t pass your tests, you should ask yourself whether the problem is with your test (e.g., are you testing for something that should be undefined behavior?) or with your implementation (i.e., is your
HashSetnot doing what it’s supposed to be doing)? Fixing the problem may require changes to your planning, your tests, and/or your implementation. You don’t need to upload revised versions of your planning document, but you should correct your tests and implementation as needed.
Be sure to read the Helpful Hints on each step as well.
Let's Go!
Before you get started on actually doing these things, read over the Helpful Hints below!
For this part, you will plan, write tests for, implement, and debug
- The parameterized constructor
- The destructor
- The
swap()member function - The
size()member function - The
buckets()member function
Planning
Within the HashSet directory, create a directory called Planning, and add your planning image, named Phase_3.jpg, to that directory.
(Double check your image within your repository. If it didn't upload correctly, you can upload it directly using GitHub's web interface.)
Hints
How to Keep the Constructor Simple
Some data members need to be initialized in the member-initialization list, but some (ones that are always set to zero, etc.) can have their values specified when you declare them in the class definition.
You don't need to do anything special to initialize or destroy a std::forward_list. Instances are already well-behaved objects, defaulting to an empty list and having their own destructor. They are much easier to work with than explicitly managing Nodes like you did in both the IntList and tree-based assignments.
So there are no
Nodes to worry about, right?
Right.
-
Phew!
Explicit Instantiation
Template instantiation is lazy, with the compiler only stamping out the versions of the code it actually needs. Often this approach is useful, but if you forget to test one of your functions, this feature can allow glaring errors to exist in your code, unnoticed, because the compiler is not even trying to compile that function.
Explicit instantiation forces the compiler to produce instances of all the member functions of a class in one go, which helps to confirm that all of those the member functions can be compiled. The provided test program, hashset-cow-test.cpp, includes an explicit instantiation that looks like
template class HashSet<Cow>; // explicit instantiation of entire templated class
Writing swap()
You wrote a swap() function for your IntList class in Homework 5. Basically, you just need to go through and call std::swap on all the data members.
-
But remember, whenever you add a new data member, you need to add it to your swap function, otherwise you'll have two very muddled-up objects, which can be a very confusing bug!
Representing the Buckets
We are encoding our hash table as an array of std::forward_list<T> objects. You've worked with arrays of objects before!
If you are uncertain about how to handle allocation, initialization, destruction, and deallocation for this array, consider going back to your dynamic train code in Homework 4, where you had an array of Car objects. This array is very similar.
Testing Reminders
Because we only use the public interface for testing, you can't really test an operation all by itself. You can test the relationships between operations, especially where one operation makes some changes and another operation lets you observe something about the data structure after the change.
Generally speaking, you should write your tests in order of increasing complexity and increasing dependency on various operations. In this part of the assignment you are implementing some very basic operations, and so you can only write very basic tests. Some of these operations might have relationships to other operations that you will implement later—you can test those relationships then!
Remember that we never call a class’s destructor directly, so you shouldn’t write explicit tests for it. But you should use valgrind here (and on every step from here on out!) to make sure that memory is being managed correctly.
Recall the Format of Your Tests
You should probably look back at your test programs from previous projects to make sure you use the testing logger correctly.
(When logged in, completion status appears here.)