Skip to content

Instantly share code, notes, and snippets.

@lectricas
Created March 29, 2021 21:00
Show Gist options
  • Save lectricas/c290e526e84162015eadf050d3cbf249 to your computer and use it in GitHub Desktop.
Save lectricas/c290e526e84162015eadf050d3cbf249 to your computer and use it in GitHub Desktop.
#include <string>
#include <array>
#include <iostream>
#include <unordered_map>
#include <cassert>
#include <sstream>
using namespace std;
#define m 104729
class IntHashMap {
class Node {
public:
Node(const int key, const int value, Node *next, Node *prev) {
this->key = key;
this->value = value;
this->next = next;
this->prev = prev;
}
int value;
int key;
Node *next;
Node *prev;
};
array<Node *, m> arr{};
public:
void put(const int key, const int value) {
int bucket = key % m;
Node *n = new Node(key, value, nullptr, nullptr);
if (arr[bucket] == nullptr) {
arr[bucket] = n;
} else {
Node *current = arr[bucket];
while (current != nullptr) {
if (current->key == key) {
current->value = value;
return;
}
current = current->next;
}
arr[bucket]->prev = n;
n->next = arr[bucket];
arr[bucket] = n;
}
}
public:
int get(const int key) {
int bucket = key % m;
Node *current = arr[bucket];
while (current != nullptr) {
if (current->key == key) {
return current->value;
}
current = current->next;
}
throw "None";
}
public:
int remove(const int key) {
int bucket = key % m;
Node *current = arr[bucket];
while (current != nullptr) {
if (current->key == key) {
int value = current->value;
if (current->prev == nullptr) {
arr[bucket] = current->next;
}
if (current->next != nullptr) {
current->next->prev = current->prev;
}
if (current->prev != nullptr) {
current->prev->next = current->next;
}
return value;
}
current = current->next;
}
throw "None";
}
};
int main() {
IntHashMap *map = new IntHashMap();
int n;
cin >> n;
std::cin.ignore();
for (int i = 0; i < n; i++) {
std::string line, command;
getline(std::cin, line);
istringstream iss(line);
iss >> command;
try {
int key;
iss >> key;
if (command == "get") {
cout << map->get(key) << "\n";
} else if (command == "delete") {
cout << map->remove(key) << "\n";
} else if (command == "put") {
int value;
iss >> value;
map->put(key, value);
}
} catch (const char *msg) {
std::cout << msg << "\n";
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment