We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
class LRUCache : public Cache {
Node *ptr_bf{};
public:
LRUCache(int capacity) {
cp = capacity;
tail = nullptr;
head = nullptr;
}
~LRUCache() {
while (head != nullptr) {
ptr_bf = head->next;
delete head;
head = ptr_bf;
}
}
void set(int k, int v) {
if (mp.find(k) != mp.end()) { // if key found
ptr_bf = mp[k];
ptr_bf->value = v;
if (ptr_bf->prev != nullptr) {
if (ptr_bf->next == nullptr) { // if last element in linked list
tail = ptr_bf->prev;
ptr_bf->prev->next = nullptr;
} else { // else if not last
ptr_bf->prev->next = ptr_bf->next;
ptr_bf->next->prev = ptr_bf->prev;
}
ptr_bf->prev = nullptr;
ptr_bf->next = head;
head = mp[k];
}
} else { // if key not found
if (mp.empty()) { // if size of map is 0
Node *new_node = new Node(k, v);
mp[k] = new_node;
head = new_node;
tail = new_node;
} else if (mp.size() >= cp) { // if size of map reach max capacity
//pop last
mp.erase(tail->key);
ptr_bf = tail->prev;
delete tail;
tail = ptr_bf;
tail->next = nullptr;
//add new
Node *new_node = new Node(nullptr, head, k, v);
mp[k] = new_node;
head->prev = new_node;
head = new_node;
} else { // if size of map normal
Node *new_node = new Node(nullptr, head, k, v);
mp[k] = new_node;
head->prev = new_node;
head = new_node;
}
}
}
int get(int k) {
if (mp.find(k) != mp.end()) { // if key is present
return mp[k]->value;
} else { // if key not present
return -1;
}
}
};
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Abstract Classes - Polymorphism
You are viewing a single comment's thread. Return to all comments →
class LRUCache : public Cache { Node *ptr_bf{}; public: LRUCache(int capacity) { cp = capacity; tail = nullptr; head = nullptr; }
};