Skip to content

Instantly share code, notes, and snippets.

@vitkarpov
Created October 17, 2019 13:42
Show Gist options
  • Save vitkarpov/cda7b80083ecda641a85423b4d70f3c1 to your computer and use it in GitHub Desktop.
Save vitkarpov/cda7b80083ecda641a85423b4d70f3c1 to your computer and use it in GitHub Desktop.
class LRUCache {
typedef pair<int, int> Node;
typedef list<Node>::iterator ref;
list<Node> q;
unordered_map<int, ref> m;
int capacity;
void insert(int key, int value) {
if (m.find(key) != m.end()) {
q.erase(m[key]);
m.erase(key);
}
q.push_front(make_pair(key, value));
m[key] = q.begin();
if (q.size() > capacity) {
m.erase(q.back().first);
q.pop_back();
}
}
public:
LRUCache(int v) : capacity(v) {
m.reserve(capacity);
}
int get(int key) {
if (m.find(key) == m.end()) {
return -1;
}
int value = m[key]->second;
insert(key, value);
return value;
}
void put(int key, int value) {
insert(key, value);
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment