· 4 years ago · May 07, 2021, 09:16 AM
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_ = 8;
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 delete[] table_;
54 };
55
56 /*
57 * See https://en.cppreference.com/w/cpp/container/unordered_map/empty
58 *
59 * Returns true if the tree is empty, false otherwise
60 */
61 bool Empty() const {
62 return (Size() == 0);
63 };
64
65 /*
66 * See https://en.cppreference.com/w/cpp/container/unordered_map/size
67 *
68 * Returns the number of elements in the container
69 */
70 size_t Size() const {
71 return size_;
72 };
73
74 /*
75 * See https://en.cppreference.com/w/cpp/container/unordered_map/clear
76 *
77 * Erases all elements from the container.
78 */
79 void Clear() {
80 for (size_t i = 0; i < bucket_count_; i++) {
81 HashNode<Key, T>* temp = table_[i];
82 while (temp != nullptr) {
83 HashNode<Key, T>* parrent = temp;
84 temp = temp->next;
85 delete parrent;
86 }
87 table_[i] = nullptr;
88 }
89 size_ = 0;
90 };
91
92 /*
93 * See https://en.cppreference.com/w/cpp/container/unordered_map/insert
94 *
95 * Returns a bool value set to true if the insertion took place.
96 */
97 bool Insert(const Key& key, const T& value) {
98 if (!Contains(key)) {
99 size_t hash_value = hash_function_(key) % bucket_count_;
100 HashNode<Key, T>* temp = table_[hash_value];
101 HashNode<Key, T>* inserted_hash_node = new HashNode<Key, T>(key, value);
102 HashNode<Key, T>* parrent = nullptr;
103
104 while (temp != nullptr) {
105 parrent = temp;
106 temp = temp->next;
107 }
108 if (parrent != nullptr) {
109 parrent->next = inserted_hash_node;
110 } else {
111 table_[hash_value] = inserted_hash_node;
112 }
113 size_++;
114 return true;
115 } else {
116 return false;
117 }
118 };
119
120 /*
121 * See https://en.cppreference.com/w/cpp/container/unordered_map/erase
122 *
123 * Removes the element from the container with set key.
124 * Returns true if the erase took place.
125 */
126 bool Erase(const Key& key) {
127 if (Contains(key)) {
128 size_t hash_value = hash_function_(key) % bucket_count_;
129 HashNode<Key, T>* temp = table_[hash_value];
130 HashNode<Key, T>* parrent = nullptr;
131
132 while (temp != nullptr && !(equal_(temp->key, key))) {
133 parrent = temp;
134 temp = temp->next;
135 }
136 if (parrent != nullptr) {
137 parrent->next = temp->next;
138 } else {
139 table_[hash_value] = temp->next;
140 }
141 delete temp;
142 size_--;
143 return true;
144
145 } else {
146 return false;
147 }
148 };
149
150 /*
151 * See https://en.cppreference.com/w/cpp/container/unordered_map/contains
152 *
153 * Returns true if an element with key equivalent to value exists in the container.
154 */
155 bool Contains(const Key& key) const {
156 size_t hash_value = hash_function_(key) % bucket_count_;
157 HashNode<Key, T>* temp = table_[hash_value];
158
159 while (temp != nullptr) {
160 if (equal_(temp->key, key)) {
161 return true;
162 }
163 temp = temp->next;
164 }
165 return false;
166 };
167
168 /*
169 * See https://en.cppreference.com/w/cpp/container/unordered_map/operator_at
170 *
171 * Returns a reference to the value that is mapped to a key equivalent to key, performing an
172 * insertion if such key does not already exist.
173 */
174 T& operator[](const Key& key) {
175 size_t hash_value = hash_function_(key) % bucket_count_;
176 HashNode<Key, T>* temp = table_[hash_value];
177 while (temp != nullptr) {
178 if (temp->key == key) {
179 return temp->value;
180 }
181 }
182 return temp->value;
183 };
184
185private:
186 HashNode<Key, T>** table_;
187 size_t bucket_count_;
188 size_t size_;
189 Hash hash_function_;
190 KeyEqual equal_;
191};
192
193int main() {
194 size_t n;
195 std::cin >> n;
196 HashTable<int, int, std::hash<int>, std::equal_to<int>> hash_table;
197 for (size_t i = 0; i < n; i++) {
198 std::string command;
199 std::cin >> command;
200 if (command == "Insert") {
201 int new_key;
202 int new_value;
203 std::cin >> new_key;
204 std::cin >> new_value;
205 std::cout << hash_table.Insert(new_key, new_value) << std::endl;
206 }
207 if (command == "operator") {
208 int new_key;
209 int new_value;
210 std::cin >> new_key;
211 std::cin >> new_value;
212 if (hash_table.Contains(new_key)) {
213 std::cout << new_key << " " << hash_table[new_key] << std::endl;
214 hash_table.Erase(new_key);
215 hash_table.Insert(new_key, new_value);
216 } else {
217 hash_table.Insert(new_key, new_value);
218 std::cout << new_key << " " << new_value << std::endl;
219 }
220 }
221 if (command == "Delete") {
222 int new_key;
223 std::cin >> new_key;
224 std::cout << hash_table.Erase(new_key) << std::endl;
225 }
226 if (command == "Find") {
227 int new_key;
228 std::cin >> new_key;
229 std::cout << hash_table.Contains(new_key) << std::endl;
230 }
231 if (command == "Size") {
232 std::cout << hash_table.Size() << std::endl;
233 }
234 if (command == "Clear") {
235 hash_table.Clear();
236 std::cout << "Clear" << std::endl;
237 }
238 if (command == "Empty") {
239 std::cout << hash_table.Empty() << std::endl;
240 }
241 }
242}