#include <bits/stdc++.h>
using namespace std;
class LRUCache {
public:
int capacity;
unordered_map<int, list<pair<int, int>>::iterator> map;
list<pair<int, int>> values;
LRUCache(int capacity) {
this->capacity = capacity;
}
int get(int key) {
if(map.find(key) == map.end()) {
return -1;
}
else {
list<pair<int, int>>::iterator itr = map[key];
int key = itr->first;
int value = itr->second;
values.erase(itr);
values.push_front({key, value});
map[key] = values.begin();
return value;
}
}
void put(int key, int value) {
if(map.find(key) == map.end()) {
if(map.size() == this->capacity) {
// delete oldest
list<pair<int, int>>::iterator itr = values.end();
itr--;
map.erase(itr->first);
values.erase(itr);
values.push_front({key, value});
map[key] = values.begin();
}
else {
// only insertion
values.push_front({key, value});
map[key] = values.begin();
}
}
else {
// no change in capacity, only value changes
list<pair<int, int>>::iterator itr = map[key];
int key = itr->first;
values.erase(itr);
values.push_front({key, value});
map[key] = values.begin();
}
}
};
int main() {
LRUCache* lRUCache = new LRUCache(2);
lRUCache->put(1, 1); // cache is {1=1}
lRUCache->put(2, 2); // cache is {1=1, 2=2}
cout << lRUCache->get(1) << endl; // return 1
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpjbGFzcyBMUlVDYWNoZSB7CnB1YmxpYzoKICAgIGludCBjYXBhY2l0eTsKICAgIHVub3JkZXJlZF9tYXA8aW50LCBsaXN0PHBhaXI8aW50LCBpbnQ+Pjo6aXRlcmF0b3I+IG1hcDsKICAgIGxpc3Q8cGFpcjxpbnQsIGludD4+IHZhbHVlczsKICAgIExSVUNhY2hlKGludCBjYXBhY2l0eSkgewogICAgICAgIHRoaXMtPmNhcGFjaXR5ID0gY2FwYWNpdHk7CiAgICB9CiAgICAKICAgIGludCBnZXQoaW50IGtleSkgewogICAgICAgIGlmKG1hcC5maW5kKGtleSkgPT0gbWFwLmVuZCgpKSB7CiAgICAgICAgICAgIHJldHVybiAtMTsKICAgICAgICB9CgogICAgICAgIGVsc2UgewogICAgICAgICAgIGxpc3Q8cGFpcjxpbnQsIGludD4+OjppdGVyYXRvciBpdHIgPSBtYXBba2V5XTsKICAgICAgICAgICBpbnQga2V5ID0gaXRyLT5maXJzdDsKICAgICAgICAgICBpbnQgdmFsdWUgPSBpdHItPnNlY29uZDsKICAgICAgICAgICB2YWx1ZXMuZXJhc2UoaXRyKTsKICAgICAgICAgICB2YWx1ZXMucHVzaF9mcm9udCh7a2V5LCB2YWx1ZX0pOwogICAgICAgICAgIG1hcFtrZXldID0gdmFsdWVzLmJlZ2luKCk7CiAgICAgICAgICAgcmV0dXJuIHZhbHVlOwogICAgICAgIH0KICAgIH0KICAgIAogICAgdm9pZCBwdXQoaW50IGtleSwgaW50IHZhbHVlKSB7CiAgICAgICAgaWYobWFwLmZpbmQoa2V5KSA9PSBtYXAuZW5kKCkpIHsKICAgICAgICAgICAgaWYobWFwLnNpemUoKSA9PSB0aGlzLT5jYXBhY2l0eSkgewogICAgICAgICAgICAgICAgLy8gZGVsZXRlIG9sZGVzdAogICAgICAgICAgICAgICAgbGlzdDxwYWlyPGludCwgaW50Pj46Oml0ZXJhdG9yIGl0ciA9IHZhbHVlcy5lbmQoKTsKICAgICAgICAgICAgICAgIGl0ci0tOwogICAgICAgICAgICAgICAgbWFwLmVyYXNlKGl0ci0+Zmlyc3QpOwogICAgICAgICAgICAgICAgdmFsdWVzLmVyYXNlKGl0cik7CiAgICAgICAgICAgICAgICB2YWx1ZXMucHVzaF9mcm9udCh7a2V5LCB2YWx1ZX0pOwogICAgICAgICAgICAgICAgbWFwW2tleV0gPSB2YWx1ZXMuYmVnaW4oKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgZWxzZSB7CiAgICAgICAgICAgICAgICAvLyBvbmx5IGluc2VydGlvbgogICAgICAgICAgICAgICAgdmFsdWVzLnB1c2hfZnJvbnQoe2tleSwgdmFsdWV9KTsKICAgICAgICAgICAgICAgIG1hcFtrZXldID0gdmFsdWVzLmJlZ2luKCk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgCiAgICAgICAgfQogICAgICAgIAogICAgICAgIGVsc2UgewogICAgICAgICAgICAvLyBubyBjaGFuZ2UgaW4gY2FwYWNpdHksIG9ubHkgdmFsdWUgY2hhbmdlcwogICAgICAgICAgICBsaXN0PHBhaXI8aW50LCBpbnQ+Pjo6aXRlcmF0b3IgaXRyID0gbWFwW2tleV07CiAgICAgICAgICAgIGludCBrZXkgPSBpdHItPmZpcnN0OwogICAgICAgICAgICB2YWx1ZXMuZXJhc2UoaXRyKTsKICAgICAgICAgICAgdmFsdWVzLnB1c2hfZnJvbnQoe2tleSwgdmFsdWV9KTsKICAgICAgICAgICAgbWFwW2tleV0gPSB2YWx1ZXMuYmVnaW4oKTsKICAgICAgICAgICAgCiAgICAgICAgfQogICAgfQp9OwoKCmludCBtYWluKCkgewoJCglMUlVDYWNoZSogbFJVQ2FjaGUgPSBuZXcgTFJVQ2FjaGUoMik7CglsUlVDYWNoZS0+cHV0KDEsIDEpOyAvLyBjYWNoZSBpcyB7MT0xfQoJbFJVQ2FjaGUtPnB1dCgyLCAyKTsgLy8gY2FjaGUgaXMgezE9MSwgMj0yfQoJY291dCA8PCBsUlVDYWNoZS0+Z2V0KDEpIDw8IGVuZGw7ICAgIC8vIHJldHVybiAxCgkKCXJldHVybiAwOwp9Cg==