Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <list>
- #include <cassert>
- #include <stdexcept>
- template<typename K,typename V,typename Hash>
- class HashMap {
- Hash hashFunction;
- // TO DO: data to store the hash table, the number of elements and the max_load_factor.
- std::vector<std::list<std::pair<K,V>>> hashTable;
- int initSize = 10;
- int currentSize = 0;
- double maxLoadFactor = 0.75;
- // Suggestion for the hash table: either
- // vector<vector<pair<K,V>>> table;
- // or
- // vector<list<pair<K,V>>> table;
- // would work well for the chaining approach.
- 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.
- typename std::remove_reference<decltype(hashTable.begin())>::type mainIter;
- typename std::remove_reference<decltype(hashTable.begin())>::type mainEnd;
- typename std::remove_reference<decltype(hashTable[0].begin())>::type subIter;
- public:
- friend class const_iterator;
- friend class HashMap;
- // NOTE: These might be different depending on how you store your hashTable..
- 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 hashTable..
- 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 hashTable..
- typename std::remove_reference<decltype(hashTable.cbegin())>::type mainIter;
- typename std::remove_reference<decltype(hashTable.cbegin())>::type mainEnd;
- typename std::remove_reference<decltype(hashTable[0].cbegin())>::type subIter;
- public:
- // NOTE: These might be different depending on how you store your table.
- const_iterator(const decltype(hashTable.cbegin()) mi,const decltype(hashTable.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(hashTable.cbegin()) mi,
- const decltype(hashTable.cbegin()) me,
- const decltype(hashTable[0].cbegin()) si):
- mainIter(mi),mainEnd(me),subIter(si) {}
- const_iterator(const decltype(hashTable.begin()) mi,
- const decltype(hashTable.begin()) me,
- const decltype(hashTable[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;
- }
- };
- // TO DO
- HashMap(const Hash &hf) {
- hashFunction = hf;
- for(int i = 0; i < initSize; i++) {
- hashTable.insert(new std::list<std::pair<key_type, mapped_type>> {});
- }
- }
- // HashMap(const HashMap<K,V,Hash> &that); // Only if needed.
- // HashMap &operator=(const HashMap<K,V,Hash> &that); // Only if needed.
- bool empty() const { return currentSize == 0; }
- bool satisfiesLoadingFactor() {
- return (currentSize / initSize) < maxLoadFactor;
- }
- unsigned int size() const {
- return currentSize;
- }
- iterator find(const key_type& k) {
- for(int i = 0; i < hashTable.size(); i++) {
- std::list<std::pair<key_type, mapped_type>>::iterator currIt = hashTable[i].begin();
- std::list<std::pair<key_type, mapped_type>>::iterator end = hashTable[i].end();
- while(currIt != end) {
- std::list<std::pair<key_type, mapped_type>> bucket = (*currIt);
- if((bucket->first) == k) {
- return currIt;
- }else{
- currIt++;
- }
- }
- }
- }
- const_iterator find(const key_type& k) const {
- for(int i = 0; i < hashTable.size(); i++) {
- std::list<std::pair<key_type, mapped_type>>::iterator currIt = hashTable[i].begin();
- std::list<std::pair<key_type, mapped_type>>::iterator end = hashTable[i].end();
- while(currIt != end) {
- std::list<std::pair<key_type, mapped_type>> bucket = (*currIt);
- if((bucket->first) == k) {
- return new const_iterator(currIt.begin(), currIt.end());
- }else{
- currIt++;
- }
- }
- }
- }
- int count(const key_type& k) const {
- int count = 0;
- for(int i = 0; i < hashTable.size(); i++) {
- std::list<std::pair<key_type, mapped_type>>::iterator currIt = hashTable[i].begin();
- std::list<std::pair<key_type, mapped_type>>::iterator end = hashTable[i].end();
- while(currIt != end) {
- list<pair<key_type, mapped_type>> bucket = (*currIt);
- if((bucket->first) == k) {
- return bucket.size();
- }else{
- currIt++;
- }
- }
- }
- return count;
- }
- std::pair<iterator,bool> insert(const value_type& val) {
- if(!satisfiesLoadingFactor()) {
- growTableAndRehash();
- }
- int hashedNum = hashFunction(val);
- while(!hashTable[hashedNum].empty()) {
- hashedNum = hashFunction(val);
- }
- std::list<std::pair<key_type, mapped_type>> bucket = hashTable[hashedNum];
- bucket.insert(make_pair(hashedNum, val));
- currentSize++;
- return make_pair(hashTable.begin(), true);
- }
- template <class InputIterator>
- void insert(InputIterator first, InputIterator last) {
- if(!satisfiesLoadingFactor()) {
- growTableAndRehash();
- }
- }
- iterator erase(const_iterator position) {
- for(int i = 0; i < hashTable.size(); i++) {
- std::list<std::pair<key_type, mapped_type>>::iterator currIt = hashTable[i].begin();
- std::list<std::pair<key_type, mapped_type>>::iterator end = hashTable[i].end();
- while(currIt != end) {
- list<pair<key_type, mapped_type>> bucket = (*currIt);
- if(currIt == position) {
- bucket.erase(currIt++);
- currentSize--;
- return currIt;
- }else{
- currIt++;
- }
- }
- }
- return position;
- }
- int erase(const key_type& k) {
- int noErased = 0;
- for(int i = 0; i < hashTable.size(); i++) {
- std::list<std::pair<key_type, mapped_type>>::iterator currIt = hashTable[i].begin();
- std::list<std::pair<key_type, mapped_type>>::iterator end = hashTable[i].end();
- while(currIt != end) {
- std::list<std::pair<key_type, mapped_type>> bucket = (*currIt);
- if((bucket->first) == k) {
- bucket.erase(currIt++);
- noErased++;
- currentSize--;
- }else{
- currIt++;
- }
- }
- }
- return noErased;
- }
- void clear() {
- if(empty()) {
- return;
- }
- hashTable.clear();
- currentSize = 0;
- }
- mapped_type &operator[](const K &key) {
- for(int i = 0; i < hashTable.size(); i++) {
- std::list<std::pair<key_type, mapped_type>>::iterator currIt = hashTable[i].begin();
- std::list<std::pair<key_type, mapped_type>>::iterator end = hashTable[i].end();
- while(currIt != end) {
- bucket = (*currIt);
- if((bucket->first) == key) {
- return bucket->second;
- }else{
- currIt++;
- }
- }
- }
- throw "Value was not found in the HashMap!";
- }
- bool operator==(const HashMap<K,V,Hash>& rhs) const {
- return (*this == rhs);
- }
- bool operator!=(const HashMap<K,V,Hash>& rhs) const {return !(*this==rhs);}
- // NOTE: These might be different depending on how you store your table
- iterator begin() {
- return iterator(hashTable.begin(),hashTable.end());
- }
- const_iterator begin() const{
- return const_iterator(hashTable.begin(),hashTable.end());
- }
- iterator end(){
- return iterator(hashTable.end(),hashTable.end());
- }
- const_iterator end() const{
- return const_iterator(hashTable.end(),hashTable.end());
- }
- const_iterator cbegin() const{
- return const_iterator(hashTable.begin(),hashTable.end());
- }
- const_iterator cend() const{
- return const_iterator(hashTable.end(),hashTable.end());
- }
- private:
- void growTableAndRehash() {
- initSize = initSize * 2;
- for(int i = 0; i < (initSize / 2); i++) {
- hashTable.insert(new std::list<std::pair<key_type, mapped_type>> {});
- }
- // rehash the table
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement