Hard LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:
get
and set
.get(key)
- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value)
- Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
class DllNode
{
public:
DllNode *prev;
DllNode *next;
int val;
int key;
DllNode(int key, int val)
{
this->key = key;
this->val = val;
this->prev = this;
this->next = this;
}
void Detach()
{
prev->next = next;
next->prev = prev;
}
void AddLeft(DllNode *node)
{
prev->next = node;
node->prev = prev;
node->next = this;
prev = node;
}
};
class LRUCache{
public:
int m_cap;
DllNode m_head;
unordered_map<int, DllNode *> m_map;
LRUCache(int capacity): m_head(0,0)
{
m_cap = capacity;
}
int get(int key) {
if (m_map.count(key) ==0)
return -1;
DllNode *node = m_map[key];
node->Detach();
m_head.AddLeft(node);
return node->val;
}
void set(int key, int value) {
if (m_map.find(key) != m_map.end())
{
DllNode *node = m_map[key];
node->Detach();
delete node;
m_map.erase(key);
}
if (m_map.size() == m_cap)
{
DllNode *oldest = m_head.next;
oldest->Detach();
m_map.erase(oldest->key);
delete oldest;
}
DllNode *node = new DllNode(key, value);
m_head.AddLeft(node);
m_map[key] = node;
}
};
No comments:
Post a Comment