· 4 years ago · May 06, 2021, 09:18 PM
1#include <functional>
2#include <iostream>
3
4template <typename Key, typename T>
5class HashNode {
6public:
7 Key key;
8 T value;
9 HashNode* next;
10 HashNode(Key key, T value) : key(key), value(value), next(nullptr) {
11 }
12};
13
14template <typename Key, typename T, typename Hash = std::hash<Key>,
15 typename KeyEqual = std::equal_to<Key>>
16class HashTable {
17public:
18 /*
19 * See https://en.cppreference.com/w/cpp/container/unordered_map/unordered_map (1)
20 *
21 * Constructs new container. The number of buckets to create is implementation-defined.
22 */
23 HashTable() {
24 bucket_count_ = 10;
25 size_ = 0;
26 table_ = new HashNode<Key, T>*[bucket_count_];
27 for (size_t i = 0; i < bucket_count_; i++) {
28 table_[i] = nullptr;
29 }
30 };
31
32 /*
33 * See https://en.cppreference.com/w/cpp/container/unordered_map/unordered_map (1)
34 *
35 * Constructs new container, uses bucket_count parameter as a minimal number of buckets to
36 * create.
37 */
38 explicit HashTable(size_t bucket_count) {
39 bucket_count_ = bucket_count;
40 size_ = 0;
41 table_ = new HashNode<Key, T>*[bucket_count_];
42 for (size_t i = 0; i < bucket_count_; i++) {
43 table_[i] = nullptr;
44 }
45 };
46
47 HashTable(const HashTable& other) {
48 *this = other;
49 };
50
51 ~HashTable() {
52 Clear();
53 };
54
55 /*
56 * See https://en.cppreference.com/w/cpp/container/unordered_map/empty
57 *
58 * Returns true if the tree is empty, false otherwise
59 */
60 bool Empty() const {
61 return (Size() == 0);
62 };
63
64 /*
65 * See https://en.cppreference.com/w/cpp/container/unordered_map/size
66 *
67 * Returns the number of elements in the container
68 */
69 size_t Size() const {
70 return size_;
71 };
72
73 /*
74 * See https://en.cppreference.com/w/cpp/container/unordered_map/clear
75 *
76 * Erases all elements from the container.
77 */
78 void Clear() {
79 for (size_t i = 0; i < bucket_count_; i++) {
80 while (table_[i] != nullptr) {
81 HashNode<Key, T>* temp = table_[i];
82 table_[i] = table_[i]->next;
83 delete temp;
84 }
85 table_[i] = nullptr;
86 }
87 size_ = 0;
88 };
89
90 /*
91 * See https://en.cppreference.com/w/cpp/container/unordered_map/insert
92 *
93 * Returns a bool value set to true if the insertion took place.
94 */
95 bool Insert(const Key& key, const T& value) {
96 if (!Contains(key)) {
97 size_t hash_value = hash_function_(key) % bucket_count_;
98 HashNode<Key, T>* temp = table_[hash_value];
99 HashNode<Key, T>* inserted_hash_node = new HashNode<Key, T>(key, value);
100 HashNode<Key, T>* parrent = nullptr;
101
102 while (temp != nullptr) {
103 parrent = temp;
104 temp = temp->next;
105 }
106 if (parrent != nullptr) {
107 parrent->next = inserted_hash_node;
108 } else {
109 table_[hash_value] = inserted_hash_node;
110 }
111 size_++;
112 return true;
113 } else {
114 return false;
115 }
116 };
117
118 /*
119 * See https://en.cppreference.com/w/cpp/container/unordered_map/erase
120 *
121 * Removes the element from the container with set key.
122 * Returns true if the erase took place.
123 */
124 bool Erase(const Key& key) {
125 if (Contains(key)) {
126 size_t hash_value = hash_function_(key) % bucket_count_;
127 HashNode<Key, T>* temp = table_[hash_value];
128 HashNode<Key, T>* parrent = nullptr;
129
130 while (temp != nullptr && !(equal_(temp->key, key))) {
131 parrent = temp;
132 temp = temp->next;
133 }
134 if (parrent != nullptr) {
135 parrent->next = temp->next;
136 } else {
137 table_[hash_value] = temp->next;
138 }
139 delete temp;
140 size_--;
141 return true;
142
143 } else {
144 return false;
145 }
146 };
147
148 /*
149 * See https://en.cppreference.com/w/cpp/container/unordered_map/contains
150 *
151 * Returns true if an element with key equivalent to value exists in the container.
152 */
153 bool Contains(const Key& key) const {
154 size_t hash_value = hash_function_(key) % bucket_count_;
155 HashNode<Key, T>* temp = table_[hash_value];
156
157 while (temp != nullptr) {
158 if (equal_(temp->key, key)) {
159 return true;
160 }
161 temp = temp->next;
162 }
163 return false;
164 };
165
166 /*
167 * See https://en.cppreference.com/w/cpp/container/unordered_map/operator_at
168 *
169 * Returns a reference to the value that is mapped to a key equivalent to key, performing an
170 * insertion if such key does not already exist.
171 */
172 T& operator[](const Key& key) {
173 size_t hash_value = hash_function_(key) % bucket_count_;
174 HashNode<Key, T>* temp = table_[hash_value];
175 while (temp != nullptr) {
176 if (temp->key == key) {
177 return temp->value;
178 }
179 }
180 return temp->value;
181 };
182
183private:
184 HashNode<Key, T>** table_;
185 size_t bucket_count_;
186 size_t size_;
187 Hash hash_function_;
188 KeyEqual equal_;
189};
190
191int main() {
192 size_t n;
193 std::cin >> n;
194 HashTable<int, int, std::hash<int>, std::equal_to<int>> hash_table;
195 for (size_t i = 0; i < n; i++) {
196 std::string command;
197 std::cin >> command;
198 if (command == "Insert") {
199 int new_key;
200 int new_value;
201 std::cin >> new_key;
202 std::cin >> new_value;
203 std::cout << hash_table.Insert(new_key, new_value) << std::endl;
204 }
205 if (command == "operator") {
206 int new_key;
207 int new_value;
208 std::cin >> new_key;
209 std::cin >> new_value;
210 if (hash_table.Contains(new_key)) {
211 std::cout << new_key << " " << hash_table[new_key] << std::endl;
212 hash_table.Erase(new_key);
213 hash_table.Insert(new_key, new_value);
214 } else {
215 hash_table.Insert(new_key, new_value);
216 std::cout << new_key << " " << new_value << std::endl;
217 }
218 }
219 if (command == "Delete") {
220 int new_key;
221 std::cin >> new_key;
222 std::cout << hash_table.Erase(new_key) << std::endl;
223 }
224 if (command == "Find") {
225 int new_key;
226 std::cin >> new_key;
227 std::cout << hash_table.Contains(new_key) << std::endl;
228 }
229 if (command == "Size") {
230 std::cout << hash_table.Size() << std::endl;
231 }
232 if (command == "Clear") {
233 hash_table.Clear();
234 std::cout << "Clear" << std::endl;
235 }
236 if (command == "Empty") {
237 std::cout << hash_table.Empty() << std::endl;
238 }
239 }
240}