Phase 2: HashMultiset<T> Interface and Stubs
HashMultiset<T> Class Interface
Here is the specification for the HashMultiset<T> class you will be implementing:
As usual, we encourage you to have the specifications open in a separate browser window or tab for reference while you code.
An Aside Regarding the Private Encoding
I read the specifications and I'm confused about this whole
KeyValuestruct thing. I don't remember seeing anything like that in the lessons!
In the lessons, we mostly focused on how hash tables can be used to implement a set (which we'd previously also used BSTs for), which just stores keys. By contrast, HashMultiset<T> is a map (also known as an associative data structure), because it maps (or associates) each key to a value, just like a Python dict does. These might seem like completely different things, but remember that in the Week 9 Lessons we explained that sets and maps are closely related. Specifically, we said the following:
We'll focus on sets, but in fact everything we do for sets can be easily modified to solve the map problem instead. (In many ways, a map is just like a set where we're storing key/value pairs in the set.)
That's exactly what we'll do in this homework!
So, where the lessons showed hash tables with the keys directly stored in the buckets, like so...
| bucket | keys | |||||||
|---|---|---|---|---|---|---|---|---|
| 1 | → | juice |
→ | pancakes |
||||
| 2 | ||||||||
| 3 | → | coffee |
→ | milk |
→ | cheese |
||
| 4 | → | sausage |
||||||
| ... |
...the hash table you'll be implementing instead stores key-value pairs in the buckets (actually, key-count pairs since we're constraining the mapped value type to be integer counts), like so:
| bucket | (key,count)s | |||||||
|---|---|---|---|---|---|---|---|---|
| 1 | → | (juice,4) |
→ | (pancakes,2) |
||||
| 2 | ||||||||
| 3 | → | (coffee,1) |
→ | (milk,12) |
→ | (cheese,9) |
||
| 4 | → | (sausage,1) |
||||||
| ... |
The important thing to keep in mind is that these key-count pairs are part of the private encoding. The outside user doesn't know about their existence, just like they didn't know about Nodes in your TreeSet<T>! From the user perspective, they only ever work with keys; that is, the user would call insert("milk"), NOT insert(("milk", 12)). It is the HashMultiset<T>'s job to internally maintain the key-count pairs and ensure that the counts get updated when insert is called multiple times with the same key.
This was a long-winded way to answer Duck's question:
KeyCountis just the name of the struct we use to represent key-count pairs.
You could have also used C++'s
std::pairclass for this purpose.-
True. But that class offers a bit more functionality than we need, and making our own struct allows us to give meaningful names like
keyandcountto the items in the pair.
Let's Go!
To be able to test your code before you have everything written, it's helpful to have made stubs. We'll implement these stubs over the remaining phases.
In hashmultiset.hpp, write…
Do we have to do this again? Sure, I can make a bunch of stubs, and it's good that I know how. But I'm not really learning anything new by doing it over and over again.
-
But what about the joy of starting from a blank slate?
-
Meh. Happier to not have makework.
-
Okay.
We've made stubs for all the functions in the HashMultiset interface, and provided declarations in the header.
Run make
Just to feel like you've done something in this part, run make. Everything should build without warnings, but (obviously) nothing will actually work yet.
(When logged in, completion status appears here.)