这个作业是用C++完成一个抽象数据结构的map集合
CS515
The library generic hash function std::hash<T>is used to calculate the hash value for our KEY
type keys. The template header:
template <typename KEY, typename T, typename H = std::hash<KEY>>
indicates there are three type parameters: the key type KEY, the value type T and the function
object type H, which is used to hold the hash function and is assigned a default value, the
std::hash<T> function. To calculate the hash value, simply use
std::size_t key = H()(newkey);
and then mod the value key by the table size.
•
•
The hash table will be rehashed dynamically when the load factor reaches 2. This means that the
underlying hash table doubles the size (approximately since we want to keep the table size prime),
and all entries be re-inserted into the table. The hash table does not shrink dynamically when the
entry size reduces.
A public method named tsize()is required so that we can verify your rehash implementation.
Submission:
•
•
Submit unorderedmap.hand unorderedmap.cpp.
You should also fill out the README file and submit it as well. Submit the following files to the
appropriate assignment on Mimir:
unorderedmap.h unorderedmap.cpp README
•
Do not turn in executables or object code. Programs that produce compile time errors or
warnings will receive a zero mark (even if it might work perfectly on your home computer).
1
•
Be sure to provide comments in your program. You must include the information as the section
of comments below:
/**
CS515 Assignment 10
File: XXX.cpp
Name: XXX
Section: X
Date: XXX
Collaboration Declaration: assistance received from TA, PAC etc.
*/
Some notes on grading:
–
–
–
Programs are graded for correctness (output results and code details), following directions
and using specified features, documentation and style.
To successfully pass the provided sample tests is not an indication of a potential good grade; to
fail one or more of these tests is an indication of a potential bad grade.
You must test thoroughly your program with your own test data/cases to ensure all the
requirements are fulfilled. We will use additional test data/cases other than the sample tests
to grade your program.
–
Here is a tentative grading scheme.
directions
100
10
5
10
5
8
5
8
8
5
8
10
4
10
4
Unordered Map run 1 (Insert)
Unordered Map run 1 valgrind
Unordered Map run 2 (operator[])
Unordered Map run 2 valgrind
Unordered Map run 3 (find)
Unordered Map run 3 valgrind
Unordered Map run 4 (find)
Unordered Map run 5 (erase)
Unordered Map run 5 valgrind
Unordered Map run 6 (erase)
Unordered Map run 7 (iterator++)
Unordered Map run 7 valgrind
Unordered Map run 8 (rehash)
Unordered Map run 8 valgrind
