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