Python
There’s many possible implementations for LRU Caches in Python, but probably one of the shortest implementation is through OrderedDict (python >= 3.1). For python >= 3.7, any dict is ordered, but the API does not allow popping items from the start.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
if key not in self.cache:
return -1
val = self.cache[key]
# put the key to the last
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
elif len(self.cache) == self.capacity:
self.cache.popitem(last=False)
self.cache[key] = value
C++
The C++ standard library provides a nice abstraction for linked lists, which provides the splice method.
class LRUCache {
private:
int m_capacity {};
// key, val
std::list<std::pair<int, int>> m_l;
std::unordered_map<int, std::list<std::pair<int, int>>::iterator> m_mp;
void moveToLast(std::list<std::pair<int, int>>::iterator it) {
// put the item at the end of the list
auto it2 = std::next(it, 1);
m_l.splice(m_l.end(), m_l, it, it2);
}
public:
LRUCache(int capacity)
: m_capacity {capacity} {
}
int get(int key) {
int val {-1};
auto it_mp = m_mp.find(key);
if (it_mp != m_mp.end()) {
auto it_li = it_mp->second;
val = it_li->second;
moveToLast(it_li);
}
return val;
}
void put(int key, int value) {
auto it_mp = m_mp.find(key);
if (it_mp != m_mp.end()) {
auto it_li = it_mp->second;
it_li->second = value;
moveToLast(it_li);
} else {
if (m_mp.size() >= m_capacity) {
// evict the front
m_mp.erase(m_l.front().first);
m_l.pop_front();
}
m_l.emplace_back(key, value);
m_mp.insert({key, std::prev(m_l.end())});
}
}
};
Leave a Reply