Hard
An LRU cache built from a hash map and a linked list
This LRUCache is intended to support get and put in O(1). Does it actually achieve that?
main.cpp
#include <list>
#include <unordered_map>
class LRUCache {
int capacity;
std::list<int> order; // most recently used at front
std::unordered_map<int, int> cache; // key -> value
public:
LRUCache(int cap) : capacity(cap) {}
int get(int key) {
auto it = cache.find(key);
if (it == cache.end()) return -1;
order.remove(key); // move key to front
order.push_front(key);
return it->second;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
order.remove(key);
} else if ((int)cache.size() >= capacity) {
int lru = order.back();
order.pop_back();
cache.erase(lru);
}
order.push_front(key);
cache[key] = value;
}
};16 of 46 in Data Structures & Algorithms