Assignment due on Paperless on Friday, Dec. 8th at 11:59 PM (FIRM DEADLINE)
According to veteran C++ programmers, there are two projects which bring together all the knowledge that a proficient C++ programmer should have:
In this assignment, we will be putting #1 on your resume by completing a STL-compliant HashMap.
Recall that the Map
abstract data type stores key → value pairs, and provides efficient lookup of the value of any key.
There are two versions of this in the STL: std::map
, traditionally implemented using a balanced binary search tree, and std::unordered_map
(introduced in C++11), which uses a clever technique called hashing and supports the most map operations in constant time (!).
A hashmap is a bit of a complicated data structure, but we've given you nearly all of the implementation of it. In brief, this is how it works:
_buckets_array
in our HashMap) of "buckets".
node
s, which are defined in hashmap.h
.
node
in these linked lists contains one key-value pair that is contained in our map. In the node
struct, this is the field
value
, of type value_type
. value_type
is a type-alias for a std::pair<K, M>
. Check out its definition
near the top of the .h file!
_hash_function
. For our purposes, this will always be the default
hash function in the STL. Then, the HashMap class mods that integer by the number of buckets in _buckets_array
. This is the index
at which HashMap will insert or look for the key. From here, its just a matter of traversing the linked list stored at that index to find the key in question
(it is possible that multiple keys are stored in the same index because their hashes, or the mod of their hashes, are the same!)
You will not necessarily write a lot of code on this assignment (~20 lines), but some of your time will be spent on understanding the starter code given to you, and reasoning about design choices and common C++ idioms. You may optionally work with a partner. We recommend having a partner to discuss the design questions. If you choose to work with a partner, we ask that you and your partner submit a single version of the assignment among both of you. This means that you will ideally be working with your partner on a shared version of the code and short answer questions. Feel free to start a shared Google Doc, a private GitHub repository, or anything else that you'd need to keep track of a shared version of the code. You may also choose to schedule video chat sessions with each other to work on the assignment.
scp
your Assignment 3 starter code to your 106L folder in myth.
scp LOCAL_PATH <yoursunetid>@myth.stanford.edu:MYTH_PATH
Downloads/HashMap_Starter.zip
.ssh
ing into Myth using ssh <yoursunetid>@myth.stanford.edu
, 2) entering
your password and then 3) cd
ing to your CS106L directory and finally 4) printing out the path to this folder using pwd
.
unzip HashMap_Starter.zip
.
Feel free to email the lecturers if you are having trouble with setup!
Please download the starter code here. The starter code contains the following files:
hashmap.h
:
This file contains the (incomplete) class function prototypes for the HashMap, and also contains thorough comments about each function.
You will need to modify many of these function prototypes for milestone 1, and add a few for milestone 2
Like in CS 106B, you may add any private helper functions (though it is unlikely you will need to), but do not add or change the prototypes of any public functions.
Imagine what a disaster it would be for the world if the vector’s size function was renamed to length or if the erase function had a few extra parameters...a good chunk of the world’s C++ code would stop compiling!
hashmap.cpp
:
This file contains the implementation of the HashMap, and also contains thorough comments about implementation details.
Besides changing function signatures for milestone 1, you will have to add the implementations for milestone 2 to this file.
hashmap_iterator.h
This file contains the complete class declaration and implementation for a HashMapIterator, and also contains thorough comments about each function.
You will be reading the code here for milestone 1, but you will not need to modify this file at all.
We have never used a class as our iterator type before, make sure you read through these files and try to understand what is going on!
Importantly, check out the difference between the iterator
and const_iterator
aliases in hashmap.h
short_answer.txt
: You will write your solutions to the short answer questions in this file.build.sh
: This file contains the compilation instructions for the project. To check if your Hashmap compiles, run ./build.sh
from your assignment 4 directory.
main.sh
: This file contains example code using your The hashmap. To run this code, first build it and then run ./main
tests.cpp
and test_settings.cpp
: These files contain crazy amounts of code meant to test your hashmap! You shouldn't need to edit them!
You compile and run this code the same way you would lecture code! In the terminal from your HashMap_Starter
directory, run ./build.sh
to compile and ./main
to run your code!
Make sure the lines marked "UNCOMMENT FOR MILESTONE 2" are commented out for now. You will get tons of compiler errors!
Before changing any functions, your code should compile. After chaning the functions in main, don't freak out about the loads of compile errors! Just keep looking for functions in HashMap to mark const until you get to a reasonable point in the compile mesagqes, and then try to use those to find more functions that need a const or an overload!
Make sure you change your function signatures in two places: the .h and the .cpp
The functions in main are declared before theyre implemented, so any signatures you change there should also change where they are first defined as well!
Its easy to make a lot of copy-paste errors here. Remember when you are overloading, you are also changing the return type.
Notice how begin()
is overloaded with a const version! Even though only the return type is changed, this type of overloading is ok because the function is marked const
, which means the compiler can figure out which version of begin()
to use based on whether the HashMap its been called on is const or not!
Your first task will be to make a const-interface for the HashMap class. Recall that we often mark variables,
especially function parameters const
to avoid a specific kind of bug: modifying a piece of data when we weren't supposed to.
We highly recommend checking out the end of the Template Classes and Const-Correctness lecture before starting!
We have already marked a couple member functions const for you (check out the const overload of begin()
, it is up to you to find the rest!
Here is what you need to do to complete this milestone:
main.cpp
and pay special attention to all the helper functions called by student_main()
. None of them have bugs,
but some of them don't properly mark their parameters const
when necessary. Mark the appropriate parameters const
.
Now, if you try to build, you will notice your code doesn't compile! Thats because most of your HashMap functions are not marked const
.
hashmap.cpp
and hashmap.h
files. Go ahead and mark any existing functions const
, as long as
this is appropriate. This is step 1 for creating your const-interface! Remember, any signatures you change hashmap.h
, you also need to
change in hashmap.cpp
.
const
version) to make your const-interface robust. Recall that iterators by default allow us to dereference and change
their underlying value, but sometimes we just want to use an iterator to, well, iterate, without changing any values. Make use of the const_iterator
alias we provided you in hashmap.h
to create const versions of the appropriate functions.
begin()
. Use the static_cast/const_cast
trick demonstrated there in the rest of your functions!
const_iterator
when necessary?
const
in main.cpp
, any call to a non-const function will error,
you can use this as a guide for which functions you might want to overload! There is one function that does not return an iterator that still must be overloaded, can you find it?
Please answer these questions in short_answer.txt
at()
and the implementation of the operator []
. Wy did you have to overload one and not the other?
HashMap::find
member function, there is also a std::find
function in the STL algorithms library. If you were searching for key k in HashMap m, is it preferable to call m.find(k)
or std::find(m.begin(), m.end(), k)
?
Any good STL-compliant class must have correct special member functions.. Recall that there are six major special member functions:
The first two are implemented for you; your job is to implement the last four.
Specifically, the copy operations should create an identical copy of the provided HashMap, while the move operations should move the contents of the provided HashMap to this
(the instance of the HashMap upon which the move operation is called). Avoid memory leaks and perform your copy/move as efficiently and safely as possible.
Check out the Special Member Functions lecture and the Move Semantics lecture!
Try to use the member initializer list (colon after constructor) whenever possible for efficiency!
We do not provide the headers, so you will have to add them to the .h file yourself.
Read over the .h file again and make sure you understand each private member variable! You will need to fill these in your SMFs!
We have given you helpers which cover the vast majority of the actual nitty gritty of filling a copied/moved hashmap. Pay special attention to insert()
and clear()
!
Hints
clear()
and insert()
change the _size
member variable, so keep that in mind when changing _size yourself.
If you see that size is twice what you expect it to be, then you are probably incrementing _size twice - once in insert(), and once in your code.clear()
and insert()
:)
You can run the Milestone 2 tests by uncommenting the lines marked "UNCOMMENT FOR MILESTONE 2" and then selecting option 2 when you run your code. Remember to ./build.sh
first!
You don't need to look at them, and the testing file actually contains more tests than we run, but Test 4A, 4B, and 4C create copies of your HashMap using the copy constructor and copy assignment operator, and verifies their correctness. In addition, there are tests for edge cases such as self-assignment. Tests 4D, 4E, and 4F try to move HashMaps from one to another using the move constructor and move assignment, and verifies correctness just like test 4A.
Note that the move operations and time tests may pass even if you haven't implemented the move operations (recall that if no copy/move operations are declared, the compiler generates default ones, which will pass the move but not copy tests). See the test_settings.cpp for more information. The tests use some compiler directives (#pragma) to silence compiler warnings about self-assignment. You can safely ignore those.
Test 4G and Test 4H time your move operations to verify that you are actually moving the contents of the HashMaps rather than copying the contents. The tests try the move operations on HashMaps of different sizes, and verify that the runtime of the move operations is O(1), not O(n). You can see the results of the time test printed in the test harness.
Please answer these questions in short_answer.txt
Please submit hashmap.h
, hashmap.cpp
and short_answer.txt
to Paperless!