Advertisement
Guest User

HashMap C++ Help

a guest
May 2nd, 2019
191
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.16 KB | None | 0 0
  1. #include <vector>
  2. #include <list>
  3. #include <cassert>
  4. #include <stdexcept>
  5.  
  6. template<typename K,typename V,typename Hash>
  7. class HashMap {
  8. Hash hashFunction;
  9. // TO DO: data to store the hash table, the number of elements and the max_load_factor.
  10.  
  11. std::vector<std::list<std::pair<K,V>>> hashTable;
  12.  
  13. int initSize = 10;
  14.  
  15. int currentSize = 0;
  16. double maxLoadFactor = 0.75;
  17.  
  18. // Suggestion for the hash table: either
  19. // vector<vector<pair<K,V>>> table;
  20. // or
  21. // vector<list<pair<K,V>>> table;
  22. // would work well for the chaining approach.
  23.  
  24. public:
  25. typedef K key_type;
  26. typedef V mapped_type;
  27. typedef std::pair<K,V> value_type;
  28.  
  29. class const_iterator;
  30.  
  31. class iterator {
  32. // NOTE: These might be different depending on how you store your table.
  33. typename std::remove_reference<decltype(hashTable.begin())>::type mainIter;
  34. typename std::remove_reference<decltype(hashTable.begin())>::type mainEnd;
  35. typename std::remove_reference<decltype(hashTable[0].begin())>::type subIter;
  36. public:
  37. friend class const_iterator;
  38. friend class HashMap;
  39.  
  40. // NOTE: These might be different depending on how you store your hashTable..
  41. iterator(const decltype(mainIter) mi,const decltype(mainEnd) me):mainIter(mi),mainEnd(me) {
  42. if(mainIter!=mainEnd) subIter = mainIter->begin();
  43. while(mainIter!=mainEnd && subIter == mainIter->end()) {
  44. ++mainIter;
  45. if(mainIter!=mainEnd) subIter = mainIter->begin();
  46. }
  47. }
  48. // NOTE: These might be different depending on how you store your hashTable..
  49. iterator(const decltype(mainIter) mi,
  50. const decltype(mainEnd) me,
  51. const decltype(subIter) si):
  52. mainIter(mi),mainEnd(me),subIter(si) {}
  53.  
  54. bool operator==(const iterator &i) const { return mainIter==i.mainIter && (mainIter==mainEnd || subIter==i.subIter); }
  55. bool operator!=(const iterator &i) const { return !(*this==i); }
  56. std::pair<K,V> &operator*() { return *subIter; }
  57. iterator &operator++() {
  58. ++subIter;
  59. while(mainIter!=mainEnd && subIter==mainIter->end()) {
  60. ++mainIter;
  61. if(mainIter!=mainEnd) subIter = mainIter->begin();
  62. }
  63. return *this;
  64. }
  65. iterator operator++(int) {
  66. iterator tmp(*this);
  67. ++(*this);
  68. return tmp;
  69. }
  70. };
  71.  
  72. class const_iterator {
  73. // NOTE: These might be different depending on how you store your hashTable..
  74. typename std::remove_reference<decltype(hashTable.cbegin())>::type mainIter;
  75. typename std::remove_reference<decltype(hashTable.cbegin())>::type mainEnd;
  76. typename std::remove_reference<decltype(hashTable[0].cbegin())>::type subIter;
  77. public:
  78. // NOTE: These might be different depending on how you store your table.
  79. const_iterator(const decltype(hashTable.cbegin()) mi,const decltype(hashTable.cbegin()) me):mainIter(mi),mainEnd(me) {
  80. if(mainIter!=mainEnd) subIter = mainIter->begin();
  81. while(mainIter!=mainEnd && subIter == mainIter->end()) {
  82. ++mainIter;
  83. if(mainIter!=mainEnd) subIter = mainIter->begin();
  84. }
  85. }
  86. // NOTE: These might be different depending on how you store your table.
  87. const_iterator(const decltype(hashTable.cbegin()) mi,
  88. const decltype(hashTable.cbegin()) me,
  89. const decltype(hashTable[0].cbegin()) si):
  90. mainIter(mi),mainEnd(me),subIter(si) {}
  91.  
  92. const_iterator(const decltype(hashTable.begin()) mi,
  93. const decltype(hashTable.begin()) me,
  94. const decltype(hashTable[0].begin()) si):
  95. mainIter(mi),mainEnd(me),subIter(si) {}
  96.  
  97. // NOTE: These might be different depending on how you store your table.
  98. const_iterator(const iterator &i):mainIter(i.mainIter),mainEnd(i.mainEnd),subIter(i.subIter) {
  99.  
  100. }
  101.  
  102. bool operator==(const const_iterator &i) const { return mainIter==i.mainIter && (mainIter==mainEnd || subIter==i.subIter); }
  103. bool operator!=(const const_iterator &i) const { return !(*this==i); }
  104. const std::pair<K,V> &operator*() const { return *subIter; }
  105. const_iterator &operator++() {
  106. ++subIter;
  107. while(mainIter!=mainEnd && subIter==mainIter->end()) {
  108. ++mainIter;
  109. if(mainIter!=mainEnd) subIter = mainIter->begin();
  110. }
  111. return *this;
  112. }
  113. const_iterator operator++(int) {
  114. const_iterator tmp(*this);
  115. ++(*this);
  116. return tmp;
  117. }
  118. };
  119.  
  120. // TO DO
  121. HashMap(const Hash &hf) {
  122. hashFunction = hf;
  123.  
  124. for(int i = 0; i < initSize; i++) {
  125. hashTable.insert(new std::list<std::pair<key_type, mapped_type>> {});
  126. }
  127. }
  128. // HashMap(const HashMap<K,V,Hash> &that); // Only if needed.
  129.  
  130. // HashMap &operator=(const HashMap<K,V,Hash> &that); // Only if needed.
  131.  
  132. bool empty() const { return currentSize == 0; }
  133.  
  134. bool satisfiesLoadingFactor() {
  135. return (currentSize / initSize) < maxLoadFactor;
  136. }
  137.  
  138. unsigned int size() const {
  139. return currentSize;
  140. }
  141.  
  142. iterator find(const key_type& k) {
  143. for(int i = 0; i < hashTable.size(); i++) {
  144. std::list<std::pair<key_type, mapped_type>>::iterator currIt = hashTable[i].begin();
  145. std::list<std::pair<key_type, mapped_type>>::iterator end = hashTable[i].end();
  146.  
  147. while(currIt != end) {
  148. std::list<std::pair<key_type, mapped_type>> bucket = (*currIt);
  149.  
  150. if((bucket->first) == k) {
  151. return currIt;
  152. }else{
  153. currIt++;
  154. }
  155. }
  156. }
  157. }
  158.  
  159. const_iterator find(const key_type& k) const {
  160. for(int i = 0; i < hashTable.size(); i++) {
  161. std::list<std::pair<key_type, mapped_type>>::iterator currIt = hashTable[i].begin();
  162. std::list<std::pair<key_type, mapped_type>>::iterator end = hashTable[i].end();
  163.  
  164. while(currIt != end) {
  165. std::list<std::pair<key_type, mapped_type>> bucket = (*currIt);
  166. if((bucket->first) == k) {
  167. return new const_iterator(currIt.begin(), currIt.end());
  168. }else{
  169. currIt++;
  170. }
  171. }
  172. }
  173. }
  174.  
  175. int count(const key_type& k) const {
  176. int count = 0;
  177.  
  178. for(int i = 0; i < hashTable.size(); i++) {
  179. std::list<std::pair<key_type, mapped_type>>::iterator currIt = hashTable[i].begin();
  180. std::list<std::pair<key_type, mapped_type>>::iterator end = hashTable[i].end();
  181.  
  182. while(currIt != end) {
  183. list<pair<key_type, mapped_type>> bucket = (*currIt);
  184. if((bucket->first) == k) {
  185. return bucket.size();
  186. }else{
  187. currIt++;
  188. }
  189. }
  190. }
  191.  
  192. return count;
  193. }
  194.  
  195. std::pair<iterator,bool> insert(const value_type& val) {
  196. if(!satisfiesLoadingFactor()) {
  197. growTableAndRehash();
  198. }
  199.  
  200. int hashedNum = hashFunction(val);
  201.  
  202. while(!hashTable[hashedNum].empty()) {
  203. hashedNum = hashFunction(val);
  204. }
  205.  
  206. std::list<std::pair<key_type, mapped_type>> bucket = hashTable[hashedNum];
  207.  
  208. bucket.insert(make_pair(hashedNum, val));
  209.  
  210. currentSize++;
  211.  
  212. return make_pair(hashTable.begin(), true);
  213.  
  214. }
  215.  
  216. template <class InputIterator>
  217. void insert(InputIterator first, InputIterator last) {
  218. if(!satisfiesLoadingFactor()) {
  219. growTableAndRehash();
  220. }
  221.  
  222.  
  223. }
  224.  
  225. iterator erase(const_iterator position) {
  226. for(int i = 0; i < hashTable.size(); i++) {
  227. std::list<std::pair<key_type, mapped_type>>::iterator currIt = hashTable[i].begin();
  228. std::list<std::pair<key_type, mapped_type>>::iterator end = hashTable[i].end();
  229.  
  230. while(currIt != end) {
  231. list<pair<key_type, mapped_type>> bucket = (*currIt);
  232.  
  233. if(currIt == position) {
  234. bucket.erase(currIt++);
  235. currentSize--;
  236. return currIt;
  237. }else{
  238. currIt++;
  239. }
  240. }
  241. }
  242.  
  243. return position;
  244. }
  245.  
  246. int erase(const key_type& k) {
  247.  
  248. int noErased = 0;
  249.  
  250. for(int i = 0; i < hashTable.size(); i++) {
  251. std::list<std::pair<key_type, mapped_type>>::iterator currIt = hashTable[i].begin();
  252. std::list<std::pair<key_type, mapped_type>>::iterator end = hashTable[i].end();
  253.  
  254. while(currIt != end) {
  255. std::list<std::pair<key_type, mapped_type>> bucket = (*currIt);
  256.  
  257. if((bucket->first) == k) {
  258. bucket.erase(currIt++);
  259. noErased++;
  260. currentSize--;
  261. }else{
  262. currIt++;
  263. }
  264. }
  265. }
  266.  
  267. return noErased;
  268. }
  269.  
  270. void clear() {
  271. if(empty()) {
  272. return;
  273. }
  274.  
  275. hashTable.clear();
  276.  
  277. currentSize = 0;
  278. }
  279.  
  280. mapped_type &operator[](const K &key) {
  281. for(int i = 0; i < hashTable.size(); i++) {
  282. std::list<std::pair<key_type, mapped_type>>::iterator currIt = hashTable[i].begin();
  283. std::list<std::pair<key_type, mapped_type>>::iterator end = hashTable[i].end();
  284.  
  285. while(currIt != end) {
  286. bucket = (*currIt);
  287.  
  288. if((bucket->first) == key) {
  289. return bucket->second;
  290. }else{
  291. currIt++;
  292. }
  293. }
  294. }
  295.  
  296. throw "Value was not found in the HashMap!";
  297. }
  298.  
  299. bool operator==(const HashMap<K,V,Hash>& rhs) const {
  300. return (*this == rhs);
  301. }
  302.  
  303. bool operator!=(const HashMap<K,V,Hash>& rhs) const {return !(*this==rhs);}
  304.  
  305. // NOTE: These might be different depending on how you store your table
  306. iterator begin() {
  307. return iterator(hashTable.begin(),hashTable.end());
  308. }
  309.  
  310. const_iterator begin() const{
  311. return const_iterator(hashTable.begin(),hashTable.end());
  312. }
  313.  
  314. iterator end(){
  315. return iterator(hashTable.end(),hashTable.end());
  316. }
  317.  
  318. const_iterator end() const{
  319. return const_iterator(hashTable.end(),hashTable.end());
  320. }
  321.  
  322. const_iterator cbegin() const{
  323. return const_iterator(hashTable.begin(),hashTable.end());
  324. }
  325.  
  326. const_iterator cend() const{
  327. return const_iterator(hashTable.end(),hashTable.end());
  328. }
  329.  
  330. private:
  331. void growTableAndRehash() {
  332. initSize = initSize * 2;
  333.  
  334. for(int i = 0; i < (initSize / 2); i++) {
  335. hashTable.insert(new std::list<std::pair<key_type, mapped_type>> {});
  336. }
  337.  
  338. // rehash the table
  339. }
  340. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement