For this assignment you will be writing a Map that is based on a hash table. This one will exist in memory. Basically, I am asking you to write the equivalent of the C++ unordered_map type. (http://www.cplusplus.com/reference/unordered_map/unordered_map/) I'm not going to ask you to have yours include every method that the standard library contains though, only the main ones.
The code you submit will be in a file called HashMap.h and your class will be HashMap with two template arguments for key and value and a third for the hash function. (Note that the one in the STL has two additional template parameters, one for an equality function and another for an allocator. We will assume that all the types you work with have an appropriate operator== and that you can use the normal heap with new and delete for memory allocation.)
template<typename K,typename V,typename Hash>
class HashMap {
Hash hashFunction;
// Data to store the hash table and the number of elements.
public:
typedef K key_type;
typedef V mapped_type;
typedef std::pair<K,V> value_type;
class const_iterator;
class iterator {
// NOTE: These might be different depending on how you store your table.
decltype(table.begin()) mainIter;
decltype(table.begin()) mainEnd;
decltype(table[0].begin()) subIter;
public:
friend class const_iterator;
// NOTE: These might be different depending on how you store your table.
iterator(const decltype(mainIter) mi,const decltype(mainEnd) me):mainIter(mi),mainEnd(me) {
if(mainIter!=mainEnd) subIter = mainIter->begin();
while(mainIter!=mainEnd && subIter == mainIter->end()) {
++mainIter;
if(mainIter!=mainEnd) subIter = mainIter->begin();
}
}
// NOTE: These might be different depending on how you store your table.
iterator(const decltype(mainIter) mi,
const decltype(mainEnd) me,
const decltype(subIter) si):
mainIter(mi),mainEnd(me),subIter(si) {}
bool operator==(const iterator &i) const { return mainIter==i.mainIter && (mainIter==mainEnd || subIter==i.subIter); }
bool operator!=(const iterator &i) const { return !(*this==i); }
std::pair<K,V> &operator*() { return *subIter; }
iterator &operator++() {
++subIter;
while(mainIter!=mainEnd && subIter==mainIter->end()) {
++mainIter;
if(mainIter!=mainEnd) subIter = mainIter->begin();
}
return *this;
}
iterator operator++(int) {
iterator tmp(*this);
++(*this);
return tmp;
}
};
class const_iterator {
// NOTE: These might be different depending on how you store your table.
decltype(table.cbegin()) mainIter;
decltype(table.cbegin()) mainEnd;
decltype(table[0].cbegin()) subIter;
public:
// NOTE: These might be different depending on how you store your table.
const_iterator(const decltype(table.cbegin()) mi,const decltype(table.cbegin()) me):mainIter(mi),mainEnd(me) {
if(mainIter!=mainEnd) subIter = mainIter->begin();
while(mainIter!=mainEnd && subIter == mainIter->end()) {
++mainIter;
if(mainIter!=mainEnd) subIter = mainIter->begin();
}
}
// NOTE: These might be different depending on how you store your table.
const_iterator(const decltype(table.begin()) mi,
const decltype(table.begin()) me,
const decltype(table[0].begin()) si):
mainIter(mi),mainEnd(me),subIter(si) {}
// NOTE: These might be different depending on how you store your table.
const_iterator(const iterator &i):mainIter(i.mainIter),mainEnd(i.mainEnd),subIter(i.subIter) {
}
bool operator==(const const_iterator &i) const { return mainIter==i.mainIter && (mainIter==mainEnd || subIter==i.subIter); }
bool operator!=(const const_iterator &i) const { return !(*this==i); }
const std::pair<K,V> &operator*() const { return *subIter; }
const_iterator &operator++() {
++subIter;
while(mainIter!=mainEnd && subIter==mainIter->end()) {
++mainIter;
if(mainIter!=mainEnd) subIter = mainIter->begin();
}
return *this;
}
const_iterator operator++(int) {
const_iterator tmp(*this);
++(*this);
return tmp;
}
};
HashMap(const Hash &hf);
HashMap(const HashMap<K,V,Hash> &that); // Only if needed.
HashMap &operator=(const HashMap<K,V,Hash> &that); // Only if needed.
bool empty() const;
unsigned int size() const;
iterator find(const key_type& k);
const_iterator find(const key_type& k) const;
int count(const key_type& k) const;
std::pair<iterator,bool> insert(const value_type& val);
template <class InputIterator>
void insert(InputIterator first, InputIterator last) {
// TODO: Put this one here to simplify the templates
}
iterator erase(const_iterator position);
int erase(const key_type& k);
void clear();
mapped_type &operator[](const K &key);
bool operator==(const HashMap<K,V,Hash>& rhs) const;
bool operator!=(const HashMap<K,V,Hash>& rhs) const;
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
const_iterator cbegin() const;
const_iterator cend() const;
private:
void growTableAndRehash();
};